Min Heap

min_heap.cpp

#include <iostream>
#include <vector>

using namespace std;

class MinHeap
{
  public:
    MinHeap() : size(100) { priority_queue.push_back(-1); };
    ~MinHeap() {};

    bool enqueue(int value);
    int dequeue();

    void print();

  protected:
    vector<int> priority_queue;
    unsigned int size;
};

bool MinHeap::enqueue(int value)
{
  if (priority_queue.size() >= size) {
    cout << "Queue is full!" << endl;
    return false;
  }

  // Append the value to the end of queue.
  priority_queue.push_back(value);

  // Adjust heap structure.
  int index = priority_queue.size() - 1;
  int parent = index / 2;

  for (; parent > 0; parent /= 2) {
    if (priority_queue[parent] > priority_queue[index]) {
      int temp = priority_queue[parent];
      priority_queue[parent] = priority_queue[index];
      priority_queue[index] = temp;
      index = parent;
    }
  }

  return true;
}

int MinHeap::dequeue()
{
  if (priority_queue.size() == 1) {
    cout << "Queue is empty!" << endl;
    return -1;
  }

  int min_value = priority_queue[1];
  int new_root = priority_queue.back();
  priority_queue.pop_back();

  // Put the last item to the first.
  int index = 1;
  int child = index * 2;
  priority_queue[index] = new_root;

  // Adjust the heap.
  for (; child < priority_queue.size(); child *= 2) {
    bool adjust = false;
    int min = priority_queue[child] < priority_queue[child+1] ? child : child + 1;

    if (priority_queue[min] < priority_queue[index]) {
      int temp = priority_queue[min];
      priority_queue[min] = priority_queue[index];
      priority_queue[index] = temp;
      index = min;
    }
  }

  return min_value;
}

void MinHeap::print()
{
  for (vector<int>::iterator it=priority_queue.begin();
       it!=priority_queue.end(); ++it) {
    cout << *it << ' ' << endl;
  }
}

int main(int argc, char* argv[])
{
  MinHeap min_heap;
  min_heap.enqueue(10);
  min_heap.enqueue(8);
  min_heap.enqueue(9);
  min_heap.enqueue(5);
  min_heap.enqueue(4);
  min_heap.enqueue(3);

  min_heap.print();

  // Dequeue some values
  cout << "First dequeue ";
  cout << "min value: " << min_heap.dequeue() << endl;
  min_heap.print();

  cout << "Second dequeue ";
  cout << "min value: " << min_heap.dequeue() << endl;
  min_heap.print();

  cout << "Thrid dequeue ";
  cout << "min value: " << min_heap.dequeue() << endl;
  min_heap.print();

  cout << "Forth dequeue ";
  cout << "min value: " << min_heap.dequeue() << endl;
  min_heap.print();

  cout << "Fifth dequeue ";
  cout << "min value: " << min_heap.dequeue() << endl;
  min_heap.print();

  cout << "Sixth dequeue ";
  cout << "min value: " << min_heap.dequeue() << endl;
  min_heap.print();

  cout << "Seventh dequeue ";
  min_heap.dequeue();
  min_heap.print();

  return 0;
}