TH>OTOH, a heap is only slightly more complex, but its effiency is
TH>O(log2N),
BK>Shouldn't that be at least O(N * log2 N)? How could a sort
BK>algorithm ever be faster than O(N), which would IMHO mean that it
BK>wouldn't even have to access every element.
Yep. A heap does *not* access every element - that is per insertion.
O(logN) is a tell tail sign of a binary tree, and that is what a heap
is. However, a heap is usually implemented as an array for efficiency.
So, when an insertion takes place, the comparison of the insertion
key starts at the end of the array, and in binary fashion trickles to
the top. Each level up halves the posibilities. So, say, 255 elements
has only seven accesses at most to make. It made only need to make
one access. This is called reheaping.
When the highest or lowest (depending on whether it is a MAX-heap, or
a MIN-heap) element is popped off. A reheap is also required. That,
too, is O(logN).... Hmmm. come to think of it, maybe I should have
said O(2logN) since it is does get reheaped twice, once going in and
again comming out.
At any rate it is very fast on large sets.
BTW, heaps make real good priority trees, but they are not the
panacia of sorts. You can only look at the top element in the sort.
If you want to look at them all, you have to pop them off, and that
destroys them as they go. You can work off a copy of the heap to
avoid this.
I use heaps to sort lists. One time sorts work quite well.
If you think I have misspoken anywhere, please feel free to point it
up. We're all here to learn. Right?
___ Blue Wave/QWK v2.12
--- Maximus/2 3.01
---------------