当前位置:网站首页>堆排序详解
堆排序详解
2022-07-06 08:22:00 【故、梦】
什么是堆?
堆是一种完全二叉树「即每个节点的所在下标与满二叉树节点的下标一致」
根据堆的性质,可以将堆分成大根堆和小根堆
- 大根堆:每个节点的值大于等于它的左右孩子的值
- 小根堆:每个节点的值小于等于它的左右孩子的值
上图就是一个大根堆,我们可以将其映射到数组 array 中
根据大根堆的性质,我们很容易得到以下结论:
array[i] >= array[2 * i + 1] && array[i] >= array[2 * i + 2]
堆排序的基本思想
堆排序大体上可以分为三步:
- 将待排序的数组构建成一个大根堆,这样堆顶的元素就是最大的元素。
- 将堆顶元素和最后一个元素交换,然后将除去最后一个元素的剩下节点重新构造为一个大根堆
- 重复步骤 2 ,直至排序完成。「第一次可以得到最大的元素,第二次可以得到第二大的元素,依此类推」
类比:这个过程就像是,在一群人中找到一个最高的,让他和坐最后一排的人交换位置;然后在剩下的人中找到身高第二高的,让他和坐在倒数第二排的人交换位置;依此类推。
堆排序的详细实现
假设待排序数组 array =[5,8,2,4,3,6,7,1]
1 将待排序数组构建成一个大根堆
首先,将待排序数组变成一个完全二叉树
接下来,我们需要保证:每个节点的值比它的左右孩子的值要大。这里你可能会想,我们可以从最上层开始,比较父节点和子节点的大小关系,将较大的元素放在父节点上。这种方法看似是对的,但是我们从上往下遍历的过程中,上层的子节点可能被更大的值替换,导致部分子节点比父节点要大「即无法保证堆顶的值是最大的」。如下图所示
因此,我们必须从下到上进行比较。为此,我们需要找到最后一个父节点,然后倒叙整理父子节点的大小关系。那么该怎么找到最后一个父节点呢?因为,在大根堆中array[i] >= array[2 * i + 1] && array[i] >= array[2 * i + 2]
,所以当叶子节点坐标为 length - 1
时**「下标最大的叶子节点」**,其父节点的坐标为 (length / 2) - 1
。「根据 i * 2 + 1 = length - 1
和 i * 2 + 2 = length - 1
」
找到最后一个父节点后,比较它和左右节点的值,如果左右节点的值比它大,将左右节点的较大值与它交换;否则不进行任何操作,对于 array ,会交换 7 和 2 的位置
然后交换 8 和 5 的位置
注意,如果交换节点后,下一层的子节点比父节点要大,还要继续进行交换。
将堆顶元素和最后一个元素交换,然后将除去最后一个元素的剩下节点重新构造为一个大根堆
将堆顶元素和最后一个元素进行交换
- 重复步骤 2 ,直至排序完成。
我们用一个动态图感受一下整个过程
代码实现
Kotlin
class Solution {
fun heapSort(array: IntArray) {
if (array.isEmpty()) return
var length = array.size
buildMaxHeap(array, length)
for (i in length - 1 downTo 0) {
// 这里可以写成 downTo 1 因为到 1 时已经交换完毕
swap(array, 0, i) // 交换根顶和当前最后的元素
length--
heapify(array,0,length) // 因为交换,可能不满足大根堆的条件,对堆顶元素进行调整
}
}
private fun buildMaxHeap(array: IntArray, length: Int) {
val fatherIndex = (length / 2) + 1 // 找到最后一个父节点所在下标
for (i in fatherIndex downTo 0) {
heapify(array, i, length)
}
}
private fun swap(array: IntArray, i: Int, j: Int) {
val temp = array[i]
array[i] = array[j]
array[j] = temp
}
private fun heapify(array: IntArray, i: Int, length: Int) {
val left = 2 * i + 1 // 左节点
val right = 2 * i + 2 // 右节点
var largeIndex = i // 父节点与左右节点中的最大值对应的下标
if (left < length && array[left] > array[largeIndex]) largeIndex = left
if (right < length && array[right] > array[largeIndex]) largeIndex = right
if (largeIndex != i) {
swap(array, largeIndex, i) // 交换后,可能导致下层不是大根堆
heapify(array, largeIndex, length)
}
}
}
边栏推荐
- How to use information mechanism to realize process mutual exclusion, process synchronization and precursor relationship
- Résumé des diagrammes de description des broches de la série ESP
- Analysis of pointer and array written test questions
- leetcode刷题 (5.28) 哈希表
- Learn Arduino with examples
- Easy to use tcp-udp_ Debug tool download and use
- [research materials] 2021 China online high growth white paper - Download attached
- Restore backup data on S3 compatible storage with tidb lightning
- The Vice Minister of the Ministry of industry and information technology of "APEC industry +" of the national economic and information technology center led a team to Sichuan to investigate the operat
- C语言 - 位段
猜你喜欢
Résumé des diagrammes de description des broches de la série ESP
On the day of resignation, jd.com deleted the database and ran away, and the programmer was sentenced
tree树的精准查询
Convolution, pooling, activation function, initialization, normalization, regularization, learning rate - Summary of deep learning foundation
Analysis of pointer and array written test questions
Sort according to a number in a string in a column of CSV file
Fibonacci sequence
Nft智能合约发行,盲盒,公开发售技术实战--合约篇
NFT smart contract release, blind box, public offering technology practice -- jigsaw puzzle
2022.02.13 - NC001. Reverse linked list
随机推荐
Configuring OSPF load sharing for Huawei devices
Wireshark grabs packets to understand its word TCP segment
升级 TiDB Operator
Vocabulary notes for postgraduate entrance examination (3)
[brush questions] top101 must be brushed in the interview of niuke.com
1204 character deletion operation (2)
Pointer advanced --- pointer array, array pointer
使用 BR 恢复 S3 兼容存储上的备份数据
Colorlog combined with logging to print colored logs
Remote storage access authorization
Online yaml to CSV tool
从 CSV 文件迁移数据到 TiDB
[secretly kill little partner pytorch20 days -day01- example of structured data modeling process]
根据csv文件某一列字符串中某个数字排序
Deep learning: derivation of shallow neural networks and deep neural networks
String to leading 0
【刷题】牛客网面试必刷TOP101
Image fusion -- challenges, opportunities and Countermeasures
PLT in Matplotlib tight_ layout()
1. Color inversion, logarithmic transformation, gamma transformation source code - miniopencv from zero