编辑代码

#include <stdio.h>
#include <math.h>

void heapify(int *heap, int capacity) {
	int lastParentIndex = floor(capacity/2);
	int i = lastParentIndex;
	for (; i>0; --i) {
		int parentIndex = i;
		while (parentIndex <= lastParentIndex) {
			int leftChildIndex = 2*parentIndex;
			int maxIndex = leftChildIndex;

			if ((leftChildIndex+1 <= capacity) && (heap[leftChildIndex+1] > heap[maxIndex]))
				maxIndex = leftChildIndex + 1;

			if (heap[parentIndex] < heap[maxIndex]) {
				int temp = heap[parentIndex];
				heap[parentIndex] = heap[maxIndex];
				heap[maxIndex] = temp;

				parentIndex = maxIndex;
			} else
				break;
		}
	}
}

void heapSort(int *heap, int capacity) {
	int top=1, buttom=capacity-1, swap;
	while (top < buttom) {
		swap = heap[top];
		heap[top] = heap[buttom];
		heap[buttom] = swap;
		heapify(heap, --buttom);
	}
}

void printHeap(int *heap, int capacity) {
	int i = 1;
	for (; i<capacity; i++) printf("%d ", heap[i]);
	printf("\n");
}

int main() {
	int heap0[] = {-1, 9, 6, 8, 2, 5, 7, 4};
	int capacity = 8;
	heapify(heap0, capacity);
	printHeap(heap0, capacity);
	heapSort(heap0, capacity);
	printHeap(heap0, capacity);

	int heap1[] = {-1, 1, 2, 3, 4};
	capacity = 5;
	heapify(heap1, capacity);
	printHeap(heap1, capacity);
	heapSort(heap1, capacity);
	printHeap(heap1, capacity);

	int heap2[] = {-1, 4, 3, 2, 1};
	capacity = 5;
	heapify(heap2, capacity);
	printHeap(heap2, capacity);
	heapSort(heap2, capacity);
	printHeap(heap2, capacity);

    int heap3[] = {-1};
	capacity = 1;
	heapify(heap3, capacity);
	printHeap(heap3, capacity);
	heapSort(heap3, capacity);
	printHeap(heap3, capacity);

    int heap4[] = {-1, 1, 1, 1, 1};
	capacity = 5;
	heapify(heap4, capacity);
	printHeap(heap4, capacity);
	heapSort(heap4, capacity);
	printHeap(heap4, capacity);

    int heap5[] = {-1, 1};
	capacity = 2;
	heapify(heap5, capacity);
	printHeap(heap5, capacity);
	heapSort(heap5, capacity);
	printHeap(heap5, capacity);

	return 0;
}