Re: Heap vs BST

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.

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

.

Relevant Pages

  • Re: Heap vs BST
    ... > Ok, if I cache max of a BST, then get_max is O, and my BST behaves ... > like a Heap, but also provides the usual extras. ... require pointers or indices to indicate parent/child relationships, ...
    (comp.theory)
  • Re: Heapsorting doubly-linked lists in C
    ... >> you don't have a sorted list to begin with, and you don't want a BST. ... > You weren't suggesting arranging the heap as a binary tree? ... not a binary *search* tree. ...
    (comp.programming)
  • Heap vs BST
    ... Ok, if I cache max of a BST, then get_max is O, and my BST behaves ... like a Heap, but also provides the usual extras. ...
    (comp.theory)
  • Dynamic memory in binary search tree (BST) object
    ... contains another object having a dynamically allocated array. ... there's a BST Node object that includes this base data type: ... need to be a pointer back to the parent. ...
    (alt.comp.lang.borland-delphi)
  • Re: Heap vs BST
    ... >>> like a Heap, but also provides the usual extras. ... >> require pointers or indices to indicate parent/child relationships, ... > storing everything in an array. ... Your AVL tree won't stay perfectly ...
    (comp.theory)