堆排序实际上是利用了完全二叉树的公式化描述特性，将一个数组以最大堆的方式呈现，并逐一删除其根节点。
几个概念要理解：
假设完全二叉树中一元素的序号为i，1 <= i <= n，则以下关系成立：
1. 当i=1时，该元素为二叉树的根。若i>1，则该元素父节点的编号为i/2(int取整)；
2. 当2i>n时，该元素无左孩子，否则，其左孩子的编号为2i；
3. 当2i+1>n时，该元素无右孩子 ，否则，其右孩子的编号为2i+1。
最大树：每个节点的值都大于或等于其子节点值的树。
最大堆：完全二叉树 && 最大树。
MaxHeap.c:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define RET_TRUE 0 #define RET_FALSE -1 struct MaxHeap { int *data; int total_size; int cur_size; }; static struct MaxHeap * maxheap_init(int size); static void maxheap_destroy(struct MaxHeap **heap); static int maxheap_insert(struct MaxHeap *heap, int ele); static int maxheap_delete_max(struct MaxHeap *heap, int *ret_ele); static void swap_int(int *a, int *b) { int c = *a; *a = *b; *b = c; } static struct MaxHeap * maxheap_init(int size) { struct MaxHeap *heap; if(size <= 0) return NULL; heap = malloc(sizeof(struct MaxHeap)); if(NULL == heap) return NULL; memset(heap, 0, sizeof(struct MaxHeap)); heap->data = malloc(size * sizeof(int)); if(NULL == heap->data) { free(heap); return NULL; } memset(heap->data, 0, size * sizeof(int)); heap->total_size = size; heap->cur_size = 0; return heap; } static void maxheap_destroy(struct MaxHeap **heap) { struct MaxHeap *m_heap; m_heap = *heap; if(m_heap) { if(m_heap->data) { free(m_heap->data); m_heap->data = NULL; } free(m_heap); m_heap = NULL; } } static int maxheap_insert(struct MaxHeap *heap, int ele) { int i; if(NULL == heap || NULL == heap->data || heap->total_size == heap->cur_size) /* heap is full */ return RET_FALSE; heap->data[heap->cur_size++] = ele; for(i = heap->cur_size - 1; i > 0; i--) { if(heap->data[i] > heap->data[i/2]) { swap_int(&heap->data[i], &heap->data[i/2]); } } return RET_TRUE; } static int maxheap_delete_max(struct MaxHeap *heap, int *ret_ele) { int i, left_i, right_i; if(NULL == heap || NULL == ret_ele || heap->cur_size <= 0) /* heap is empty */ return RET_FALSE; *ret_ele = heap->data[0]; heap->data[0] = heap->data[--heap->cur_size]; i = 1; left_i = 2*i; right_i = 2*i+1; while(left_i <= heap->cur_size) { if(right_i <= heap->cur_size) { /* Both left child and right child exist. */ if(heap->data[left_i-1] > heap->data[i-1] && heap->data[left_i-1] > heap->data[right_i-1]) { swap_int(&heap->data[left_i-1], &heap->data[i-1]); /* Choose left child as the biggest. */ } else if(heap->data[right_i-1] > heap->data[i-1] && heap->data[right_i-1] > heap->data[left_i-1]) { swap_int(&heap->data[right_i-1], &heap->data[i-1]); /* Choose right child as the biggest. */ } } else { /* Only left child exists. */ if(heap->data[i-1] < heap->data[left_i-1]) swap_int(&heap->data[i-1], &heap->data[left_i-1]); } i++; left_i = 2*i; /* 根据完全二叉树的特性寻找左/右子节点 */ right_i = 2*i+1; } return RET_TRUE; } static void print_max_heap(struct MaxHeap *heap) { int i = 0; if(heap && heap->data) { printf(" Max heap: "); for(i = 0; i < heap->cur_size; i++) printf("%d ", heap->data[i]); printf("\n"); } } int main() { int ele, index; struct MaxHeap * max_heap = maxheap_init(10); maxheap_insert(max_heap, 45); maxheap_insert(max_heap, 32); maxheap_insert(max_heap, 78); maxheap_insert(max_heap, 65); maxheap_insert(max_heap, 12); maxheap_insert(max_heap, 5); maxheap_insert(max_heap, 90); maxheap_insert(max_heap, 22); maxheap_insert(max_heap, 89); maxheap_insert(max_heap, 2); print_max_heap(max_heap); index = max_heap->cur_size; printf("Heap Sort: "); while(index--) { maxheap_delete_max(max_heap, &ele); printf("%d ", ele); } printf("\n"); return 0; }