minheap implementation

minheap.cpp

#include "minheap.h"

/* Default constructor */
minheap::minheap()
{
  // Ensure that there is always an empty element at index 0
  values.push_back(0); 
};

void minheap::insert(int v)
{
   // Insert at "next" location
   values.push_back(v);
   // Percolate up
   for(int i = values.size() -1; i > 1; i /= 2)
   {
       if(values[i] < values[i/2]) // If inserted value is less than its parent
       {
           // Swap them
           int temp = values[i];
           values[i] = values[i/2];
           values[i/2] = temp;
           /* // Alternative: XOR swap - good to know for software interviews!
           values[i] ^= values[i/2];
           values[i/2] ^= values[i];
           values[i] ^= values[i/2];
           // */
       }else{
           break;
       }
   }
}

int minheap::findMin()
{
   return values[1];
}

void minheap::deleteMin()
{
   if(values.size() == 1) // empty heap
   {
       return;
   }
   // Swap "last" element into the root
   values[1] = values[values.size() - 1];
   values.pop_back();
   // Percolate down
   int i = 1;
   while(true)
   {
       // Compare to each child
       if(values[i*2] < values[i*2 + 1]) // Left branch is lesser; must swap left
       {
           if(values[i*2] < values[i]){ // Should swap left
               int temp = values[i];
               values[i] = values[i*2];
               values[i*2] = temp;
               i = i*2;
           }else{
               break;
           }
       }else{ // Right branch is lesser; swap right
           if(values[i*2 + 1] < values[i]){
               int temp = values[i];
               values[i] = values[i*2 + 1];
               values[i*2 + 1] = temp;
               i = i*2 + 1;
           }else{
               break;
           }
       }
   }
}

minheap.h

#ifndef MINHEAP_H
#define MINHEAP_H

#include <vector>
using namespace std;

class minheap{
public:
   minheap();
   void insert(int);
   int findMin();
   void deleteMin();

private:
   vector<int> values;
};
#endif