tags: DSA C++ Python

写在前面

记录一下二叉堆和堆排序, 堆(二叉堆)作为一种基本数据结构, 常在lc周赛三题位置出现, 遇到了我只能干着急, 必须好好学一下了. 参考算法导论(第三版).

这里说的堆指的是数据结构(抽象概念), 而不是程序执行时候的堆区(内存实体)

二叉堆介绍

二叉堆（英语：binary heap）是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆¹。

• 当父节点的键值总是大于或等于任何一个子节点的键值时为“最大堆”。
• 当父节点的键值总是小于或等于任何一个子节点的键值时为“最小堆”。

实际使用时, 二叉堆表示为一个数组, 可以被看成近似的完全二叉树(叶结点从左下角开始)

在一颗二叉树中，若除最后一层外的其余层都是满的，并且最后一层要么是满的，要么在右边缺少连续若干节点，则此二叉树为完全二叉树²（Complete Binary Tree）。

具有nnn个节点的完全二叉树的深度为log⁡2n+1\log_2n+1log2​n+1。深度为kkk的完全二叉树，至少有2k−1{\displaystyle 2^{\begin{aligned}k-1\end{aligned}}}2k−1​个节点，至多有2k−1{\displaystyle 2^{\begin{aligned}k\end{aligned}}-1}2k​−1个节点。

堆具有以下几种属性:

• length: 二叉堆(数组)长度;

• root: 根节点;

• 父节点/左子节点/右子节点:
  设iii表示任一节点下标(下标从000开始), 则
  {Parent(i)=⌊(i−1)/2⌋;Left(i)=2i+1;Right(i)=2i+2;\begin{cases} Parent(i)=\lfloor (i-1)/2\rfloor;\\ Left(i)=2i+1;\\ Right(i)=2i+2; \end{cases} ⎩⎪⎨⎪⎧​Parent(i)=⌊(i−1)/2⌋;Left(i)=2i+1;Right(i)=2i+2;​

• 最大堆(堆排序):
  arr[Parent(i)]≥arr[i]arr[Parent(i)]\geq arr[i] arr[Parent(i)]≥arr[i]

• 最小堆(优先队列):
  arr[Parent(i)]≤arr[i]arr[Parent(i)]\leq arr[i] arr[Parent(i)]≤arr[i]

下面的ASCII图来自Wikipedia¹, 分别展示了小根堆和大根堆.

            1                                 11                          /      \                          /      \ 2         3                       9         10/    \     /   \                   /   \     /    \ 4      5   6     7                5      6   7      8/ \    / \                        / \    / \8  9   10 11                      1   2  3   4 

堆化(heapify)

这里以大根堆为例. 如输入数组不满足堆的条件(根节点大于等于子节点), 则需要对数组进行堆化.

小根堆调整一下大小于号即可.

基本方法(递归调用)

void Max_Heapify(vector &arr, int len, int i) {// array index start with 0int l = 2 * i + 1, r = 2 * i + 2;int largest = i;if (l < len and arr[l] > arr[largest]) largest = l;if (r < len and arr[r] > arr[largest]) largest = r;if (largest != i) {swap(arr[i], arr[largest]);Max_Heapify(arr, len, largest);}
}

其中,

• arr是堆数组, 以引用方式传参使其可以原地修改;
• len是数组长度, 这里虽然不改变参数的值, 但是后面进行堆排序时候会用到的;
• i是待堆化(heapify)的结点索引, 一般取值为0;

首先根据上面的节点之间的关系公式计算左子节点和右子结点的编号, 然后当前节点分别与左子结点和右子节点值进行比较, 若不满足堆的条件就记录新的最大值, 最后交换最大值即可. 最后向下遍历(递归)直到都满足条件.

思路还是比较清晰, 因为用到了递归.

迭代法

这里因为用到了尾递归, 所以直接修改递归函数的最后一行中传值语句即可³.

void Max_Heapify(vector &arr, int len, int i) {bool done = false;while (!done) {int largest = i, l = 2 * i + 1, r = 2 * i + 2;if (l < len && arr[l] > arr[largest]) largest = l;if (r < len && arr[r] > arr[largest]) largest = r;if (largest != i) {swap(arr[i], arr[largest]);i = largest;} elsedone = true;}
}

还有一种方法, 这里参考了⁴的代码, 感觉不如while循环来的直观,

void Max_Heapify(vector &arr, int len, int i) {int largest{}, tmp = arr[i];for (; i * 2 < len; i = largest) {largest = i * 2;if (largest + 1 < len && arr[largest + 1] > arr[largest]) largest++;if (arr[i] < arr[largest])swap(arr[largest], arr[i]);elsebreak;}
}

这种方法把递归传值放在了for中, 跳出条件是i * 2 < len, 通过让largest++的方式完成左右子结点与当前节点的比较, 是相当巧妙的写法.

建堆

通过堆化数组来完成:

void Build_Max_Heap(vector &arr) {int n = arr.size();for (int i = (n - 1) / 2; i >= 0; --i) Max_Heapify(arr, n, i);
}

排序

void Heap_Sort(vector &arr) {Build_Max_Heap(arr);int n = arr.size();for (int i = n - 1; i > 0; --i) {swap(arr[0], arr[i]);Max_Heapify(arr, i, 0);}
}

这里的排序是原地操作, 即每次从堆化后的数组中"弹出"(用交换操作完成)一个最大值(根)放在最后, 一直到数组头.

需要注意的是, 在弹出根节点之后, 还需要调整其余的n-1结点的顺序, 使其仍保持堆的属性, 就是通过前面的Heapify完成的.

ref