什么是堆？

堆通常是一个可以被看做一棵树的数组对象，堆总是一棵完全二叉树。

堆的特点

其中每个结点的元素都不大于其孩子结点的元素，这样的堆称为小根堆。

其中每个结点的元素都不小于其孩子结点的元素，这样的堆称为大根堆。

我们将堆数据展开就会取得如下数组：

通过关系映射我们可以推导出如下两个公式：

R 表示数组，i 表示元素下标。

Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)

如图所示：R{50 ,45 ,40 ,20 ,25 ,35 ,30 ,10 ,15} 是一个典型的大根堆，堆中有4个父节点{50,45,40,20}。

元素50用R[0]表示，他拥有两个子节点R[1]、R[2]
元素45用R[1]表示，他拥有两个子节点R[3]、R[4]，父节点R[0]
元素40用R[2]表示，他拥有两个子节点R[5]、R[6]，父节点R[0]
元素20用R[3]表示，他拥有两个子节点R[7]、R[8]，父节点R[1]

可以看出，它们满足以下规律：

设当前元素在数组中以R[i]表示，那么，

它的左孩子结点是：R[2*i+1];
它的右孩子结点是：R[2*i+2];
它的父结点是：R[(i-1)/2];
R[i] >= R[2*i+1] 且 R[i] >= R[2i+2]。

堆排序

堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。

实现流程

元数据： [7 8 3 6 0 2 1 4 5 9]

构建堆以后： [9 8 3 6 7 2 1 4 5 0]

第 1 次调整堆后：[8 7 3 6 0 2 1 4 5 9]

第 2 次调整堆后：[7 6 3 5 0 2 1 4 8 9]

第 3 次调整堆后：[6 5 3 4 0 2 1 7 8 9]

第 4 次调整堆后：[5 4 3 1 0 2 6 7 8 9]

第 5 次调整堆后：[4 2 3 1 0 5 6 7 8 9]

第 6 次调整堆后：[3 2 0 1 4 5 6 7 8 9]

第 7 次调整堆后：[2 1 0 3 4 5 6 7 8 9]

第 8 次调整堆后：[1 0 2 3 4 5 6 7 8 9]

第 9 次调整堆后：[0 1 2 3 4 5 6 7 8 9]

排序后： [0 1 2 3 4 5 6 7 8 9]

逻辑动画

堆排序

代码实现

GO

package main

import (
    "fmt"

    "gitee.com/wolferhua/gostudy/algorithm/utils"
)

func main() {
    numbers := utils.GetRandSlices(10, 4) // []int{3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6}
    fmt.Println("元数据：",numbers)
    HeapSort(numbers)
}

func HeapSort(arr []int) {
    length := len(arr)

    //初始化，i从最後一个父节点开始调整，构建初始堆。
    for i := length/2 - 1; i >= 0; i-- {
        // fmt.Println("==============================================")
        // fmt.Println(i, length-1)
        MaxHeapify(arr, i, length-1)
    }
    fmt.Println("构建堆以后：",arr)
    //先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕
    count:=0
    for i := length - 1; i > 0; i-- {
        //swap(&arr[0], &arr[i]);
        // fmt.Println("==============================================")
        // fmt.Println(i - 1)
        arr[0], arr[i] = arr[i], arr[0]
        MaxHeapify(arr, 0, i-1)
        count++

        fmt.Printf("第 %d 次调整堆后：%v\n",count,arr)
    }
    // fmt.Println(arr)

    fmt.Println("排序后：",arr)
}

func MaxHeapify(arr []int, start, end int) {
    //建立父节点指标和子节点指标
    dad := start
    son := dad*2 + 1
    for son <= end { //若子节点指标在范围内才做比较
        if son+1 <= end && arr[son] < arr[son+1] { //先比较两个子节点大小，选择最大的
            son++
        }
        if arr[dad] > arr[son] { //如果父节点大於子节点代表调整完毕，直接跳出函数
            return
        } else { //否则交换父子内容再继续子节点和孙节点比较
            // fmt.Printf("dad=%d,son=%d\n\n", dad, son)
            // fmt.Println(arr)
            arr[dad], arr[son] = arr[son], arr[dad]
            dad = son
            son = dad*2 + 1
        }
    }
}

Python

# -*- coding: UTF-8 -*-
numbers = [7, 8, 3, 6, 0, 2, 1, 4, 5, 9]
print("元数据：",numbers)

def max_heapify(nums,lo,hi):
    dad = lo         # 父节点的位置
    son = 2 * dad + 1   # 子节点的位置
    tmp = nums[lo]   # 最原来的根的值
    while son <= hi: #若子节点指标在范围内才做比较
        if son + 1 <= hi and nums[son+1] > nums[son]: # 如果右孩子存在并且右孩子更大
            son += 1
        if tmp < nums[son]: # 如果最原来的根的值比孩子小
            nums[dad] = nums[son]  # 把孩子向上移动一层
            dad = son
            son = 2 * dad + 1
        else:
            break
    nums[dad] = tmp# 最原来的根的值放到对应的位置上(叶子节点)

def heap_sort(nums):
    length = len(nums) # 数组长度
    # 构建堆
    for i in range(length//2-1,-1,-1):
        max_heapify(nums,i,length-1)
    
    #  排序
    for l in range(length-1, -1, -1):    # l表示堆最后一个元素的位置
        nums[0], nums[l] = nums[l], nums[0]
        # 堆的大小少了一个元素 （l-1）
        max_heapify(nums, 0, l-1)

 

heap_sort(numbers)
print( "排序后：",numbers )

长按二维码关注我们