On 8/2/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
> Does anybody have 'j code' implementing this? The
> discription found at:
>
> http://citeseer.ist.psu.edu/cachedpage/526368/1
I have not.
That said, I should note that one of the assertions in that paper -- that
a binary tree requires the use of pointers to locate parent/child nodes --
is not necessarily true.
To illustrate, here's a model of a priority queue. Relevant verbs are
addnode n, and delnode '' -- delnode always returns the first node in
what would be sorted order, for the nodes which are present at the
time it runs.
Note that this is intended as a queue -- there are much more efficient
approaches if I can operate on large lists of nodes.
Note also that this is intended as a model -- for example my implementation
of a node is brutally simple, and not particularly useful, and I'm not very
efficient in managing memory during some operations. These could
easily be changed, but I didn't need anything better, so didn't bother.
Also, note that the operation of adding a node to the tree could be
performed as a single vector operation, sorting the nodes at the list
of indices given by (0>.<[EMAIL PROTECTED]:)^:a: instead of using repeated
swapping.
And -- my main point -- I do not use pointers at all, when representing
the parent/child relationship between nodes. I don't think those
pointers would add anything useful unless you need to be able to
quickly remove nodes from arbitrary locations in the tree and your
application is such that "nothing here" placeholders would be too
expensive to maintain -- and I've not investageted such cases
well enough to know that those pointers would really be required even
there -- as long as your algorithm keeps the tree reasonably close to
balanced, I think that that issue should not become a major issue.
heap=: '' NB. 0: parent, 1: 1st child, 2: 2nd child, 3: 1st child's
1st child, ...
NB. heap is x for dyads, global for monads
NB. y is value -- nodes are boxed integers (deadlines)
node=: <^:(1-L.)
addnode=:3 :0
heap=: heap addnode y
:
(x,node y) upheap #x
)
delnode=:3 :0
r=.0{::heap
heap=: heap delnode ''
r
:
(}:x swap 0 _1) downheap 0
)
NB. y is index pair
swap=: ({~|.)`]`[}
NB. y is index
parent=: <[EMAIL PROTECTED]:@<:
upheap=:3 :0
heap=: heap upheap y
:
if.1>y do.x return.end.
pair=.(,parent)y
if.(-:\:~)pair{x do.x return. end.
(x swap pair) upheap {:pair
)
downheap=:3 :0
heap=: heap downheap y
:
assert.0=#$y
inds=.y,(#~ (#x) > ]) 1 2+2*y
if.2>#inds do.x return.end.
vals=./:~inds{x
if.(y{x) -: {.vals do.x return.end.
kid=.{.inds{~vals i.~inds{x
(x swap y,kid) downheap kid
)
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
