编辑代码

#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;
}