DM>Tim, this *IS* N*lgN. After all, you need to make lgN compares for
DM>each of N elements...
 TH> First, I was refering only to the insertion/poping of a single
 TH> element. What you seem to be describing is "N * O(NlogN)", meaning "N
 TH> * O(log2(N))", and that's okay, *if* you are refering to the total
 TH> time. Of course heaps have a special advantage in that they are
 TH> sorted as insertions are made. Thus, you don't "sort" a heap, they
 TH> just always provide the desired (min/max) value.
 TH> Consider the merge or quick sort algorithms: These are examples of
 TH> O(NlogN) because they belong to the "divide and conqure" genere. You
 TH> stare with an (supposedly) unsorted list, and you sort it. Heaps are
 TH> also NlogN, but the sorting is distributed such that the total time
 TH> is missleading.
I think it is quite accurate to call it NlgN since that is the time required 
to create the heap, irrespective of the creation/loading of the data.  If you 
ignore the *total* time, you become misleading when comparing sorts: lgN 
looks much faster than quicksort's NlgN, when, in fact, it often isn't any 
faster in actual practice.
 TH> I don't think Big(O) considers the sum of the elements, since any 'N'
 TH> before the O makes it common in the analysis. Thus, they should be
 TH> factored out. After all, there are some O(1) functions, for example.
Yes, but they aren't sorting since sorting, by its nature, needs to involve 
at least N elements.  :-)  O(1) functions are only things such as finding an 
element in a vector.  However, the desired output is a single element - 
obviously when you want to find M elements, it becomes O(M).
We were talking about sorts which imply N elements.  When you change the 
topic to "adding single elements", yes, it becomes O(lgN).  This is 
misleading when comparing against other sorts, but does imply a capability 
that other sorts do not have (adding single elements on the fly at relatively 
low cost).  I know that when I was first introduced to sorting, as I'm sure 
some of our readers are doing right now, I'd have been confused by your 
comparison without making the difference quite explicit.
 TH> That don't make sense, Darin. Heaps are generally unsorted as you
 TH> described. That is, heaps are usually implemented in an array, and
 TH> viewed in liniar manner appear to be unsorted. But it is orgainzed
 TH> such that the desired element can be accessed. An unsorted heap is
 TH> kind of redundant repeats. [grin]
Yayayaya... I was confusing binary trees with heaps.  My mistake.  I still 
get these wrong once in a while, which is why I like to ensure everything is 
made explicit.  :-)  Thankfully, C++ (desperate attempt to remind everyone of 
the topic ) has the standard template library that does all of this for 
me.  I just need to plug in the right template to my typedef for the 
performances that I want (fast access?  fast sort?  fast insert?  sorted at 
all? ...) and away I go.  :-)
---
---------------