什么是堆排序

理解堆排,首先要理解二叉堆。理解了二叉堆的“下沉”操作,基本上就可以理解堆排了。今天我们来看一看什么是堆,以及堆的一般操作

优先级队列

近日,谦子遇到了烦心事,于是找老师去诉苦了
1.png
谦子列了几个要做的事
2.png
谦子道出了心中的苦
3.png
谦子两眼发光
4.png
克顺手画了一个图
5.png

优先级队列中每个元素都有优先级优先级最高的最先被处理

优先队列的实现

6.png
谦子非常想知道黑盒里面是什么
7.png
克非常善于引导学生思考
8.png
谦子想了想说
10.png
谦子说着说着画了一个图
11.png
谦子画了一幅图解释道
12.png
随后,谦子又画出了插入6后的图
13.png
克还是不满意
14.png

15.png

这里我们只讨论二叉堆,把二叉堆称为堆
堆也有d-堆,左式堆等等

16.png
克看谦子不是很明白,顺手画了个图
17.png
克画了一个二叉堆实例
18.png

注意:二叉堆中两个孩子之前的大小没有关系,可能左孩子>=右孩子,也可能右>=左

19.png
克随手画了一个小根堆和一个大根堆
20.png
21.png
22.png

插入操作

23.png

每个父节点的值小于等于其左右孩子的值被称为堆的有序性
另一种情况是大于等于也称之为堆的有序性

克随手画了一个插入操作破坏堆有序性的图
24.png
如何调整,谦子心里想
25.png
上浮这个词形象生动,谦子心里想
26.png
说完,克飞速地写出了上浮的代码

1
2
3
4
5
6
7
8
9
10
11
12
/**
* 如果待插入的元素小于其父,则交换子和父,并继续上浮,直到大于等于其父
* @param arr 储存堆的数组,元素从下标1开始有效,0位置不存在有效值
* @param inserted 被插入节点的索引
*/
public void swim(int[] arr, int inserted) {
int parent = inserted/2;
if (arr[inserted] < arr[parent]) {
swap(arr, inserted, parent);
swim(arr, parent);
}
}

谦子暗自惊叹老师的代码功力

删除操作

29.png
谦子听完此话紧张的手心出汗,但还是硬着头皮想了想,突然灵光一现
30.png
随后谦子画出了交换后的图
31.png
32.png
33.png
34.png
35.png
谦子刚松了口气,谁知还要写代码,只见谦子想了想,写写擦擦好几遍最终写下了如下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 对以arr[parentIndex]为父节点的堆进行调整(下沉)
* 在父节点,左右孩子中选出最小的节点,如果最小节点不是父节点则交换
* 继续下沉,反之不下沉
* @param arr 要调整的数组
* @param parentIndex 父节点的索引
*/
public void sink(int[] arr, int parentIndex) {
// 堆的大小,第0 个位置无有效值
int heapSize = arr.length - 1;
// 从父节点,左孩子和右孩子选出最小节点,得其索引
int minNodeIndex = minIndex(arr, parentIndex, heapSize);
// 如果最小的节点的索引不是父节点,则说明最小的节点在左右孩子中,交换并继续下沉调整
if (minNodeIndex != parentIndex) {
swap(arr, minNodeIndex, parentIndex);
sink(arr, minNodeIndex); // 交换后继续下沉
}
}

36.png
慧子解释道,并画了一个图
37.png
只见谦子又写了一段代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 求得给定的三个节点的最小节点的索引
* @param parentIndex 父节点的索引
* @param heapSize 堆的大小
* @return 最小节点的索引
*/
private int minIndex(int[] arr, int parentIndex, int heapSize) {
int minIndex = parentIndex; // 保存最小节点的下标,初始时认为父节点最小
int leftIndex = leftIndex(parentIndex); // 找到parent的左孩子下标
// 如果leftIndex没有越界,比较左孩子和父节点,选择小的Node的下标赋给minIndex
if (leftIndex <= heapSize) {
minIndex = arr[leftIndex] < arr[parentIndex] ? leftIndex : parentIndex;
}
int rightIndex = rightIndex(parentIndex);
if (rightIndex < heapSize) {
minIndex = arr[rightIndex] < arr[minIndex] ? rightIndex : minIndex;
}
return minIndex;
}

leftIndex = 2parentIndex;
rightIndex = 2
parentIndex+1;

40.png

看来以后得好好学数据结构与算法了,不然连时间都管理不好,谦子心想