#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