Max Heap

max_heap.cpp

#include <iostream>
#include <vector>

using namespace std;

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

    bool enqueue(int value);
    int dequeue();
    void swap(int &a, int &b);
    void print();

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

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

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

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

  for (; parent != 0; parent /= 2) {
    if (priority_queue[parent] < priority_queue[index]) {
      swap(priority_queue[parent], priority_queue[index]);
      index = parent;
    }
  }

  return true;
}

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

  // switch the value of first and last value of the queue.
  priority_queue[1] = priority_queue.back();
  priority_queue.pop_back();

  // Adjust the heap.
  int index = 1;
  int child = index * 2; 

  for (; child < priority_queue.size(); child *= 2) {
    int max = priority_queue[child] > priority_queue[child+1] ? child : child + 1;
    if (priority_queue[max] > priority_queue[index]) {
      swap(priority_queue[max], priority_queue[index]);
      index = max;
    }
  }

  return min_value;
}

void MaxHeap::swap(int &a, int &b)
{
  a ^= b;
  b ^= a;
  a ^= b;
}

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

int main(int argc, char* argv[])
{
  MaxHeap max_heap;
  for (int i=1; i<=10; i++) {
    max_heap.enqueue(i);
  }
  max_heap.print();

  for (int i=5; i>0; i--) {
    max_heap.dequeue();
    max_heap.print();
  }
  return 0;
}