priority_queue.cpp

#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;
    }
};