From: not_valid@nospicedham.comcast.net   
      
   "Terje Mathisen"  wrote in message news:okoeol$ikv$1@gioia.aioe.org...   
      
   > OK, let's go through it:   
      
   > A priority queue is perfect if you have to be prepared to spit out an   
   > ordered list any any point in time, it carries a cost of O(log(n)) for   
   > both insertions and deletions (with n = 40 here, so the log(n) term will   
   > be ~6) for most operations.   
      
   > Unless you also maintain a separate #40 marker, i.e. the current cutoff   
   > point, you will carry that log(40) cost for all new records, _including_   
   > all those that fall outside the top 40 range!   
      
   > I.e. the naive version will blindly insert the new record and then   
   > delete the current #41 to bring the total back to 40.   
      
   > If the total count is large (i.e. >= 400) at least 90% of all new   
   > records will be discarded immediately at O(1) cost as long as you have   
   > that cutoff point available. At that point the difference between a   
   > O(log(n)) and a O(n) algorithm is a fixed number (6/(40*0.5) =~ 3).   
      
   Going back to Robert Wessel's post, he suggests building the N=40   
   heap in reverse sort order so that the current #40 will lie on top of   
   the heap.  Then each new element need only be compared with the   
   heap top, and for random data the new element will be discarded   
   at no further cost all but roughly N*ln(M/N) times.   
      
   If the new element is better than the current #40, it gets inserted   
   by replacing the top of heap element followed by a percolate down   
   to restore the heap condition. A heap of size N=40 may require up   
   to 10 comparisons to percolate down compared to an average of   
   20 data movements for a sorted array.  If he ever wants to get   
   bigger N, it will be easy to stick with the heap.  Besides, O.P. said   
   he already has efficient heapsort code at hand, so he has very   
   little work involved in adapting it to the operations required to   
   build, maintain, and read out the heap.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)