C++ Priority Queue Implementation: Code & Explanation

C++ Priority Queue Implementation

This document provides a C++ implementation of a priority queue using a heap data structure. The code includes the class definition, member functions, and supporting utilities.

Priority Queue Class Definition

#ifndef priority_queue_h_
#define priority_queue_h_

#include <iostream>
#include <vector>
#include <cassert>

template <class T>
class priority_queue {
private:
    std::vector<T> m_heap;

public:
    priority_queue() {}

    priority_queue(std::vector<T> const& values)
    {
        m_heap = values;
        for (int i = 0; i < m_heap.size(); i++){
            percolate_down(i);
            for (int j = i; j < m_heap.size(); j++){
                percolate_down(j);
            }
        }
    }

    const T& top() const
    {
        assert(!m_heap.empty());
        return m_heap[0];
    }

    void push(const T& entry)
    {
        if (m_heap.size() == 0){
            m_heap.push_back(entry);
            return;
        }
        m_heap.push_back(entry);
        percolate_up(m_heap.size() - 1);
    }

    void pop()
    {
        T val = m_heap[m_heap.size() - 1];
        m_heap.pop_back();
        m_heap[0] = val;
        percolate_down(0);
    }

    void percolate_up(int i){
        while (i > 0){
            if (m_heap[i] < m_heap[(i - 1) / 2]){
                swap((i - 1) / 2, i);
                i = (i - 1) / 2;
            }
            else{
                break;
            }
        }
    }

    void percolate_down(int i){
        while ((2 * i + 1) < m_heap.size()){
            int child;
            if (2 * i + 2 < m_heap.size() && m_heap[2 * i + 2] < m_heap[2 * i + 1]){
                child = 2 * i + 2;
            }
            else{
                child = 2 * i + 1;
            }
            if (m_heap[child] < m_heap[i]){
                swap(i, child);
                i = child;
                std::cout << "\n";
            }
            else{
                break;
            }
        }
    }
    int size() { return m_heap.size(); }
    bool empty() { return m_heap.empty(); }


    //  The following three functions are used for debugging.
    //  Check to see that internally the heap property is realized.
    bool check_heap()
    {
        return this->check_heap(this->m_heap);
    }
    void swap(int i, int j){
        T val = m_heap[j];
        m_heap[j] = m_heap[i];
        m_heap[i] = val;
    }

    //  Check an external vector to see that the heap property is realized.
    bool check_heap(const std::vector<T>& heap)
    {
        if (heap.size() == 0){
            return true;
        }
        for (int i = 0; i < heap.size() / 2; i++){
            if (heap[i] > heap[2 * i + 1] || heap[i] > heap[2 * i + 2]){
                return false;
            }
        }
        return true;
    }

    //  A utility to print the contents of the heap.  Use it for debugging.
    void print_heap(std::ostream & ostr)
    {
        for (unsigned int i = 0; i<m_heap.size(); ++i)
            ostr << i << ": " << m_heap[i] << std::endl;
    }

};

template <class T>
void heap_sort(std::vector<T> & v)
{
    //v_ = std::vector<T>(v);
    priority_queue<T> pq_v(v);
    for (int i = 0; i < v.size(); i++){
        T temp = pq_v.top();
        v[i] = temp;
        pq_v.pop();
    }


}
#endif

Usage Example: Heap Sort

The code also includes a heap_sort function that utilizes the priority queue to sort a vector.