Re: Heap vs BST


alex.gman@xxxxxxxxx wrote:
> sillybanter@xxxxxxxxx wrote:
> > alex.gman@xxxxxxxxx wrote:
> >
> > > Ok, if I cache max of a BST, then get_max is O(1), and my BST behaves
> > > like a Heap, but also provides the usual extras. Makes me wonder, what
> > > are the advantages of Heaps over BSTs now, after get_max is no longer
> > > one of them?
> >
> > Are you going to keep your BST balanced?
>
> Yes
>
> > If so, then the code is much
> > more complex. Compare an AVL implementation (insert with rebalance
> > would probably be 100+ lines of code) to a heap (insert can be done in
> > about 5-6 lines of code).
>
> I don't think this matters much, because this is library code. Written
> once, used by many people many times.
>
> > Add to that the fact that balanced BST
> > require pointers or indices to indicate parent/child relationships,
> > whereas a heap can be thrown into an array with implied (or computed)
> > parent/child relationships, and you see that heaps are in fact quite a
> > bit more space efficient.

> Firstly, there are pluses and minuses to using "pointers" instead of
> storing everything in an array. Arrays are difficult to grow.

Right, with binary heap (the standard array implementation), you
get O(log n) amortized per op. It's only an amortized bound since
you need to grow the array periodically, say by repeated doubling.

> Secondly, why shouldn't I put my AVL tree onto an array as well, and
> use the same parent/children formula?

The parent/child formula works on binary heaps because the
tree is perfectly balanced. Your AVL tree won't stay perfectly
balanced.

.

Relevant Pages

  • Re: Array Fundamentals
    ... When a value-type object is created, C# allocates a single ... the values inside an Array should be allocated ... reside on the heap ... >type is that only the reference type exist on the heap. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Garbage collectable pinned arrays!
    ... But collecting the object and ... When the array is pinned it is copied to heap. ... compacts the generation containing the array. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Garbage collectable pinned arrays!
    ... reference to it anywhere on the call stack. ... But collecting the object and ... When the array is pinned it is copied to heap. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: BMP/JPG/GIF library in Ada?
    ... I've chosen a constrained representation inheriting from Controlled. ... The internal array of data is ... or having to do the heap work in that outer type. ... What worries me is that even if using the heap I evade the stack ...
    (comp.lang.ada)
  • Re: Datenstruktur gesucht =?ISO-8859-1?Q?f=FCr_A*?=
    ... Das Array enthält zunächst nur null. ... Dies erlaubt eine äußerst schnelle Implementierung um festzustellen ob ein Feld in der Open List ist. ... Datenredundanz erzeugen, ... Implementierungen einer Binary Heap in dieser Art schneller sein, als mit den Standard Collection-Klasse von Java. ...
    (de.comp.lang.java)