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.
TH>Yep. A heap does *not* access every element - that is per insertion.
TH>O(logN) is a tell tail sign of a binary tree, and that is what a heap
TH>is. However, a heap is usually implemented as an array for efficiency.
TH>So, when an insertion takes place, the comparison of the insertion
TH>key starts at the end of the array, and in binary fashion trickles
TH>to the top. Each level up halves the posibilities. So, say, 255
TH>elements has only seven accesses at most to make. It made only
TH>need to make one access. This is called reheaping.
DM>Tim, this *IS* N*lgN. After all, you need to make lgN compares for
DM>each of N elements...
Hi Darin;
First, I was refering only to the insertion/poping of a single
element. What you seem to be describing is "N * O(NlogN)", meaning "N
* O(log2(N))", and that's okay, *if* you are refering to the total
time. Of course heaps have a special advantage in that they are
sorted as insertions are made. Thus, you don't "sort" a heap, they
just always provide the desired (min/max) value.
Consider the merge or quick sort algorithms: These are examples of
O(NlogN) because they belong to the "divide and conqure" genere. You
stare with an (supposedly) unsorted list, and you sort it. Heaps are
also NlogN, but the sorting is distributed such that the total time
is missleading.
I don't think Big(O) considers the sum of the elements, since any 'N'
before the O makes it common in the analysis. Thus, they should be
factored out. After all, there are some O(1) functions, for example.
TH>When the highest or lowest (depending on whether it is a MAX-heap,
TH>or a MIN-heap) element is popped off. A reheap is also required.
TH>That, too, is O(logN).... Hmmm. come to think of it, maybe I
TH>should have said O(2logN) since it is does get reheaped twice,
TH>once going in and again comming out.
DM>One aspect of O-notation is that there isn't any constants...
I seem to recall seeing some examples, and I used one of them in an
above example. I have a handout that illustrates several different
notations. I tried to look for it - and Murphy was right again - I
can't find it when I need it.
DM>that's still "O(logN)" (and still wrong - you need to take N off
DM>the heap as well, so it's O(N*logN))
Yes, for the whole, but I refering to a single insertion time.
DM>For priority trees, one item that I saw that seemed faster was an
DM>unsorted heap - where a node was guaranteed only to be higher than
DM>its leaves, but the order of the leaves were unimportant. This
DM>reduces the constant, but does not (IIRC) change the order of the
DM>algorithm.
That don't make sense, Darin. Heaps are generally unsorted as you
described. That is, heaps are usually implemented in an array, and
viewed in liniar manner appear to be unsorted. But it is orgainzed
such that the desired element can be accessed. An unsorted heap is
kind of redundant repeats. [grin]
I have written code for both a min and a max heap. Each include file
are maybe 50 lines long, I'd be happy to post one of them to
illustrate what I am talking about.
cheers...
--- Maximus/2 3.01
---------------