1.基本思想
具有n个元素的序列 （h1,h2,...,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。完全二 叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。
2.实现原理
初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个 堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对 它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。
一般用数组来表示堆，若根结点存在序号0处， i结点的父结点下标就为(i-1)/2。i结点的左右子结点下标分别为2*i+1和2*i+2。
（注：如果根结点是从1开始，则左右孩子结点分别是2i和2i+1。）
如第0个结点左右子结点下标分别为1和2。
3.代码实例
(1)代码:
//使树成为一个大顶堆:顶部最大 public void HeapAdjust(int[] array, int parent, int length) { int temp = array[parent]; // temp保存当前父节点 int child = 2 * parent + 1; // 先获得左孩子 while (child < length) { // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点 if (child + 1 < length && array[child] < array[child + 1]) { child++; } // 如果父结点的值已经大于孩子结点的值，则直接结束 if (temp >= array[child]) break; // 把孩子结点的值赋给父结点 array[parent] = array[child]; // 选取孩子结点的左孩子结点,继续向下筛选 parent = child; child = 2 * child + 1; } array[parent] = temp; } public void heapSort(int[] list) { // 循环建立初始堆 for (int i = list.length / 2; i >= 0; i--) { HeapAdjust(list, i, list.length - 1); } // 进行n-1次循环，完成排序 for (int i = list.length - 1; i > 0; i--) { // 最后一个元素和第一元素进行交换 int temp = list[i]; list[i] = list[0]; list[0] = temp; // 筛选 R[0] 结点，得到i-1个结点的堆 HeapAdjust(list, 0, i); System.out.format("第 %d 趟: ", list.length - i); printPart(list, 0, list.length - 1); } } // 打印序列 public void printPart(int[] list, int begin, int end) { for (int i = 0; i < begin; i++) { System.out.print(" "); } for (int i = begin; i <= end; i++) { System.out.print(list[i] + " "); } System.out.println(); } public static void main(String[] args) { // 初始化一个序列 int[] array = { 70, 60, 12, 40, 30, 8, 10 }; // 调用快速排序方法 HeapSort heap = new HeapSort(); System.out.print("排序前: "); heap.printPart(array, 0, array.length - 1); heap.heapSort(array); System.out.print("排序后: "); heap.printPart(array, 0, array.length - 1); }
(2)结果:
排序前: 70 60 12 40 30 8 10
第 1 趟: 60 40 12 10 30 8 70
第 2 趟: 40 30 12 10 8 60 70
第 3 趟: 30 10 12 8 40 60 70
第 4 趟: 12 10 8 30 40 60 70
第 5 趟: 10 8 12 30 40 60 70
第 6 趟: 8 10 12 30 40 60 70
排序后: 8 10 12 30 40 60 70
4.算法分析
堆排序也是一种不稳定的排序算法。
堆排序优于简单选择排序的原因：
简单选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果，可减少比较次数。
堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
5.排序特点
堆排序是一种树形选择排序，是对简单选择排序的有效改进。