Warp wrote:
> 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.
> 
>   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?

I was under the impression that any kind of balanced tree tends to be 
faster to access [because it's balanced, so you avoid the O(n) 
worst-case behaviour], but slower to update [because you have to keep 
re-balancing it]. A heap is much simpler to keep balanced because you 
have far more freedom about where to put things. (On the other hand, an 
in-order traversal is much slower.)

So it appears to me that the two simply have "different" properties. 
Some things are more efficient with a heap, some with a balanced search 
tree.

Unless you know something I don't...

>   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).
> 
>   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.

Hmm, interesting...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message