TH>Consider the merge or quick sort algorithms: These are examples of
TH>O(NlogN) because they belong to the "divide and conqure" genere.
TH>You stare with an (supposedly) unsorted list, and you sort it.
TH>Heaps are also NlogN, but the sorting is distributed such that the
TH>total time is missleading.
DM>I think it is quite accurate to call it NlgN since that is the
DM>time required to create the heap, irrespective of the
DM>creation/loading of the data. If you ignore the *total* time, you
DM>become misleading when comparing sorts: lgN looks much faster than
DM>quicksort's NlgN, when, in fact, it often isn't any faster in
DM>actual practice.
Darin, comparing big 'O' *can* in itself be misleading. Sure, appear
to be the same, but try using quick sort in a priority queue, or try
referencing the 'Nth' element in a heap.
Clearly, some algorithems have distinct advantages over others, and
it is the programmers judgment to select the one best suited for the
job. Heaps are faster because the sort as you go. The min/max value
is available in O(lnN). Quick sorts and merge sorts require much
longer to sort results, but don't have the front end overhead.
DM>We were talking about sorts which imply N elements. When you
DM>change the topic to "adding single elements", yes, it becomes
DM>O(lgN).
Darrin, if you will review my past posts, that *was* the discussion.
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]
DM>Yayayaya... I was confusing binary trees with heaps. My mistake.
Don't let it happen again. You have now used up your quota of one
mistake per year. [grin]
DM>I still get these wrong once in a while, which is why I like to
DM>ensure everything is made explicit. :-) Thankfully, C++ (desperate
DM>attempt to remind everyone of the topic ) has the standard
DM>template library that does all of this for me.
Template? Template! TEMPLATE!!!... We don't need no stinkin' Template!
[grin]
DM>I just need to plug in the right template to my typedef for the
DM>performances that I want (fast access? fast sort? fast insert?
DM>sorted at all? ...) and away I go. :-)
You forgot paper or plastic... [grin]
Ah,... I'm gettin crazy, here.
___ Blue Wave/QWK v2.12
--- Maximus/2 3.01
---------------