#include <stdio.h>
#include <stdlib.h>
int *heap;
int capacity;
void heapify(int nodeIndex, int heapBottom) {
int lastParentIndex = heapBottom/2;
while (nodeIndex <= lastParentIndex) {
int leftChildIndex = 2 * nodeIndex;
int maxIndex = leftChildIndex;
if((leftChildIndex + 1 <= heapBottom) && (heap[leftChildIndex + 1] > heap[leftChildIndex])) {
maxIndex = leftChildIndex + 1;
}
if (heap[nodeIndex] < heap[maxIndex]) {
int temp = heap[nodeIndex] ;
heap[nodeIndex] = heap[maxIndex];
heap[maxIndex] = temp;
nodeIndex = maxIndex;
}
else {
break;
}
}
}
void heapFromBottom(int arr[], int length) {
heap = (int*)malloc(sizeof(int)*(length+1));
capacity = length;
for (int i = 0; i < length; ++i) {
heap[i+1] = arr[i];
}
int lastParentIndex = length/2;
for (int i = lastParentIndex; i > 0; --i) {
heapify(i, capacity);
}
}
void sort() {
int heapTop = 1;
int heapBottom = capacity;
while (heapTop < heapBottom) {
int temp = heap[heapTop];
heap[heapTop] = heap[heapBottom];
heap[heapBottom] = temp;
--heapBottom;
heapify(heapTop, heapBottom);
}
}
void printArray(int array[], int length) {
for (int i = 0; i < length; i++) {
printf("%3d",array[i]);
}
printf("\n");
}
int main () {
int arr[] = {2, 9, 7, 6, 5, 8};
heapFromBottom(arr, 6);
printArray(heap+1, 6);
sort();
printArray(heap+1, 6);
return 0;
}