home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / programm / 3630 < prev    next >
Encoding:
Text File  |  1993-01-28  |  1.5 KB  |  34 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!UB.com!pacbell.com!decwrl!concert!gatech!rpi!batcomputer!munnari.oz.au!manuel.anu.edu.au!csc.canberra.edu.au!fir!eyal
  3. From: eyal@fir.canberra.edu.au (Eyal Lebedinsky)
  4. Subject: Re: is it possible to find max & next smallest in one pass?
  5. Message-ID: <eyal.728121809@fir>
  6. Sender: news@csc.canberra.edu.au
  7. Organization: Info Sci & Eng, University of Canberra, AUSTRALIA
  8. References: <1993Jan25.224200.7195@bnlux1.bnl.gov>
  9. Date: 27 Jan 93 08:03:29 GMT
  10. Lines: 22
  11.  
  12. In <1993Jan25.224200.7195@bnlux1.bnl.gov> murphy@sscdaq.phy.bnl.gov (Michael Murphy) writes:
  13.  
  14.  
  15. >>jos@and.nl (Jos Horsmeier) writes:
  16.  
  17. >>>In article <asean.727858796@armstrong.ecn.purdue.edu> asean@armstrong.ecn.purdue.edu (Sean Ahern) writes:
  18. >>>|jagrant@emr1.emr.ca (John Grant) writes:
  19. >>>|>Given an array of values, is it possible to find the maximum of
  20. >>>|>the array and the next smallest value in a single pass?  The reason
  21. >>>|>I want it in one pass, is that the array is actually a data file
  22. >>>|>of a million float values.
  23.  
  24. Well, the usual way of finding the highest-n in a list is to simply
  25. create a priority queue. This data structure is cheap to maintain and
  26. most alg books give a reasonable description of it.
  27.  
  28. For just the top two (max and next-smallest) it boils down to a simple
  29. test while keeping the so-far best and next. Insted of just doing 'if
  30. x[] > max then max = x[]' you also check to see if it second best (if it
  31. is best then the old best is now second-best).
  32.  
  33. Then again, I may have missed the point of the question.
  34.