a bit of data structure: Binary Heap

In my opinion, Binary Heap is one of the most ingenious data structure in the sense that its implementation can be done on a static 1D array, albeit its nature of being a dynamic non-linear data structure.

Binary Heap maintains the property that the parent node has a key less its children (if it has any). Each node has 2 child at most, a left child and a right child. The relationship between parent node and child node can be laid down on an array of size N, where index \( 1 \leq i \leq N\) represent a node in the Binary Heap. Furthermore, left child of \(i\) is placed at index \(2i\) while right child is placed at \(2i + 1\). Under this relationship, an array that maintain these properties will form a full binary tree representing the heap.

Insertion is done by appending the new element at the ending entry of the array, and a procedure called Up-Heapify is called. It recursively check whether the parent of the new element is greater than itself, and if it is, they swap places. If the root is reached, or the parent is already less than itself, the procedure terminates.

Erasing the top element is done by swapping the top element with the last entry of the array, and a procedure called Down-Heapify is called. It recursively check whether the children of the new element is less than itself, and if so, it swaps place with the lowest of the two.

Binary Heap is used for the implementation of Priority Queue, and other algorithms that require keeping track of the lowest/highest element in a collection.

Here is a simple implementation of Min-Heap which places the minimum element on top of the heap throughout.

//Implementation of Min-Binary Heap
//Support: Insert, Pop, Top
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

class MinHeap
{
 private:
  typedef int pos;
  static const pos NIL = 0;
  int max_size; //max size of array
  pos last;  //position of last element
  int *minheap; //pointer to an array
  //MinHeap Construction Algorithm
  void upheap(pos x);
  void downheap(pos x);
  pos left_child(pos x);
  pos right_child(pos x);
  pos parent(pos x);
  void heapswap(pos x, pos y);
 public:
  MinHeap(int sz): max_size(sz), minheap(new int[sz+1]), last(NIL){}
  
  ~MinHeap()
  {
   delete[] minheap;
  }

  void push(int m);
  void pop();
  int top();
  bool empty();
  void to_string();
};

MinHeap::pos MinHeap::left_child(pos x)
{
 if(2*x > last)
  return NIL;

 return 2*x;
}

MinHeap::pos MinHeap::right_child(pos x)
{
 if(2*x + 1 > last)
  return NIL;

 return 2*x + 1;
}

MinHeap::pos MinHeap::parent(pos x)
{
 if(x == 1)
  return NIL;

 return x/2;
}

void MinHeap::heapswap(pos x, pos y)
{
 int temp = minheap[x];
 minheap[x] = minheap[y];
 minheap[y] = temp;
}

void MinHeap::upheap(pos x)
{
 pos par = parent(x);
 while (par != NIL && minheap[par] > minheap[x])
 {
  heapswap(x,par);
  x = parent(x);
 }
}

void MinHeap::downheap(pos x)
{
 pos next = x;
 pos left = left_child(x);
 pos right = right_child(x);
 if(left != NIL && minheap[left] < minheap[next])
  next = left;
 if(right != NIL && minheap[right] < minheap[next])
  next = right;
 if(next == x) return;
 heapswap(x, next);
 downheap(next);
}

//Function definitions
void MinHeap::push(int m)
{
 if(last+1 > max_size)
 {
  printf("MinHeap is already full, insertion is aborted\n");
  return;
 }
 ++last;
 minheap[last] = m;
 upheap(last);
}

int MinHeap::top()
{
 if(last < 1)
 {
  printf("MinHeap is empty\n");
  return NIL;
 }
 return minheap[1];
}

void MinHeap::pop()
{
 if(empty())
  return;
 minheap[1] = minheap[last];
 --last;
 downheap(1);
}

void MinHeap::to_string()
{
 for(pos it = 1; it <= last; ++it)
 {
  printf("%d ", minheap[it]);
 }
 printf("\n");
}

bool MinHeap::empty()
{
 if(last == NIL)
  return true;

 return false;
}

int main()
{
 /**
  * TEST BODY
  * 3 Commands: Push, Pop, and Top
  */

 printf(":::::::::::MinHeap:::::::::::\n 2014 - Prajogo Tio \n Simple Implementation of MinHeap\n\n");
 printf("Enter the intended size of the MinHeap: ");
 int max_sz;
 cin >> max_sz;
 MinHeap myHeap(max_sz);
 printf("Command:\n");
 printf("1. push <number>\n2. top\n3. pop\n4. quit\n\n");
 string cmd;
 int num;
 while(printf("Key in your command: \n"), cin >> cmd)
 {
  if( cmd == "quit")
  {
   printf("Program is terminating. See you again.\n\n");
   break;
  }

  if( cmd == "push")
  {
   cin >> num;
   myHeap.push(num);
   cout << num << " has been pushed to the heap\n\n";
  }
  else if( cmd == "pop")
  {
   myHeap.pop();
   cout << "Top element has been removed\n\n";
  }
  else if( cmd == "top")
  {
   if(myHeap.empty()) 
   {
    cout << "MinHeap is empty\n\n";
   } else {
    cout << "Top element: " << myHeap.top() << endl << endl;
   }
  }

 }

 return 0;
}