Detailed explanation of heap sorting

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 ：

1. 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 .
2. 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
3. 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

3. 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)
        }
    }
}