二叉堆其实就是一棵堆有序的二叉树
开篇
本篇文章主要讲什么
此文是排序算法系列文章的倒数第三篇，因此本文的主要意图还是讲排序算法，这次我们一起聊聊堆排序。
在正式开始之前，我们先要花些篇幅聊两种很重要的基础数据结构——优先队列和二叉堆。
正文
优先队列（PriorityQueue）
有时我们需要处理一组有序数据时，并不需要它们整体有序。设想这样一种情况，对于一组数据，每次我们都只处理其中键值最大的元素，我们可能会把这组数据的规模扩大，往里面放更多新元素，但仍是每次挑键值最大的元素来处理。对于这种情况我们当然可以使整组数据一直保持整体有序，但这不是必要的——我们只需保证第一个元素始终是键值最大那个就行。
这就需要引入了一种新的数据结构——优先队列，它应该高效地实现两种基本操作，访问最大元素和插入元素。
一种优先队列的经典实现方式就是使用二叉堆这种更低级点的数据结构。
二叉堆（BinaryHeap）
接着来详细了解下二叉堆（下简称堆）这种数据结构。
看到这个名字你是不是想到了二叉树？堆其实就是一棵堆有序的二叉树（二叉树这种更低级的数据结构非本文重点，此处略过不表，还请读者自行复习二叉树相关知识）。
何为堆有序？
当一颗二叉树的每个结点其键值都大于等于它的两个子结点时，我们称其是堆有序的。
也即在一颗堆有序的二叉树中，每个结点的键值都小于等于它的父结点。很容易确定，根结点是一棵堆有序的二叉树中键值最大的结点。
这是一个堆：
11
/ \
9 10
/ \ / \
5 6 7 8
/ \ / \
1 2 3 4
具体我们如何在程序中表示一个堆呢？用数组即可。
就是将堆（二叉树）的结点按层级顺序依次放入数组中。为了方便后面算法的表示，我们不使用数组的第一个位置，即从数组下标为 1 的位置开始存储一个堆。把上面的堆放入数组中我们可以得到：
[-1，11, 9, 10, 5, 6, 7, 8, 1, 2, 3, 4]//把上面的二叉堆按层级顺序放入数组中，注意我们没使用数组第一个位置，我们把没使用到的数组位置置值为-1表示
这样一个数组。
这样表示的堆有几条重要性质：
- 位置（也即下标） n 的结点其父结点的位置为 n/2
- 位置（也即下标） n 的结点其两个子结点的位置为 2n 或 2n + 1（如果两个子结点都存在的话）
- 一颗大小为 N 的完全二叉树其高度为（lg N)
1 和 2 让我们可以不使用指针，仅通过计算数组的索引在树中上下移动，3 保证了我们实现的基本操作其算法仅具有对数级别的时间复杂度。
下面我们用 Java 代码来实现一个基于二叉堆的自然数优先队列：
/**
* 基于二叉堆实现的正整数优先队列
* 注意下面注释的表述可粗略认为优先队列等于二叉堆等于二叉树
*/
public class IntPQ {
private int[] heap;//用于存放整个二叉堆(值)的数组，不使用数组第一个位置，即 heap[0] 我们永远也用不到
private int size = 0;//堆当前的体积大小，二叉堆存储于数组 heap 的[1-size] 中，heap[0] 无用
/**
* <p>构造函数</p>
* @param size：需要构造的优先队列的初始大小
*/
public IntPQ(int size) {
heap = new int[size + 1];
}
/**
* <p>交换数组中两个位置的值</p>
* @param i 待交换值的位置
* @param j 待交换值的位置
*/
private void exch(int i, int j){
if (i < 1 || i >= heap.length || j < 1 || j >= heap.length){
return;
}
int mid = heap[i];
heap[i] = heap[j];
heap[j] = mid;
}
/**
*
* @return 优先队列是否是空的
*/
public boolean isEmpty(){
return size == 0;
}
/**
*
* @return 优先队列当前大小
*/
public int size(){
return size;
}
/**
* 注意下面两个方法极为重要，即二叉堆结点的跃迁和降级操作，
* 什么意思呢？
* 首先我们要知道数据结构的树和现实世界中的树有点不一样，数据结构的树树根在上树叶在下，现实世界反之，我们这里讨论数据结构的树
* 所谓跃迁操作，就是这个树下面的某个结点的键值比它的父结点要大，那它肯定要跃迁到它父结点上面才能使整棵树堆有序
* 反之，就是所谓的降级操作
* 就是堆中某个结点不在它该在的位置，打破了二叉树的堆有序时，我们将其归位让二叉树重新堆有序的操作
* 这两个方法是 insert 和 delMax 方法的基础*/
/**
* <p>二叉堆中指定位置结点的跃迁操作，如果此结点的值比它的父结点大，就和父结点交换位置，如此往复直至树的根部</p>
* @param i 待跃迁结点位置
*/
private void up(int i){
while (i > 1 && heap[i] > heap[i/2]){//需要上浮的结点位置在根结点下面且值大于它的父结点
//交换 i 和 i/2 两个位置的值
exch(i, i/2);
i /= 2;
}
}
/**
* <p>二叉堆中指定位置结点的降级操作，如果此结点的值比它的两个自结点中较大那个小，就和此子结点交换位置，如此往复直至树的叶子结点那层</p>
* @param i 待跃迁结点位置
*/
private void down(int i){
while (i * 2 <= size){
int j = i * 2;
if (j < size && heap[j] < heap[j + 1]){
j += 1;
}
if (heap[i] < heap[j]){
//交换 i 和 j 两个位置的值
exch(i, j);
i = j;
}else {
break;
}
}
}
/**
* <p>结点插入操作，注意这里我偷懒没写给数组扩容的逻辑，因这不是重点略过没写，读者可自行改进
* 此方法具有对数级别的平均时间复杂度</p>
* @param value 待插入的结点
*/
public void insert(int value){
//将结点插入当前二叉树的最后面，同时使当前二叉树的大小加一
heap[++ size] = value;
//新插入的结点可能会破坏二叉树的堆有序，然后对其执行跃迁操作，以让其归入正确位置，确保二叉树的堆有序
up(size);
}
/**
* <p>删除并返回队列中值最大的那个元素（其实就是当前树根），也就是树根结点，此方法具有对数级别的平均时间复杂度</p>
* @return
*/
public int delMax(){
int max = heap[1];//从二叉树的根结点得到键值最大的元素
//将根结点的最后一个叶子结点交换位置，并将树的大小减一，
// 此时我们相当于把根结点删除了，但新的根结点键值不一定是最大的，
// 所以我们需要降级归位，使二叉树重新堆有序
exch(1, size --);
down(1);//根结点降级归位，使二叉树重新堆有序
return max;
}
}
堆排序
经过上面那么多铺垫，一种新的排序算法已呼之欲出。
是滴，利用二叉堆这种数据结构，我们可以实现一种新的排序算法——堆排序。
终于说到堆排序了！你可以暂缓几分钟，接着我们来好好聊聊什么是堆排序，准备好~
堆排序的思路是这样的，利用优先队列（基于二叉堆）的两个基本操作（插入元素和删除最大元素），我们可以写出对数组原地排序的更高效算法，其最坏时间复杂度仅为线性对数级别的（n log n）。具体算法实现共分两步，构造堆和销毁堆。
- 构造堆：即先对数组进行原地调整，让整个数组堆化。基于堆元素的跃迁和降级操作，你或许会有多种思路来将一个数组堆化，这里我们使用一种最经典高效的方法来将一个数组堆化。即使用下沉操作遍历树中的所有非叶子结点，递归地给数组构造出堆的秩序。为什么要这样来构造堆？因为这是对数组操作最少，最节省成本的堆构造方式。这个问题其实很有意思，值得好好思考。之所以只遍历所有非叶子结点，是因为我们可以跳过所有大小为 1 的子堆，因为大小为 1 的子堆（子树）已经是一个堆了（已经堆有序了），而如果一个结点的两个子结点已经是堆了，那在此结点上调用降级操作可将它们变成一个整体的堆，就是如此，递归地给数组建立起堆的秩序。这里有个问题，堆中的非叶子结点分布在数组中的什么位置区间？如果现在的数组规模为 n ，那答案就是从堆第一个结点的位置到数组下标 n/2，即[1, n/2]，这点很容易自证。如果用来给数组原地排序的话，那堆在数组中存放时就不能跳过第一个位置了，这样当前堆所有非叶子结点所在区间就是[0, n/2 - 1]。
- 销毁堆：将数组构建出堆秩序后，我们已经得到了一个堆。再进一步，使数组达到整体有序，接下来要做的就是一个结点一个结点地销毁掉整个堆。你应该很容易想到，所用方法正是递归地删除当前二叉堆的树根，将其跟最后一个结点交换位置，然后堆的规模减一，此时新的根结点可能会破坏堆有序状态，我们对其进行降级操作使新的规模缩减的堆重新变成堆有序，如此递归，直至堆的规模缩减为一，此时整个数组达到整体有序，排序完成。
OK 捋完整体逻辑我们来撸一下代码：
/**
* <p>堆排序的 Java 实现</p>
* @param array: 待排序数组，我们采用原地排序
*/
public static void sortHeap(int[] array){
//第一步，构建堆
int start = array.length/2 - 1;//构建堆的开始遍历下标，因为数组是从下标 0 开始存放堆的，所以减一，此下标在遍历中递减
int bound = array.length - 1;//待操作子堆最后一个下标，也可看做当前堆长度，不过此长度从 0 开始计
for (; start >= 0; start --){
down(array, start, bound);
}
//第二步，销毁堆，这个过程跟选择排序有点类似
while (bound > 0){
exch(array, 0, bound);
down(array, 0, -- bound);
}
}
/**
* <p>交换数组中两个位置的值</p>
* @param i 待交换值的位置
* @param j 待交换值的位置
*/
private static void exch(int[] array, int i, int j){
if (i < 0 || i >= array.length || j < 0 || j >= array.length){
return;
}
int mid = array[i];
array[i] = array[j];
array[j] = mid;
}
/**
* <p>调整后的堆结点降级操作</p>
* @param heap 待操作数组，存放堆
* @param index 待降级操作的结点位置
* @param bound 待操作结点所在子堆(此子堆根结点目前不在应在位置，我们对其根结点执行降级操作使其归位)的最后一个结点位置（下标）
*/
private static void down(int[] heap, int index, int bound){
//注意对比原始的 down 方法中操作下标的地方，这里多了很多 + 1 操作，原因就是我们从数组中第一个位置开始存放堆
while (index * 2 + 1 <= bound){
int j = index * 2 + 1;
if (j < bound && heap[j] < heap[j + 1]){
j += 1;
}
if (heap[index] < heap[j]){
//交换 i 和 j 两个位置的值
exch(heap, index, j);
index = j;
}else {
break;
}
}
}
代码主要看 sortHeap 方法。
我的天花这么多篇幅终于聊完本文主角堆排序了！
总结
堆排序的效率比 冒泡排序、选择排序、插入排序和希尔排序都要高，其最差时间复杂度仅为线性对数级别的O(n log n)。
尾巴
关于优先队列这种数据结构，它的应用场景可不止排序，本系列后续文章会再单独聊聊这种数据结构，你会看到更多优先队列大显身手的应用场景，敬请期待。
下篇，我们聊聊归并排序。
完。
网友评论