堆排序就是对简单选择排序进行的一种改进。(调整堆的过程就是选择待排序序列中的最大值，本质和选择排序是一样的)。
记录的比较与交换是跳跃式进行，因此堆排序是一种不稳定的原地排序方法。
不适合待排序序列个数较少的情况。
在堆排序算法中，我们使用的是大顶堆，小顶堆通常在构造优先队列时使用。

堆结构
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子的结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

堆排序基本思想：利用堆进行排序。将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列。

主要解决两个问题：
1.如何由一个无序序列构建成一个堆？
2.如果在输出堆顶元素后，调整剩余元素成为一个新的堆？

C++实现

/********************************/
/***********堆排序***************/
/********************************/
void HeapAdjust(ElemType a[],int s,int m)
{
	int temp,j;
	temp = a[s];
	for(j = 2*s;j <= m;j *= 2)  //沿关键字较大的孩子节点向下筛选
	{
		//当前节点s，左孩子为2s，右孩子为2s+1，所以j=2*s
		if(j < m && a[j] < a[j+1])
			++j;	//j为关键字中较大的记录下标
		if(temp >= a[j])
			break;
		a[s] = a[j];
		s = j;
	}
	a[s] = temp; //插入
}

void HeapSort(ElemType a[],int n)
{
	int i;
	//第一个循环将现在的待排序序列构建成一个大顶堆
	for(i = n/2;i >= 0;i--) //i>=0
	{
		HeapAdjust(a,i,n-1);
	}
	//第二个循环将每个最大值的根节点与末尾元素交换，并在调整为大顶堆
	for(i = n-1;i > 0;i--)
	{
		swap(a,0,i);	//将堆顶记录和当前未经排序子序列的最后一个记录交换
		HeapAdjust(a,0,i-1);//将a[0..i-1]重新调整为大顶堆
	}
}

Python实现

#-------------#
#--Heap sort--#
#-------------#			
def heap_adjust(arr,s,m):
	rc = arr[s]
	j = 2*s
	while j <= m :
		if  j < m and arr[j] < arr[j+1]:
			j += 1
		if rc >= arr[j]:
			break
		arr[s] = arr[j]
		s = j
		j *= 2
	arr[s] = rc
	
def heap_sort(arr):
	arrlen = len(arr)
	for i in reversed(range(0,arrlen/2+1)): #range:arrlen/2+1?
		heap_adjust(arr,i,arrlen-1)
	for i in reversed(range(1,arrlen)):
		swap(arr,0,i)
		heap_adjust(arr,0,i-1)

堆排序复杂度分析：
运行时间消耗主要消耗在初始构建堆和重建堆时的反复筛选上。
构建整个堆的时间复杂度为o(n)。
排序时候第i次堆顶记录重建堆需要o(logi)的时间，需要取n-1次堆顶记录，所以重建堆的时间复杂度为o(nlogn)。
堆排序的时间复杂度为o(nlogn)。对排序状态不敏感，无论是最好、最坏和平均时间复杂度均为o(nlogn)。
空间复杂度o(1)。

优先级队列
堆的一个常见应用：作为高效的优先级队列。
优先级队列是一种用来维护由一组元素构成的集合S的数据结构，这一组元素中的每一个都有一个关键字key。
最大优先级队列的一个应用是在一台分时计算机上进行作业调度。