Heap #1: Build A MAX Heap

If you want to understand the code fully please read Introduction to algorithm(CLRS) chapter-6 first.

#include<cstdio>

#include<iostream>

using namespace std;

int Parent(int index)

{

return index>>1; // index/2

}

int LeftChild(int index)

{

return index<<1; // 2 * index

}

int RightChild(int index)

{

return (index<<1) + 1; // (2 * index) + 1

}

void Max_Heapify(int *x, int index, int heapsize)

{

//cout<<"Visit-->"<<index<<endl;

int left = LeftChild(index);

int right = RightChild(index);

int largest = index;

if(left<=heapsize && x[left]>x[largest])

{

largest = left;

}

if(right<=heapsize && x[right]>x[largest])

{

largest = right;

}

if(largest != index)

{

swap(x[largest], x[index]);

Max_Heapify(x, largest, heapsize);

}

}

void Build_Max_Heap(int *x, int heapsize)

{

for(int I=(heapsize/2); I>0; I--)

{

Max_Heapify(x, I, heapsize);

}

}

void printArray(int *x, int arraySize)

{

for(int I=0; I<arraySize; I++)

{

cout<<I<<" "<<x[I]<<endl;

}

cout<<endl;

}

int main()

{

//Heap start from index 1

int a[] = {-1,2,3,4,5,6,7,8};

int arraySize = sizeof(a)/sizeof(*a);

printArray(a, arraySize);

Build_Max_Heap(a, arraySize-1);

//cout<<"--"<<heapsize<<endl;

printArray(a, arraySize);

return 0;

}