当前位置:网站首页>堆排序详解
堆排序详解
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)
}
}
}
边栏推荐
- 1204 character deletion operation (2)
- vulnhub hackme: 1
- How to use information mechanism to realize process mutual exclusion, process synchronization and precursor relationship
- logback1.3. X configuration details and Practice
- NFT smart contract release, blind box, public offering technology practice -- contract
- String to leading 0
- wincc7.5下载安装教程(Win10系统)
- 在 uniapp 中使用阿里图标
- 【MySQL】锁
- Leetcode question brushing record | 203_ Remove linked list elements
猜你喜欢
【云原生】手把手教你搭建ferry开源工单系统
Artcube information of "designer universe": Guangzhou implements the community designer system to achieve "great improvement" of urban quality | national economic and Information Center
将 NFT 设置为 ENS 个人资料头像的分步指南
IoT -- 解读物联网四层架构
Nft智能合约发行,盲盒,公开发售技术实战--合约篇
Configuring OSPF load sharing for Huawei devices
Easy to use tcp-udp_ Debug tool download and use
[research materials] 2021 live broadcast annual data report of e-commerce - Download attached
From monomer structure to microservice architecture, introduction to microservices
ESP系列引脚说明图汇总
随机推荐
Verrouillage [MySQL]
指针进阶---指针数组,数组指针
"Designer universe" APEC design +: the list of winners of the Paris Design Award in France was recently announced. The winners of "Changsha world center Damei mansion" were awarded by the national eco
Go learning notes (3) basic types and statements (2)
Nft智能合约发行,盲盒,公开发售技术实战--合约篇
Yyds dry goods inventory three JS source code interpretation eventdispatcher
Colorlog结合logging打印有颜色的日志
How to use information mechanism to realize process mutual exclusion, process synchronization and precursor relationship
Zhong Xuegao, who cannot be melted, cannot escape the life cycle of online celebrity products
面向个性化需求的在线云数据库混合调优系统 | SIGMOD 2022入选论文解读
Chinese Remainder Theorem (Sun Tzu theorem) principle and template code
Use dumping to back up tidb cluster data to S3 compatible storage
根据csv文件某一列字符串中某个数字排序
Nft智能合约发行,盲盒,公开发售技术实战--拼图篇
Résumé des diagrammes de description des broches de la série ESP
LDAP Application Section (4) Jenkins Access
1204 character deletion operation (2)
Tidb backup and recovery introduction
Golang DNS write casually
[cloud native] teach you how to build ferry open source work order system