堆排序（Heapsort）
维基百科：
时间复杂度：O(n log n)
示例：
[6, 5, 3, 1, 8, 7, 2, 4]
1、堆（Heap）
维基百科：
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: If A is a parent node of B then key(A) is ordered with respect to key(B) with the same ordering applying across the heap.
PARENT(i)
return i / 2
LEFT(i)
return 2 * i
RIGHT(i)
2 * i + 1
2、Heapify
最大堆为例，伪代码：
MAX-HEAPIFY(A, i)
l = LIFT(i)
r = RIGHT(i)
if l <= A.heapsize and A[l] > A[i]
largest = l
else largest = i
if r <= A.heapsize and A[r] > A[largest]
largest = r
if largest != i
exchage A[i] with A[largest]
MAX-HEAPIFY(A, largest)
3、Build Heap
最大堆为例，伪代码：
BUILD-MAX-HEAP(A)
A.heap-size = A.length
for A.length / 2 downto 1
MAX-HEAPIFY(A, i)
4、Heapsort
最大堆为例，伪代码：
HEAPSORT(A)
BUILD-MAX-HEAP(A)
for i = A.length downto 2
exchange A[1] with A[i]
A.heap-size = A.heap-size - 1
MAX-HEAPIFY(A, 1)
5、Priority Queue
最大堆为例，伪代码：
HEAP-MAXIMUM(A)
return A[1]
HEAP-EXTRACT-MAX(A)
if A.heap-size < 1
error "heap underflow"
max = A[1]
A[1] = A[A.heap-size]
A.heap-size = A.heap-size - 1
MAX-HEAPIFY(A, 1)
return max
HEAP-INCREASE-KEY(A, i, key)
if key < A[i]
error "new key is smaller than current key"
A[i] = key
while i > 1 and A[PARENT(i)] < A[i]
exchange A[i] with A[PARENT(i)]
i = PARENT(i)
MAX-HEAP-INSERT(A, key)
A.heap-size = A.heap-size + 1
A[A.heap-size] = - INFINITY
HEAP-INCREASE-KEY(A, A.heap-size, key)
C语言实现
heap.h
typedef struct { int *array; int length; int heap_size;} Heap;int heap_parent(int index);int heap_left_child(int index);int heap_right_child(int index);
heap.c
int heap_parent(int index) { return (index - 1) / 2;}int heap_left_child(int index) { return 2 * index + 1;}int heap_right_child(int index) { return 2 * (index + 1);}
heap_sort.h
#import "heap.h"void max_heap_sort(Heap heap);
heap_sort.c
#import "heap_sort.h"void exchange(int *a, int *b) { int temp = *a; *a = *b; *b = temp;}void max_heapify(Heap heap, int index) { int largest = index; int left = heap_left_child(index); int right = heap_right_child(index); if (left < heap.heap_size && heap.array[left] > heap.array[right]) { largest = left; } if (right < heap.heap_size && heap.array[right] > heap.array[largest]) { largest = right; } if (largest != index) { exchange(heap.array + largest, heap.array + index); max_heapify(heap, largest); }}void build_max_heap(Heap heap) { int i; for (i = heap.length / 2 - 1; i >= 0; i--) { max_heapify(heap, i); }}void max_heap_sort(Heap heap) { int i; build_max_heap(heap); for (i = heap.length - 1; i > 1; i--) { exchange(heap.array, heap.array + i); heap.heap_size -= 1; max_heapify(heap, 0); }}
main.c
#import#import "heap_sort.h"int main() { int i; int array[8] = { 6, 5, 3, 1, 8, 7, 2, 4}; Heap heap = {array, 8, 8}; max_heap_sort(heap); for(i = 0; i < heap.length; i++) { printf("%d \n", heap.array[i]); } return 0;}
运行结果：
