【算法自由之路】重要的堆结构、堆排序排序算法通用比较器

什么是堆？

堆结构是特殊的二叉树结构，首先堆一定是完全二叉树，同时在提到堆的时候必不可少的要提到它是 大根堆 还是 小根堆

大根堆： 在整个二叉树结构中，所有节点满足父节点 大于 左右子节点称之为大根堆

小根堆： 在整个二叉树结构中，所有节点满足父节点 小于 左右子节点称之为小根堆

使用数组实现一个堆

如果用数组实现堆结构，我们需要推断出父节点与左右子节点的下标关系，若以数组 0 下标为数组 root 根节点，则存在

对于任意节点 i
左孩子 = i * 2 + 1
右孩子 = i * 2 + 2
父节点 = i/2 - 1以下是下标表示的树01       23   4    5   6

事实上，我们对以上的关系可以有一个计算优化，舍弃 0 下标位置，root 从 1 位置开始

对于任意节点 i
左孩子 = i * 2 = i << 1
右孩子 = i * 2 + 1 = i << 1 | 1
父节点 = i/2 = i >> 1以下是下标表示的树12       34   5   6   7

所有的运算都可以转换为位运算进行

1. 每次给定一个数，如何构建一个堆？

我们需要一个算法对新添加的数进行验证和调整，使我们的结构在插入任意一个数时仍然维持堆结构

思路是，每次插入元素，都在数组最后一个顺位插入，然后当前位置向上找父节点，比对是否大于父节点，如果大于则交换直到堆顶，否则跳出，这个过程是下列 heapInsert 方法和 upBalance

