Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#include <vector>
#include <iostream>
// Implementation of a priority queue using a binary heap where the
// binary heap is stored using a vector. The heap stores the minimal
// element at the top, which makes it a min-heap.
// This is sample class for the HiredInTech.com tutorials.
class PriorityQueue {
public:
PriorityQueue() {}
PriorityQueue(unsigned max_size) {
// If we know how big the heap will grow we could
// resize the vector we use to optimize its performance.
heap.resize(max_size);
}
unsigned size() const {
return heap.size();
}
void insert(int value) {
// Add the new value at the end of the tree, which is
// the first free cell in the vector.
heap.push_back(value);
// Start bubbling up the node if it has a lower value
// then its current parent node.
unsigned node_idx = heap.size() - 1;
// While the node has not reached the root of the tree
while(node_idx > 0) {
// Get the index of the parent node
unsigned parent_idx = (node_idx - 1) / 2;
// Check if the current parent has a greater value.
// If so, swap the nodes. Otherwise, stop here.
if (heap[node_idx] < heap[parent_idx]) {
swap_nodes(node_idx, parent_idx);
node_idx = parent_idx;
} else {
break;
}
}
}
int get_minimum() const {
// The element at position 0 contains the root node's value.
return heap[0];
}
int pop() {
// Store the root value to return it in the end
int result = heap[0];
// If the heap has only one element just pop it and return
if (heap.size() == 1) {
heap.pop_back();
return result;
}
// Move the last node to the root
heap[0] = heap.back();
// Remove the vector cell corresponding to the last node
heap.pop_back();
// Start bubbling down the node we put at the root
unsigned node_idx = 0;
// While the current node has at least one child node,
// check if they must be swapped
while (2 * node_idx + 1 < heap.size()) {
int min_child_idx = 2 * node_idx + 1;
int min_child_value = heap[min_child_idx];
// If there is a right child check if it has a smaller value
// than its left sibling.
if (min_child_idx + 1 < heap.size() && heap[min_child_idx + 1] < min_child_value) {
min_child_idx++;
min_child_value = heap[min_child_idx];
}
// Check if the current node has a child with a smaller value.
// If so, swap them. Otherwise, stop iterating down the tree.
if (min_child_value < heap[node_idx]) {
swap_nodes(min_child_idx, node_idx);
node_idx = min_child_idx;
} else {
break;
}
}
return result;
}
private:
// We will use a vector to represent the heap. A plain array
// could also be used here but we will have to know how much
// memory to allocate for it, which will limit the maximum
// size the heap could have.
std::vector<int> heap;
// A helper method to swap two nodes in the binary heap.
void swap_nodes(int idx1, int idx2) {
int tmp = heap[idx1];
heap[idx1] = heap[idx2];
heap[idx2] = tmp;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment