Tim Nikias <tim### [at] gmxde> wrote:
> 3. Inserting and deleting entries using a dropping-algorithm
> (forgot the actual name right now), where the smaller values
> simply "trickle" through till the bottom of the tree, wouldn't be
> that difficult to add, its just a recursive macro-call, or could perhaps
> even be put into a while-loop

  Don't confuse a binary tree with a binary heap.
  A heap is very easy and fast to construct. Rearranging an array into a
heap can be done statically and in O(n*log n) time. Inserting a value
into a heapified array can be done statically and in O(log n) time.
  However, a heap is not a binary tree and doesn't have the advantages of
the tree. You can't find a certain item in a heap in O(log n) time, as you
can do in a tree. If you want to insert a new value in a "treed" array it will
probably require at least O(n) time, perhaps even O(n*log n) (I'm not
sure about this, so I may well be wrong).

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message