Heap sort

首先，将元素进行重排，以符合堆的条件。图中排序过程之前简单的绘出了堆树的结构。

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序的平均时间复杂度为Ο(nlogn) 。

算法描述

1. 创建一个堆H[0..n-1]
2. 把堆首（最大值）和堆尾互换
3. 把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
4. 重复步骤2，直到堆的尺寸为1

示例代码

C

#define MAX_HEAP_LEN 100
 static int heap[MAX_HEAP_LEN];
 static int heap_size = 0;              // the number of elements in heaps
 
 static void swap(int* a, int* b)
 {
 	int temp = *b;
 	*b = *a;
 	*a = temp;
 }
 
 static void shift_up(int i)
 {
 	int done = 0;		
 	if( i == 0) return;            //node is the root already
 	while((i!=0)&&(!done)) 
 	{
 		if(heap[i] > heap[(i-1)/2])		
 		{//if the current is larger than the parent, then swap
 			swap(&heap[i],&heap[(i-1)/2]);
 		}
 		else
 		{// the job is already done.
 			done =1;
 		}
 		i = (i-1)/2;
 	}
 }
 
 static void shift_down(int i)
 {
 	int done = 0;	
 	if (2*i + 1> heap_size) return;         // node i is a leaf
 
 	while((2*i+1 < heap_size)&&(!done))
 	{
 		i =2*i+1;                       // jump to left child
 		if ((i+1< heap_size) && (heap[i+1] > heap[i]))
 		{// find the bigger one of the two children	
 			i++;
 		}
 		if (heap[(i-1)/2] < heap[i])
 		{
 			swap(&heap[(i-1)/2], &heap[i]);
 		}
 		else
 		{
 			done = 1;
 		}
 	}
 }			
 
 static void delete(int i)
 {
 	int last = heap[heap_size - 1];     // get the last one;
 	heap_size--;                        // shrink the heap
 	if (i == heap_size) return;
 	heap[i] = last;                     // use the last item to overwrite the current
 	shift_down(i);
 }
 
 int delete_max()
 {
 	int ret = heap[0];
 	delete(0);	
 	return ret;  
 }
 
 void insert(int new_data)
 {
 	if(heap_size >= MAX_HEAP_LEN) return;  
 	heap_size++;
 	heap[heap_size - 1] = new_data;	
 	shift_up(heap_size - 1); 
 }