# 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

Prohibit copiar. Tots els drets reservats.