Invisible <voi### [at] devnull> wrote:
> A Min Heap is a kind of binary tree that stores data in such a way that 
> retrieving the "minimum" element is an O(1) operation. Insertion and 
> deletion are both O(log n), and I believe joining two heaps should be 
> O(log n) as well.

> A "heap sort" involves turning something into a heap (with O(n log n) 
> complexity) and then repeatedly removing the minimum element (with O(n) 
> complexity) to yield a fully sorted list.

  Btw, a balanced binary search tree has all those properties and then
some. Insertion and deletion are O(log n) operations, and you can not
only get the minimum but *also* the maximum element in O(1) time. Such
a tree can be used to sort a list of elements in O(n log n) time.
Moreover, the tree preserves full ordering: If so needed, you can traverse
the entire tree in O(n) steps and get all the elements in increasing order
(something you can't do with a heap). And even moreover, *searching* for
an element is an O(log n) operation (again something which cannot be done
so fast with a heap).

  So the question arises: Given that a balanced binary search tree has all
the same properties as a heap, and even more, why are heaps considered
useful at all?

  The answer is: Heaps don't require any ancillary data whatsoever (while
balanced binary search trees require three pointers and a flag for each
element). Moreover, the entire heap can be stored in a contiguous array
(which, as said, doesn't require *any* additional data).

  This is what makes heaps more efficient than binary search trees in
many cases. For example using a binary tree for sorting an array of
elements requires O(n) amount of additional RAM, while using heap sort
requires O(1) additional memory. Same applies, for example, for a priority
queue.

  Note that a heap requires random access (at least if it's used without
any ancillary data), while a binary tree doesn't. For this reason a heap
can only be used efficiently with arrays.

  So this raises another question: If you are going to use a heap with
something else than an array (for example a tree structure), what are
the advantages of the heap over a regular balanced binary search tree?
The advantages of the binary tree over the heap are plenty. By constructing
a heap tree you are throwing away the one property heaps have: Space
efficiency.

-- 
                                                          - Warp

Post a reply to this message