Thnking in Heaps : Algorithms

An interative version of max-Heap :

void iter_maxHeapify(int * a,int rootIndex,int heapLength){
int largest = rootIndex;
int leftIndex = left(rootIndex);
int rightIndex = left(rootIndex);

for(int largest = rootIndex;
(leftIndex < heapLength) || (rightIndex < heapLength);
leftIndex = left(rootIndex),rightIndex = right(rootIndex)){

if(leftIndex < heapLength && a[rootIndex] < a[leftIndex]){
largest = leftIndex;
}
if(rightIndex < heapLength && a[largest] < a[rightIndex]){
largest = rightIndex;
}
if(rootIndex != largest){
swap(a[largest],a[rootIndex]);
rootIndex = largest;
}
}

}

Building the Heap:

void buildMaxHeap(int * a,int heapLength){
for(int i = heapLength/2;i >=0;i--){
maxHeapify(a,i,heapLength);
}
}


Sorting a heap:

void heapSort(int * a ,int heapLength){
buildMaxHeap(a,heapLength);
for(int i = 0;i < heapLength;i++){
swap(a[i],a[heapLength-1]);
maxHeapify(a,1,heapLength-i-1);
}
}