package algorithmic.base;import java.util.Arrays;/*** @program: algorithmic-total-solution* @description: 大根堆的数组实现* @author: wangzibin* @create: 2022-11-15**/
public class BigHeap {private int[] data;private int heapSize;private int size;public BigHeap(int size) {// 0 位置弃置不用data = new int[size + 1];heapSize = 0;this.size = size;}public void heapInsert(int num) {if (heapSize >= size) {throw new IllegalStateException("堆已满");}int currentIndex = ++heapSize;data[currentIndex] = num;// 这是一个向上比对交换的过程upBalance(currentIndex);}/*** @Description: 向上平衡* @Param currentIndex* @Return void*/private void upBalance(int currentIndex) {int parentIndex = findParent(currentIndex);while (data[currentIndex] > data[parentIndex] && parentIndex != 0) {swap(currentIndex, parentIndex);currentIndex = parentIndex;parentIndex = findParent(currentIndex);}}private int findLeftChild(int currentIndex) {return currentIndex << 1;}private int findRightChild(int currentIndex) {return currentIndex << 1 | 1;}private int findParent(int currentIndex) {return currentIndex >> 1;}private void swap(int i, int j) {int tmp = data[i];data[i] = data[j];data[j] = tmp;}public static void main(String[] args) {BigHeap bigHeap = new BigHeap(20);bigHeap.heapInsert(1);bigHeap.heapInsert(2);bigHeap.heapInsert(3);bigHeap.heapInsert(4);bigHeap.heapInsert(5);bigHeap.heapInsert(6);System.out.println(Arrays.toString(bigHeap.data));}}

结果是这样的

[0, 6, 4, 5, 1, 3, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]64    5
1 3  2

2. 提供方法，每次弹出堆中最大值，并使得剩余元素仍然是一个堆

对于大根堆，最大值很好找，就是堆顶的元素，但难得是如何在弹出堆顶后仍然保持堆结构呢？这需要算法来动态调整

方案是：堆顶与数组最后一个位置交换弹出，新的堆顶向下比对进行交换平衡堆的结构。以下是增加功能优化后的大根堆代码

package algorithmic.base;import java.util.Arrays;/*** @program: algorithmic-total-solution* @description: 大根堆的数组实现**/
public class BigHeap {private int[] data;private int heapSize;private int size;public BigHeap(int size) {// 0 位置弃置不用data = new int[size + 1];heapSize = 0;this.size = size;}public void heapInsert(int num) {if (heapSize >= size) {throw new IllegalStateException("堆已满");}int currentIndex = ++heapSize;data[currentIndex] = num;// 这是一个向上比对交换的过程upBalance(currentIndex);}public int pop() {if (isEmpty()) {throw new IllegalStateException("empty heap");}int result = data[1];swap(1, heapSize--);downBalance(1);return result;}public boolean isEmpty() {return heapSize == 0;}/*** @Description: 向上平衡* @Param currentIndex* @Return void*/private void upBalance(int currentIndex) {int parentIndex = findParent(currentIndex);while (data[currentIndex] > data[parentIndex] && parentIndex != 0) {swap(currentIndex, parentIndex);currentIndex = parentIndex;parentIndex = findParent(currentIndex);}}private void downBalance(int currentIndex) {int left = findLeftChild(currentIndex);// 如果左孩子已经越界，则不需要调整while (left <= heapSize) {int right = findRightChild(currentIndex);int swapIndex = left;if (right <= heapSize) {swapIndex = data[left] > data[right] ? left : right;}if (data[swapIndex] < data[currentIndex]) {return;}swap(swapIndex, currentIndex);currentIndex = swapIndex;left = findLeftChild(currentIndex);}}private int findLeftChild(int currentIndex) {return currentIndex << 1;}private int findRightChild(int currentIndex) {return currentIndex << 1 | 1;}private int findParent(int currentIndex) {return currentIndex >> 1;}private void swap(int i, int j) {int tmp = data[i];data[i] = data[j];data[j] = tmp;}public static void main(String[] args) {BigHeap bigHeap = new BigHeap(20);bigHeap.heapInsert(1);bigHeap.heapInsert(2);bigHeap.heapInsert(3);bigHeap.heapInsert(4);bigHeap.heapInsert(5);bigHeap.heapInsert(6);System.out.println(Arrays.toString(bigHeap.data));while (!bigHeap.isEmpty()){System.out.println(bigHeap.pop());}}}

到现在，整个 pop 过程 和 insert 过程的时间复杂度都是 O(logN) 级别 空间复杂度 O(1)

3. 如何实现堆排序

让我们看一眼 downBalance 做了什么事，这个方法可以将已经是堆结构的数组中任意 i 位置的数调整为 [i, length] 范围中最大的数，且时间复杂度为 O(logN)。

于是有了以下操作

public static void main(String[] args) {BigHeap bigHeap = new BigHeap(20);bigHeap.heapInsert(1);bigHeap.heapInsert(2);bigHeap.heapInsert(3);bigHeap.heapInsert(4);bigHeap.heapInsert(5);bigHeap.heapInsert(6);// 建堆 O(N*logN)System.out.println(Arrays.toString(bigHeap.data));// O(N)while (!bigHeap.isEmpty()){// 每次搞定最大的一个数到最后位置bigHeap.swap(1, bigHeap.heapSize);// 将最后位置排除堆bigHeap.heapSize--;// 堆顶元素做 downBalance 找到最大值 O(logN)bigHeap.downBalance(1);}System.out.println(Arrays.toString(bigHeap.data));}

输出：

[0, 6, 4, 5, 1, 3, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 2, 3, 4, 5, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

所以，堆排序的时间复杂度为 O(N*logN) ，且！空间复杂度 O(1)

4. 给定数组进行堆排序

首先，将给定数组调整为堆，然后进行上述 downBalance 调整，每次搞定一个最大数(O(logN))，搞定 N 个数 (O(N*logN))

  public BigHeap(int[] arr) {// 0 位置弃置不用int size = arr.length + 1;data = new int[size];heapSize = arr.length;this.size = size;for (int i = 0; i < arr.length; i++) {data[i + 1] = arr[i];}for (int i = heapSize; i >= 1; i--) {downBalance(i);}}public void sort() {while (!isEmpty()) {swap(1, heapSize);heapSize--;downBalance(1);}}public static void main(String[] args) {for (int i = 0; i < 10000; i++) {int[] arr = RandomUtil.randomArr();int[] arr2 = CommonUtil.copyArr(arr);BigHeap bigHeap = new BigHeap(arr);bigHeap.sort();MargeSort.sort(arr2);for (int j = 0; j < arr.length; j++) {if (arr2[j] != bigHeap.data[j + 1]) {System.out.println(Arrays.toString(arr2));System.out.println(Arrays.toString(bigHeap.data));System.out.println("error");return;}}}System.out.println("success");}

在用户给定一个数组的情况下，调整为堆，这个时间复杂度可以优化为 O(N)

  public BigHeap(int[] arr) {// 0 位置弃置不用int size = arr.length + 1;data = new int[size];heapSize = arr.length;this.size = size;for (int i = 0; i < arr.length; i++) {data[i + 1] = arr[i];}for (int i = heapSize; i >= 1; i--) {downBalance(i);}}

这里思路是从位开始进行 downBalance ，有同学可能有些疑惑这个方法不也是 O(logN) 的方法吗，但在这个循环中整体分析是 O(N) 的。

在最后一层的时候 downBalance ，N/2 个节点只进行一次操作，倒数第二层 N/4 个节点最多进行 2 次操作，以此类推，最终求和收敛于 N

注意，这里我数据转存了一下到内部属性 data，完全可以不转存，调整 downBalance 和 upBalance 的入参即可实现空间复杂度 O(1)

5. 堆在排序中的一个应用

了解了堆这种结构以及实现，最重要的是知道如何使用它，以及何时使用。这需要时间和经验的积累，这里给出一个例子作为引子。

给定一个数组，该数组在排序过程中，每个数的移动位数不超过 k 个距离。如 在 0 为位置的数，在排序过后，它的下标位置不会大于 k-1。且这个给定的 k 远远小于 数组长度。请使用合适的算法给数组排序。

上述问题就可以通过堆结构来实现，我们构建一个 k 大小的小根堆，首先入堆前 k 个元素，弹出最小值排序到数组开头，这个就是数组最小值，后移一位入堆，继续弹出最小值放入第二个，以此类推。

因为排序后移动不会超过 k 个距离这个特性，所以我们可以用堆来进行排序，而这个算法时间复杂度可以达到 O(N*logk)

Java 提供的堆 PriorityQueue

Queue queue = new PriorityQueue<>();

在 Java 中，PriorityQueue 底层就是堆结构实现的，别看他叫 Queue 队列，其实默认就是一个 小根堆 。通过实现 比较器，我们可以使其变为 大根堆

比较器 Comparator

在排序算法中，我们都是在使用基本数据类型 int 进行值的比较，这样有很大的局限性，无法比较我们自定义的包装类型。

其实对于我们所有的比较，我们只需要知道两个值谁在前谁在后即可，这个比较可以抽象成一个接口，让使用者自己实现即可。

// 返回 -1，0,1 分别表示 第一个参数 小于，等于，大于 第二个参数
int compare(T o1, T o2);

该比较器接口由你需要进行比较的类本身实现，排序算法类调用其比较方法即可。

什么时候需要自己实现一个堆

系统实现的堆没办法实现堆的动态调整，比如我更新了堆中的某个值，已经构建好的对是无法更新的，这个时候堆结构可能已经不成立了。像这种定制化的需求就需要我们手动来实现功能。

整体思路即，维护一个堆中对象及其位置的 map 表，即我们可以根据对象直接定位到其在堆中的数组下标，然后根据新值重新对该位置的数进行 downBalance 和 upBalance 这两个逻辑只会执行一个，这个重平衡的时间复杂度是 O(N*logN) 的