共计 2703 个字符,预计需要花费 7 分钟才能阅读完成。
1. 介绍
1)什么是堆?
堆是一棵 顺序存储 的齐全二叉树。
每个结点的关键字都 小于或等于 其所有子结点的关键字,这样的堆称为 小根堆。
每个结点的关键字都 大于或等于 其所有子结点的关键字,这样的堆称为 大根堆。
2)什么是堆排序?
堆排序(Heapsort)是指利用堆这种数据结构来进行排序的 抉择排序 算法。沉积是一个近似齐全二叉树的构造,并同时满足子结点的值总是小于(或者大于)它的父节点。
- 小根堆 在排序算法中用于 升序 排列;
- 大根堆 在排序算法中用于 降序 排序;
3)留神:
- 堆排序 只实用于 程序构造。
- 堆排序的均匀工夫复杂度是
O(nlongn)
,最好和最坏的工夫复杂度也是O(nlongn)
。空间复杂度是O(n)
- 堆排序是先建堆,依此输入堆顶元素(把堆顶元素换到数组前面)后调整堆。
2. 算法步骤
以 大根堆 为例,
- 创立一个大根堆
- 替换堆顶和最初一个元素,剩下的元素从新调整为 大根堆
3. 残缺代码
堆排序的全副代码如下(代码应用 Java 编写):
// 堆排序
public void heapsort(int[] list) {build(list, list.length - 1);
// 每调整一次堆,在数组最初就会多一个曾经排好序的数。堆中个数为 1 时,不解决
for (int i = list.length - 1; i > 0; i--) {swap(list, 0, i); // 排好序的数组中减少一个数
adjust(list, 0, i - 1);
}
}
// 建堆,自下而上建堆。先保障上面的是堆,再把后面的数退出堆中,调整为堆。public int[] build(int[] list, int end) {
// 从最初一个父节点开始
for (int i = (end - 1) / 2; i >= 0; i--) {adjust(list, i, end);
}
return list;
}
// 调整堆,从上自下调整。调整堆时,除了堆顶元素,其余的都满足堆的性质,所以从上向下把较大的元素移到下面
public int[] adjust(int[] list, int start, int end) {
int maxIndex, left, right;
for (int i = start; i <= (end - 1) / 2; i++) {
maxIndex = i;
left = 2 * i + 1;
right = 2 * i + 2;
if (left <= end && list[left] > list[maxIndex]) maxIndex = left;
if (right <= end && list[right] > list[maxIndex]) maxIndex = right;
if (maxIndex != i) {int tmp = list[i];
list[i] = list[maxIndex];
list[maxIndex] = tmp;
}
}
return list;
}
// 替换元素。void swap(int[] list, int a, int b) {int tmp = list[a];
list[a] = list[b];
list[b] = tmp;
}
4. 代码阐明
以 无序序列 a = [1,3,4,5,2]
为例,通过堆排序失去的排好序的数组是 a = [1,2,3,4,5]
(也能够降序排列)。从此能够看出,把堆排序看成一个处理过程,那堆排序的输出是一个无序数组(链表不能够),输入是一个有序数组。这里以大根堆为例
堆排序
一个无序序列 a = [1,3,4,5,2]
,看出齐全二叉树的物理存储构造。先建成一个初始的大根堆,建堆实现之后,数组是一个大根堆 a = [5,3,4,1,2]
。建堆实现之后,就须要将大根堆顺次调整为有序序列 a = [1,2,3,4,5]
。
4.1 建堆
建堆的过程,就是从最初一个父节点开始,把每一棵树调整为堆的过程。
int[] build(int[] list, int end) {
// 从最初一个父节点开始
for (int i = (end - 1)/2; i >= 0; i--) {adjust(list, i, end);
}
return list;
}
首先来看一下,如果将一个无序序列建成大根堆。a = [1,3,4,5,2]
画成齐全二叉树之后,最初一个父节点是 [3]
。从二叉树的最初一个父节点 [3]
开始,顺次向前遍历每一个父节点,直到根节点 [1]
为止。
从最初一个父节点开始要做什么事件呢??
以以后父节点为根节点的二叉树,也就是 [3,5,2]
,将其调整为大根堆。
最初一个父节点的下标怎么计算??
节点下标是节点在数组中的地位,所以是从 0
到 array.length - 1
。
如果一个节点下标是 i
,那么它的左子叶节点下标是 2*i+1
,右子叶节点下标是 2*i+2
。
所以,如果数组中最初一个父节点下标为 i
,最初一个元素下标是 end
,那么,最初一个元素肯定是最初一个父节点的子节点。所以,就有 2*i+1 <= end
和 2*i+2 <= end
,所以能够失去最初一个父节点的下标是 (end-1)/2
。
建堆为什么是从最初一个父节点 (array.length-1)/2
开始向前遍历,而不是从 array.length-1
开始?
因为要保障调整堆时的参数是有意义的,没有越界产生。调整堆的代码中并没有判断下标是否非法。
建堆的程序是按档次遍历的程序遍历的,数组按从 (array.length-1)/2
到 0
拜访,是按档次遍历的形式向前遍历的。
4.2 调整堆
调整堆的过程,就是把堆顶元素放在适合的地位。
// 调整堆的起始、终止地位要是无效的
int[] adjust(int[] list, int start, int end) {
int maxIndex, left, right;
for (int i = start; i <= (end - 1) / 2; i++) {
maxIndex = i;
left = 2 * i + 1;
right = 2 * i + 2;
if (left <= end && list[left] > list[maxIndex]) maxIndex = left;
if (right <= end && list[right] > list[maxIndex]) maxIndex = right;
if (maxIndex != i) {int tmp = list[i];
list[i] = list[maxIndex];
list[maxIndex] = tmp;
}
}
return list;
}
将哪个区间内的元素调整为堆??
[start, end]
,蕴含左右两个下标的元素。因为调整堆的代码中并没有判断数组下标的合法性,所以传入的参数要是非法的。
怎么调整??
首先,调整的前提是,这个树满足堆的性质,除了堆顶元素。
1)找出左右子节点中的最大值,而后和堆顶元素比拟。
- 如果堆顶元素较大,则不必替换。
- 如果孩子节点较大,则将堆顶元素和较大的孩子节点替换。
2)持续调整下一个节点
调整的程序是按档次遍历的程序遍历的,数组按从 0
到 array.length-1
拜访,是按档次遍历的形式遍历的。