From: terje.mathisen@nospicedham.tmsw.no   
      
   James Van Buskirk wrote:   
   > "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.   
      
   You are right, with the reversed order he automatically get that 90%   
   discard rate for free, so past that point of optimization all the   
   numbers are so small that it really doesn't matter:   
      
   It is simply an O(1) algorithm for each new element, just with slightly   
   different constant factors.   
   >   
   > 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.   
   >   
   This is probably the msot important consideration. :-)   
      
   Terje   
      
   --   
   -    
   "almost all programming can be viewed as an exercise in caching"   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)