堆的结构实现与堆排序

photo-1536733203354-a125031aa773.jpg

1. 堆

堆是特殊的完全二叉树的情况,因此我们来大致来了解一下完全二叉树:

f9dcd100baa1cd1171faf1bdb512c8fcc2ce2dda.jpg

简单来说,完全二叉从上至下,从左往右进行编号,总会有连续(不间断)的1 ~ n序号。

堆在二叉树的基础上,满足:任意结点小于(大于)它的所有子结点,最小(大)值的结点位于根结点。如果根结点为最大值的结点则为最大堆,值大于它的所有子结点;相反,则为最小堆,如下图所示:

UTOOLS1556615020584.png

2. 堆的实现

2.1 底层结构

我们可以对堆的每个结点从上至下,从左往右进行编号,并将每个结点的序号按照下标将值存储到数组当中。因此,我们可以用一个数组来实现堆的数据结构。如下图所示:

UTOOLS1556615340975.png

进行这样的抽象后,可以很方便获取到某结点的父结点与左右结点的序号,它们满足(假设某结点序号为i):

  • 父结点: (i - 1) / 2

  • 左结点:2 * i + 1;右结点:2 * i + 2

2.2 构造堆

对于给定一个乱序的完全二叉树数组,我们需要调整为正常的堆结构。首先需要了解的一步操作是heapify。例如对于给定的二叉树:

UTOOLS1556616048025.png

从根结点进行调整(针对最大堆),因为左结点10大于根结点,所以将它们交换位置;交换之后其左结点5仍然大于4,继续交换它们的位置,直到左右节点为空。调整完成的结果如下:

UTOOLS1556616269523.png

代码实现为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void heapify(int[] tree, int n, int i) {
if (i >= n) return; // 递归出口,序号大于n说明结点为空

int left = 2 * i + 1, right = 2 * i + 2;
int max = i; // 找到父节点、左结点、右结点较大的那个数的序号

if (left < n && tree[left] > tree[max]) {
max = left;
}
if (right < n && tree[right] > tree[max]) {
max = right;
}
if (max != i) { // 父结点不是最大时进行调整
swap(tree, max, i); // 交换结点的值
heapify(tree, n, max); // 递归进行调整
}
}

public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

可以发现,上列的完全二叉树右子树是完整的堆结构。如果所给的二叉树左右子树都需要进行调整,则单单一个heapify则不够:

UTOOLS1556616714863.png

我们可以**从最后一个结点的父结点序号开始往上调整。对于上图来说,我们从尾结点9的父节点2开始调用heapify进行调整即可:

1
2
3
4
5
6
7
8
public void buildHeap(int[] tree, int n) {
int last = n - 1; // 最后一个结点
int parent = (last - 1) / 2; // 最后一个结点的父结点

for (int i = parent; i >= 0; i--) { // 从parent序号的结点开始倒着调用heapify
heapify(tree, n, i);
}
}

交换的过程如下:

UTOOLS1556617551125.png

3. 堆排序

对于一个给定的乱序数组,我们将该数组看成是乱序的完全二叉树结构。首先调用buildHeap进行构造调整为正常的堆结构。

然后每次将根结点与末尾序号的节点(尾结点)进行交换,并切割掉该尾结点,再调用heapify重新调整为正常的堆结构,重复该操作直至堆的结构为空。我们可以用一个for循环来完成并省去切割尾结点的操作。变量i代表当前堆的尾结点序号:

1
2
3
4
5
6
7
public void heapSort(int[] tree, int n) {
buildHeap(tree, n);
for (int i = n - 1; i >= 0; i--) {
swap(tree, i, 0); // 根结点与最后一个结点进行交换
heapify(tree, i, 0); // i代表当前剩余的结点数量,指向堆的尾结点
}
}

可以发现,每次切割出来的尾结点(最大的元素)将会被追加到数组的末尾(每次都进行了交换),当循环结束时,原先的乱序数组将会升序排列。

Pushy wechat
欢迎订阅我的微信公众号