算法导论 第6章 堆排序

相比归并排序和插入排序，堆排序 的时间复杂度是O(nlgn)与归并排序相同，且具有与插入排序一样的空间原址性，即任何时候只需要常数个额外的元素空间存储临时数据。因此堆排序是一种集合了这两种算法优点的排序算法。

堆排序引入了称为 堆 的数据结构，堆是一个数组，可以看成一个近似的完全二叉树，树上每个节点对应一个数组元素。

另树的根节点为A[1]，且给定一个节点的下标i，他的父节点下标为i/2向下取整，左孩子为2i，右孩子为2i+1。

最大堆 是指除了根节点以外所有节点满足父节点的值大于等于当前节点的值的堆。最小堆 是指除了根节点以外所有节点满足父节点的值小于等于当前节点的值的堆。如一个最大堆：

堆排序使用最大堆，最小堆通常用于构建优先队列。

维护堆

MAX-HEAPIFY定义了维护最大堆性质的过程，输入为数组A和下标i。该过程假定节点的左右子树都是最大堆，通过逐级下降地比较当前节点和子节点来调整至整个树为最大堆：

该过程时间复杂度O(lgn)。

对i=2的子树执行过程：

建立堆

BUILD-MAX-HEAP定义了建立堆的过程，其中对所有非叶子节点从下到上依次调用MAX-HEAPIFY，都执行完后即可得到最大堆：

该过程时间复杂度O(n)。

对数组{4, 1, 3, 2, 16, 9, 10, 14, 8, 7}的执行过程：

堆排序

HEAPSORT实现了建立最大堆并输出排序结果的过程，该过程每次将根节点调换至最后位置，并重新调整堆至最大堆：

该过程时间复杂度O(nlgn)。

执行过程：

优先队列

堆的另一个应用是作为高效的 优先队列，用于计算机系统的作业调度等场合。优先队列是一种用来维护一组元素的数据结构，其中每个元素有一个关键字。优先队列支持插入、返回最大（小）关键字、去掉并返回最大（小）关键字、将元素的关键字值增大（减小）等操作。