Priority queue

TPIE provides a very efficient external memory priority queue based off Sanders, Fast Priority Queues for Cached Memory.

It is implemented in the file priority_queue.h and exists in the tpie::ami namespace.

It is conceptually compatible with std::priority_queue, except it operates by default as a min-heap rather than a max-heap, as is common in research literature.

One may push() and pop() elements, and top() will always return the least element pushed that has not yet been popped. size() will return the number of elements pushed that have not been popped, and empty() returns size() == 0.

You must set a memory limit for the memory manager using tpie::memory_manager::set_limit() before using the priority queue, as its initialization depends on knowing how much memory is available.

Example pq.cpp:

#include <tpie/priority_queue.h> // for tpie::priority_queue
#include <tpie/tpie_assert.h> // for tp_assert macro
#include <tpie/tpie.h> // for tpie_init
void pq_test() {
    tpie::priority_queue<int> pq;
    for (int i = 10; i > 0; --i) {
        pq.push(i);
    }
    tp_assert(pq.size() == 10, "Incorrect size");
    for (int i = 1; i <= 10; ++i) {
        tp_assert(pq.top() == i, "Incorrect element");
        pq.pop();
    }
    tp_assert(pq.empty(), "Incorrect size");
}
int main() {
    tpie::tpie_init();
    tpie::get_memory_manager().set_limit(1<<30);
    pq_test();
    tpie::tpie_finish();
    return 0;
}

The above code initializes TPIE, sets the memory limit to 1 GB, initializes a priority queue, pushes 10 elements onto it, verifies that they are returned in the correct order.

Place the code file in your tpie project folder, and on Linux, compile with:

$ g++ -I. -Ibuild -c pq.cpp -Wall -Wextra -O3
$ g++ pq.o -o pq build/tpie/libtpie.a -lboost_thread-mt -lboost_filesystem-mt -lboost_system-mt