当前位置:网站首页>Detailed explanation of heap sorting
Detailed explanation of heap sorting
2022-07-06 08:35:00 【So, dream】
What is a heap ?
A heap is a complete binary tree 「 That is, the subscript of each node is consistent with that of the full binary tree node 」
Depending on the nature of the heap , You can divide the heap into Big root pile and Heap
- Big root pile : The value of each node is greater than or equal to the value of its left and right children
- Heap : The value of each node is less than or equal to the value of its left and right children
Above is a big pile , We can map it to an array array in
According to the nature of big root pile , We can easily draw the following conclusion :
array[i] >= array[2 * i + 1] && array[i] >= array[2 * i + 2]
The basic idea of heap sorting
Heap sorting can be roughly divided into three steps :
- Build the array to be sorted into a large root heap , In this way, the element at the top of the heap is the largest element .
- Exchange the top element with the last element , then The last element will be removed The remaining nodes of are reconstructed into a large root heap
- Repeat step 2 , Until the sorting is complete .「 You can get the largest element for the first time , The second time you can get the second largest element , And so on 」
analogy : The process is like , Find the tallest one in a group , Let him exchange seats with the people in the last row ; Then find the second tallest among the rest , Let him exchange seats with the person sitting in the penultimate row ; And so on .
Detailed implementation of heap sorting
Suppose the array to be sorted array =[5,8,2,4,3,6,7,1]
1 Build the array to be sorted into a large root heap
First , Turn the array to be sorted into a complete binary tree
Next , We need to make sure : The value of each node is larger than that of its left and right children . Here you might think , We can start from the top , Compare the size relationship between parent and child nodes , Put the larger element on the parent node . This method seems to be right , But in the process of traversing from top to bottom , The child nodes of the upper layer may be replaced by larger values , As a result, some child nodes are larger than their parent nodes 「 That is, the maximum value at the top of the heap cannot be guaranteed 」. As shown in the figure below
therefore , We must compare from bottom to top . So , We need to find the last parent node , Then flashback to sort out the size relationship between parent and child nodes . So how to find the last parent node ? because , In the big pile array[i] >= array[2 * i + 1] && array[i] >= array[2 * i + 2]
, So when the leaf node coordinates are length - 1
when **「 The leaf node with the largest subscript 」**, The coordinates of its parent node are (length / 2) - 1
.「 according to i * 2 + 1 = length - 1
and i * 2 + 2 = length - 1
」
After finding the last parent node , Compare it with the values of the left and right nodes , If the value of the left and right nodes is greater than it , Exchange the larger value of the left and right nodes with it ; Otherwise, no operation will be carried out , about array , Will exchange 7 and 2 The location of
Then exchange 8 and 5 The location of
Be careful , If after switching nodes , The child node of the next layer is larger than the parent node , Continue to exchange .
Exchange the top element with the last element , then The last element will be removed The remaining nodes of are reconstructed into a large root heap
Swap the top element with the last element
- Repeat step 2 , Until the sorting is complete .
Let's use a dynamic graph to feel the whole process
Code implementation
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) {
// This can be written as downTo 1 Because of 1 Time has been exchanged
swap(array, 0, i) // Swap the root top and the current last element
length--
heapify(array,0,length) // Because of the exchange , The condition of large root heap may not be met , Adjust the top element
}
}
private fun buildMaxHeap(array: IntArray, length: Int) {
val fatherIndex = (length / 2) + 1 // Find the subscript of the last parent node
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 // The left node
val right = 2 * i + 2 // Right node
var largeIndex = i // The subscript of the parent node corresponding to the maximum value in the left and right nodes
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) // After exchanging , It may cause that the lower layer is not a big pile
heapify(array, largeIndex, length)
}
}
}
边栏推荐
- 【Nvidia开发板】常见问题集 (不定时更新)
- 2022 Inner Mongolia latest water conservancy and hydropower construction safety officer simulation examination questions and answers
- Purpose of computer F1-F12
- pcd转ply后在meshlab无法打开,提示 Error details: Unespected eof
- 深度剖析C语言数据在内存中的存储
- China high purity silver nitrate Market Research and investment strategy report (2022 Edition)
- View computer devices in LAN
- C语言深度解剖——C语言关键字
- 2022 Inner Mongolia latest construction tower crane (construction special operation) simulation examination question bank and answers
- egg. JS directory structure
猜你喜欢
【MySQL】日志
Verrouillage [MySQL]
Mobile phones and computers on the same LAN access each other, IIS settings
The resources of underground pipe holes are tight, and the air blowing micro cable is not fragrant?
Image, CV2 read the conversion and size resize change of numpy array of pictures
[secretly kill little partner pytorch20 days -day01- example of structured data modeling process]
Circular reference of ES6 module
704 二分查找
2022 Inner Mongolia latest water conservancy and hydropower construction safety officer simulation examination questions and answers
Configuring OSPF load sharing for Huawei devices
随机推荐
leetcode刷题 (5.28) 哈希表
CISP-PTE实操练习讲解
marathon-envs项目环境配置(强化学习模仿参考动作)
化不掉的钟薛高,逃不出网红产品的生命周期
Indentation of tabs and spaces when writing programs for sublime text
【MySQL】日志
Crash problem of Chrome browser
[2022 广东省赛M] 拉格朗日插值 (多元函数极值 分治NTT)
C language double pointer -- classic question type
Golang force buckle leetcode 1020 Number of enclaves
企微服务商平台收费接口对接教程
Research Report on Market Research and investment strategy of microcrystalline graphite materials in China (2022 Edition)
Let the bullets fly for a while
Purpose of computer F1-F12
2022.02.13 - NC003. Design LRU cache structure
sys. argv
【MySQL】锁
Colorlog combined with logging to print colored logs
VMware virtualization cluster
Modify the video name from the name mapping relationship in the table