Priority queues

Binary heap with recursive implementation

The priority queue is maintained as a heap in a dynamic vector. A heap is a complete binary tree with the property that the value at every node is smaller or equal than the values at the nodes of its subtrees. A heap for n elements is easily implemented in positions $1$ to $n$. An element at position $i$ with $1 \le i \le n$ has its left child at position $2i$ if $2i \le n$, its right child at position $2i+1$ if $2i+1 \leq n$, and its parent at position $\lceil i/2\rceil$ if $i > 1$. For convenience, the vector includes a position that is numbered 0 and is not used.

Below, $n$ denotes the size of the priority queue. For the analysis, it is assumed that extending a vector by a new element added at the end has constant cost (this is not quite true: it is constant amortized cost).

#include <cassert>
#include <vector>
using namespace std;


template <typename T>
class PriorityQueue {

private:

    /** Vector for the heap (position 0 is not used). */
    vector<T> v;

public:

    /** Creates an empty priority queue. Cost: O(1). */
    PriorityQueue ()
    :   v(1)                // position 0 is not used
    {   }

    /** Inserts a new element in the priority queue. Cost: O(log n). */
    void insert (const T& x) {
        v.push_back(x);
        shift_up(size());
    }

    /** Removes the minimum element from the priority queue. Cost: O(log n). */
    void remove_min () {
        assert(not empty());
        v[1] = v.back();
        v.pop_back();
        shift_down(1);
    }

    /** Returns the minimum element in the priority queue. Cost: O(1). */
    T minimum () {
        assert(not empty());
        return v[1];
    }

    /** Returns the size of the priority queue. Cost: O(1). */
    int size () {
        return v.size() - 1;
    }

    /** Indicates if the priority queue is empty. Cost: O(1). */
    bool empty () {
        return size() == 0;
    }

private:

    /** Shift node i up in the heap, as long as needed. */
    void shift_up (int i) {
        if (i != 1 and v[i/2] > v[i]) {
            swap(v[i], v[i/2]);
            shift_up(i/2);
    }   }

    /** Shift down node i in the heap, as long as needed. */
    void shift_down (int i) {
        const int n = size();
        int c = 2*i;
        if (c <= n) {
            if (c+1 <= n and v[c+1] < v[c]) c++;
            if (v[i] > v[c]) {
                swap(v[i],v[c]);
                shift_down(c);
    }   }   }

};

Binary heap with iterative implementation

Same as the previous version but with iterative implementation.

#include <cassert>
#include <vector>
using namespace std;


template <typename T>
class PriorityQueue {

private:

    /** Vector for the heap (position 0 is not used). */
    vector<T> v;

public:

    /** Creates an empty priority queue. Cost: O(1). */
    PriorityQueue ()
    :   v(1)                // position 0 is not used
    {   }

    /** Inserts a new element in the priority queue. Cost: O(log n). */
    void insert (const T& x) {
        v.push_back(x);
        int i = size();
        while (i != 1 and v[i/2] > x) {
            v[i] = v[i/2];
            i = i/2;
        }
        v[i] = x;
    }

    /** Removes the minimum element from the priority queue. Cost: O(log n). */
    void remove_min () {
        assert(not empty());
        int n = size();
        const T x = v[n];
        v.pop_back();
        --n;
        int i = 1, c = 2*i;
        while (c <= n) {
            if (c+1 <= n and v[c+1] < v[c]) ++c;
            if (x <= v[c]) break;                   // this break is nice!
            v[i] = v[c];
            i = c;
            c = 2*i;
        }
        v[i] = x;
    }

    /** Returns the minimum element from the priority queue. Cost: O(1). */
    T minimum () {
        assert(not empty());
        return v[1];
    }

    /** Returns the size of the priority queue. Cost: O(1). */
    int size () {
        return v.size() - 1;
    }

    /** Indicates if the queue is empty. Cost: O(1). */
    bool empty () {
        return size() == 0;
    }

};

Example

This example reads a sequence of integers and prints them back in increasing order using a priority queue.

#include <iostream>
#include "priority-queue-ite.cc"
using namespace std;

int main() {
    PriorityQueue<int> s;
    int x;
    while (cin >> x) {
        s.insert(x);
    }
    while (not s.empty()) {
        cout << s.minimum() << endl;
        s.remove_min();
    }
}

Lliçons.jutge.org
Jordi Petit
Universitat Politècnica de Catalunya, 2023