堆与堆排
Oildum
2020-12-20 08:35:52
rt，今天我们就来讲这些东西。
---
### 1.堆是个什么玩意
堆是一种特殊的**二叉树**，可以用**数组**模拟
~~所以堆具有随机访问性（雾）~~
那么堆特殊在哪呢？其实堆分为两种：**大根堆（又称最大堆、大顶堆）**、**小根堆（又称最小堆、小顶堆）**。
其中大根堆的定义如下：
$$\boxed{\text{设}x\text{为大根堆中的某个节点，则}x\text{的左右孩子的值均小于等于}x\text{的值}}$$
小根堆则是把其中的小于等于换成大于等于。
那么，如何构建一个堆呢？
---
### 2.维护堆的性质
这里我们只讲大根堆，因为小根堆应该可以自己推得（
并且堆排序用到的也是大根堆。
首先来说一下思路吧：
1.对于某个节点 $x$，检查它的左孩子和右孩子的值是否比 $x$ 的值大；
2.如果 $x$ 是三者之中最大的，那么就结束；
3.否则将最大的节点的值与 $x$ 的值交换，再在最大的节点上重复这个过程。
这很明显就是一个递归函数。
那么用上我们模拟二叉树时候的几个函数：
```java
int parent(int n) {
return (n-1) / 2;
}
int left(int n) {
return 2 * n + 1;
}
int right(n) {
return 2 * n + 2;
}
```
就可以向下一节进发了！
---
### 3.Talking is cheap. Show me the code.
上一节中我们讲到了维护大根堆性质的思路，这次我们就来写代码。
首先我们把堆这个类先写个样子出来：
```java
class Heap {
private int heap_size;
private int[] heap;
public Heap() {this(0);}
public Heap(int size) {
heap_size = size;
heap = new int[heap_size];
}
public int getSize() {return heap_size;}
private int parent(int n) {
return (n - 1) / 2;
}
private int left(int n) {
return 2 * n + 1;
}
private int right(int n) {
return 2 * n + 2;
}
}//先写这么多
```
把前面的思路写成代码就可以得到：
```java
public void max_heapify(int i) {//在i处大根堆化
int l = left(i);
int r = right(i);//获取左右孩子的下标
int largest = 0;//储存最大节点的下标
if (l < heap_size && heap[l] > heap[i]) {
largest = l;//最大的是左孩子
} else {
largest = i;//最大的是自己
}
if (r < heap_size && heap[r] > heap[largest]) {
largest = r;//最大的是右孩子
}
if (largest != i) {//如果最大的不是自己
int t = heap[i];
heap[i] = heap[largest];
heap[largest] = t;//交换
max_heapify(largest);//继续在最大处大根堆化
}
}//结束
```
个人认为还挺容易理解的（
---
### 4.建堆
这个就没什么说的了，直接每个节点都最大堆化即可（
代码：
```java
public void buildMaxHeap(int heap[]) {
this.heap = heap;
this.heap_size = heap.length;//先把堆拷贝到自己这里
for (int i = heap_size / 2 - 1; i >= 0; i--) {
max_heapify(i);
}//在每个节点大根堆化
}
```
---
### 5.堆排序
终于进入了正题：堆排序。
堆排序其实算是堆的一个操作之一（
思路是这样的：首先把数组变成一个大根堆，然后将最大元素与当前最末一个元素交换。这是再大根堆化即可。
代码：
```java
public int[] heapsort(int arr[]) {
buildMaxHeap(arr);//构造大根堆
for (int i = arr.length - 1; i > 0; i--) {
int t = heap[0];
heap[0] = heap[i];
heap[i] = t;//交换第一个与最末一个
heap_size -= 1; //堆大小减少1
max_heapify(0); //在0处大根堆化
}
return heap;//把排序过的数组返回
}//由此可见调用heapsort会伤及自身，珍爱数据，远离堆排（
```
---
### 6.当前代码
现在我们的`Heap`类也是有模有样了（
先把代码放出来：
```java
class Heap {
private int heap_size;
private int[] heap;
public Heap() {this(0);}
public Heap(int size) {
heap_size = size;
heap = new int[heap_size];
}
public int getSize() {return heap_size;}
private int parent(int n) {
return (n - 1) / 2;
}
private int left(int n) {
return 2 * n + 1;
}
private int right(int n) {
return 2 * n + 2;
}
public void max_heapify(int i) {
int l = left(i);
int r = right(i);
int largest = 0;
if (l < heap_size && heap[l] > heap[i]) {
largest = l;
} else {
largest = i;
}
if (r < heap_size && heap[r] > heap[largest]) {
largest = r;
}
if (largest != i) {
int t = heap[i];
heap[i] = heap[largest];
heap[largest] = t;
max_heapify(largest);
}
}
public void buildMaxHeap(int heap[]) {
this.heap = heap;
this.heap_size = heap.length;
for (int i = heap_size - 1; i >= 0; i--) {
max_heapify(i);
}
}
public int[] heapsort(int arr[]) {
buildMaxHeap(arr);
for (int i = arr.length - 1; i > 0; i--) {
int t = heap[0];
heap[0] = heap[i];
heap[i] = t;
heap_size -= 1;
max_heapify(0);
}
return heap;
}
}
```
然而，堆的操作可不止这些。
---
### 7.改静为动
目前看来，堆好像是个静态数据结构，对吧？
**不！**
其实，它是**动态**的！
我们怎么实现这几种操作呢？
---
### 8.先来一个小热身
首先，我们需要一个前置：数组的插入。
这个比较简单：
```java
private int[] arrAppend(int arr[], int n) {
arr = java.util.Arrays.copyOf(arr, arr.length + 1);//复制并扩容
arr[arr.length - 1] = n;//加到新的空间里
return arr;//返回
}
```
---
### 9.堆的操作
首先就是最大值。
```java
public int maximum() {
if (heap_size == 0) {
throw new RuntimeException("堆为空");//检查
}
return heap[0];//但愿调用时满足大根堆性质
}
```
如果调用时满足大根堆性质，那就是这么简单。
然后是删除最大值，这一点和堆排序的主循环很像：
```java
public int extract_max() {
int max = maximum();//取最大值，这样顺便做个检查，如果为空就有异常，也不会执行后面的语句
heap[0] = heap[heap_size - 1];//最大值与最末一个值交换
heap_size -= 1;//堆大小减1
max_heapify(0);//维护大根堆性质
return max;//返回最大值
}
```
接下来是增值：
```java
public void increase_key(int i, int key) {//在节点i处增值
if (key < heap[i]) {
throw new RuntimeException("新值小于旧值");//检查
}
heap[i] = key;//暴力设置
while (i > 0 && heap[parent(i)] < heap[i]) {//从此处往上，检查有没有违反最大堆性质，如果有，进入循环
int t = heap[i];
heap[i] = heap[parent(i)];
heap[parent(i)] = t;//交换当前值与父节点值
i = parent(i);//继续往上
}
}
```
最后是插入和删除：
```java
public void insert(int key) {
heap = arrAppend(heap, Integer.MIN_VALUE);
heap_size += 1;
increase_key(heap_size-1, key);
}
public void delete(int i) {//删除i处的值
increase_key(i, Integer.MAX_VALUE);
extract_max();
}
```
怎么样，是不是不难（
---
### 10.结语
呼，终于讲完了
这是我整个系列里最长的一篇文章（（（