Monday, October 15, 2012

Binary Min Heap in C++


#include
#include

      int *data;
      int heapSize=0;
      int arraySize=0;

      int getLeftChildIndex(int nodeIndex) {
            return 2 * nodeIndex + 1;
      }

      int getRightChildIndex(int nodeIndex) {
            return 2 * nodeIndex + 2;
      }

      int getParentIndex(int nodeIndex) {
            return (nodeIndex - 1) / 2;
      }


  void    BinaryMinHeap(int size)
 {
            data = new int[size];
            heapSize = 0;
            arraySize = size;
      }  


void siftUp(int nodeIndex) {
      int parentIndex, tmp;
      if (nodeIndex != 0) {
            parentIndex = getParentIndex(nodeIndex);
            if (data[parentIndex] > data[nodeIndex]) {
                  tmp = data[parentIndex];
                  data[parentIndex] = data[nodeIndex];
                  data[nodeIndex] = tmp;
                  siftUp(parentIndex);
            }
      }
}

void insert(int value) {
      if (heapSize == arraySize)
            printf("Heap's underlying storage is overflow");
      else {
            heapSize++;
            data[heapSize - 1] = value;
            siftUp(heapSize - 1);
      }
}

void display()
{
for(int i=0;i{
printf("%5d",data[i]);
}
}
int main()
{
int d,a;
printf("enter the size of heap");
scanf("%d",&d);
BinaryMinHeap(d);
for(int i=0;i {
printf("enter the element");
scanf("%d",&a);
   
insert(a);
    }
    display();
getch();
     return 0;
}

No comments:

Post a Comment