|
![](/i/fill.gif) |
Warp wrote:
> Invisible <voi### [at] dev null> 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
|
![](/i/fill.gif) |