堆结构是特殊的二叉树结构，首先堆一定是完全二叉树，同时在提到堆的时候必不可少的要提到它是 大根堆 还是 小根堆
大根堆： 在整个二叉树结构中，所有节点满足父节点 大于 左右子节点称之为大根堆
小根堆： 在整个二叉树结构中，所有节点满足父节点 小于 左右子节点称之为小根堆
如果用数组实现堆结构，我们需要推断出父节点与左右子节点的下标关系，若以数组 0 下标为数组 root 根节点，则存在
对于任意节点 i
左孩子 = i * 2 + 1
右孩子 = i * 2 + 2
父节点 = i/2 - 1
以下是下标表示的树
0
1 2
3 4 5 6
事实上，我们对以上的关系可以有一个计算优化，舍弃 0 下标位置，root 从 1 位置开始
对于任意节点 i
左孩子 = i * 2 = i << 1
右孩子 = i * 2 + 1 = i << 1 | 1
父节点 = i/2 = i >> 1
以下是下标表示的树
1
2 3
4 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]
6
4 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)
Queue<Integer> queue = new PriorityQueue<>();
在 Java 中，PriorityQueue 底层就是堆结构实现的，别看他叫 Queue 队列，其实默认就是一个 小根堆 。通过实现 比较器，我们可以使其变为 大根堆
在排序算法中，我们都是在使用基本数据类型 int 进行值的比较，这样有很大的局限性，无法比较我们自定义的包装类型。
其实对于我们所有的比较，我们只需要知道两个值谁在前谁在后即可，这个比较可以抽象成一个接口，让使用者自己实现即可。
// 返回 -1，0,1 分别表示 第一个参数 小于，等于，大于 第二个参数
int compare(T o1, T o2);
该比较器接口由你需要进行比较的类本身实现，排序算法类调用其比较方法即可。
系统实现的堆没办法实现堆的动态调整，比如我更新了堆中的某个值，已经构建好的对是无法更新的，这个时候堆结构可能已经不成立了。像这种定制化的需求就需要我们手动来实现功能。
整体思路即，维护一个堆中对象及其位置的 map 表，即我们可以根据对象直接定位到其在堆中的数组下标，然后根据新值重新对该位置的数进行 downBalance 和 upBalance 这两个逻辑只会执行一个，这个重平衡的时间复杂度是 O(N*logN) 的