Heap

heap.cpp

#include<iostream>
#include<vector>
using namespace std;

class Heap
{
  vector<int> array;
  
public:
  Heap() {}
  void insert(int x);
  int delete_min();
  void print();
};

void Heap::insert(int x)
{
  int next = array.size();
  // Insert at the end and then we can bubble up
  array.push_back(x);
  
  /* As long as next is not pointing to the first
     position and x is less than next's parent, keep
     copying the element at next's parent position 
     to the position next. At the end of the loop, we
     will be at the correct position to insert the new
     value
  */
  while (next > 0 && x < array[(next - 1)/2])
  {
    array[next] = array[(next - 1)/2];
    next = (next - 1)/2;
  }
  // Now that we are at the correct position, insert x there.
  array[next] = x;
}
int Heap::delete_min()
{
  /* If the heap is empty indicate that with an error code.
    If -1 is actually an element in the heap, there might be
    some confusion in handling the return value. But this is 
    not a problem here since we don't do anything with the return value.
  */
  
  if (array.empty())
    return -1;
  // Get the first element which is the minimum element and will be deleted
  
  int answer = array.front();
  
  /* Copy the last element to the 0th position and try to percolate
     it down to its correct position to maintain the heap properties
  */
  array[0] = array[array.size()-1];
  // Delete the last element since it has been copied to the first position
  array.pop_back();
  
  /*
     If the array is not empty now, proceed with the steps
     to perform percolation. Otherwise just quit by returning
     the answer.
  */
  if (!array.empty()) {
    int pos = 0;
    int lc_pos, rc_pos;
    
    // Get a copy of the element currently at position 0
    int temp_top = array[0];
    int cmp;
    
    /*
      Keep percolating down to the smallest child of the current node
      till there are no children or both the children are greater than
      temp_top
    */
    while( pos < array.size())
    {
      /* Check if there is a left child. If there is none,
         we are at the correct position, so quit the loop.
      */
      if ( 2*pos + 1 >= array.size()) {
	      break;
      }
      else
      {
        /* 
        Get the left child position let it be the element to
        compare against temp_top unless there is a right child
        and it is less than the left child
        */
        
	      lc_pos = 2*pos + 1;
	      cmp = lc_pos;
	      
	      /* Check if there is a right child and if it is there,
	      compare it with the left child and pick up the position of the
	      smaller element for comparison in cmp.
	      */
	      if (2*pos + 2 < array.size()) {
	        rc_pos = 2*pos+2;
	        if (array[rc_pos] < array[lc_pos])
	        cmp = rc_pos;
	      }
        /*
          Compare the element at cmp with the temp_top. If it is lesser,
          copy it to the current position pos, then point pos to the position cmp
          for further comparison. If not, we have reached
          the correct position for temp_top, so quit the loop so that
          we can insert it in the position.
        */
	      if (array[cmp] < temp_top) {
	        array[pos] = array[cmp];
	        pos = cmp;
	      }
	      else
	        break;
      }
    }
    // Insert temp_top at its correct position
    array[pos] =  temp_top;
  }
  // Return the deleted minimum element
  return answer;
}

void Heap::print()
{
  for (vector<int>::const_iterator item=array.begin(); item != array.end();++item)
    cout<<*item<<endl;
}

int main()
{
  Heap h;
  h.insert(17);
  h.insert(11);
  h.insert(88);
  h.insert(9);
  h.insert(2);
  h.insert(14);
  h.insert(10);
  h.print();
  cout<<h.delete_min()<<endl;
  cout<<h.delete_min()<<endl;
  cout<<h.delete_min()<<endl;
  cout<<h.delete_min()<<endl;
  cout<<h.delete_min()<<endl;
  cout<<h.delete_min()<<endl;
  cout<<h.delete_min()<<endl;
  h.insert(20);
  h.insert(10);
  h.insert(88);
  cout<<h.delete_min()<<endl;
  cout<<h.delete_min()<<endl;
  cout<<h.delete_min()<<endl;
  cout<<h.delete_min()<<endl;
  return 0;
}