home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / programm / 3581 < prev    next >
Encoding:
Text File  |  1993-01-25  |  2.0 KB  |  42 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!paladin.american.edu!howland.reston.ans.net!sol.ctr.columbia.edu!ira.uka.de!slsvaat!us-es.sel.de!reindorf
  3. From: reindorf@us-es.sel.de (Charles Reindorf)
  4. Subject: Re: is it possible to find max & next smallest in one pass?
  5. Message-ID: <1993Jan25.100031.29146@us-es.sel.de>
  6. Sender: news@us-es.sel.de
  7. Organization: SEL-Alcatel Line Transmission Systems Dept. US/ES
  8. References:  <1993Jan24.040702.6193@emr1.emr.ca> <1993Jan25.085026.28282@us-es.sel.de> <1993Jan25.085924.28427@us-es.sel.de>
  9. Date: Mon, 25 Jan 93 10:00:31 GMT
  10. Lines: 30
  11.  
  12.  In article <1993Jan24.040702.6193@emr1.emr.ca>, jagrant@emr1.emr.ca (John Grant) writes:
  13. |> Given an array of values, is it possible to find the maximum of
  14. |> the array and the next smallest value in a single pass?  The reason
  15. |> I want it in one pass, is that the array is actually a data file
  16. |> of a million float values.
  17. |> 
  18. |> If so, I guess the same single pass could also find the min and next
  19. |> highest value too?
  20. |> 
  21. |> -- 
  22. |> John A. Grant                        jagrant@emr1.emr.ca
  23. |> Airborne Geophysics
  24. |> Geological Survey of Canada, Ottawa
  25.  
  26. I don't know what context you with to implement your algorithm here. If you are simply
  27. interested in getting the highest value out, then it is surely a simple O(n) operations
  28. performed by a linear search and discussed in detail in the responses seen so far on the
  29. net.
  30.  
  31. However, there is a method of storing a list of numbers in an array in memory as what is
  32. called a "heap" (not like the usual memory heap). Maintaining your data in such a heap,
  33. you can store new values in O(log n) cycles and *extract* the highest value (at the same 
  34. time re-organising the heap) in O(log n) cycles too. The data is still maintained in a
  35. linear array on disc or in memory and so there is no fragmentation. I am sure a description
  36. is available in Knuth, but I got it out of a Prentice&Hall book (I think) called (something
  37. like) "Data Structures and Program Design". Just a guess, but maybe this structure would be
  38. useful to you.
  39.  
  40.  
  41. --- Charles Reindorf
  42.