priority queue with limited space: looking for a good algorithm

by

Array based heaps seem ideal for your purpose. I am not sure why you rejected them.

You use a max-heap.

Say you have an N element heap (implemented as an array) which contains the N smallest elements seen so far.

When an element comes in you check against the max (O(1) time), and reject if it is greater.

If the value coming in is lower, you modify the root to be the new value and sift-down this changed value – worst case O(log N) time.

The sift-down process is simple: Starting at root, at each step you exchange this value with it’s larger child until the max-heap property is restored.

So, you will not have to do any deletes which you probably will have to, if you use std::priority_queue. Depending on the implementation of std::priority_queue, this could cause memory allocation/deallocation.

So you can have the code as follows:

  • Allocated Array of size N.
  • Fill it up with the first N elements you see.
  • heapify (you should find this in standard text books, it uses sift-down). This is O(N).
  • Now any new element you get, you either reject it in O(1) time or insert by sifting-down in worst case O(logN) time.

On an average, though, you probably will not have to sift-down the new value all the way down and might get better than O(logn) average insert time (though I haven’t tried proving it).

You only allocate size N array once and any insertion is done by exchanging elements of the array, so there is no dynamic memory allocation after that.

Check out the wiki page which has pseudo code for heapify and sift-down: http://en.wikipedia.org/wiki/Heapsort

More Related Contents:

  1. Mixing two arrays by alternating elements two by two
  2. How to find out how many bits are set (equal 1) in the product of two integers [closed]
  3. banker’s algorithm in c++
  4. What is the difference between palindrome permutation and permutation? [closed]
  5. How to replace all occurrences of a character in string?
  6. Image Processing: Algorithm Improvement for ‘Coca-Cola Can’ Recognition
  7. Sorting zipped (locked) containers in C++ using boost or the STL
  8. std::transform() and toupper(), no matching function
  9. C++ string::find complexity
  10. The reason of using `std::greater` for creating min heap via `priority_queue`
  11. C++ Efficiently Calculating a Running Median [duplicate]
  12. Special simple random number generator
  13. Finding nearest point in an efficient way
  14. Fast n choose k mod p for large n?
  15. TMP: how to generalize a Cartesian Product of Vectors?
  16. How can std::make_heap be implemented while making at most 3N comparisons?
  17. Writing a simple equation parser
  18. What is the right approach when using STL container for median calculation?
  19. Howto create combinations of several vectors without hardcoding loops in C++?
  20. Inverting a 4×4 matrix
  21. Print 2-D Array in clockwise expanding spiral from center
  22. std::back_inserter for a std::set?
  23. How to rotate a N x N matrix by 90 degrees? [closed]
  24. Ways to do modulo multiplication with primitive types
  25. Removing ‘#include ‘ doesn’t break the code
  26. Why there is no std::copy_if algorithm?
  27. LRU implementation in production code
  28. Is it possible to implement lock free map in C++
  29. Calculate mean and standard deviation from a vector of samples in C++ using Boost
  30. Checking if all elements of a vector are equal in C++

Leave a Comment