Bella's Blog
0%

数据结构之堆排序

发表于 分类于 Valine：
本文字数： 1.7k 阅读时长 ≈ 2 分钟

学习数据结构之堆排序

基础知识

如下所示为一棵树
image-20240419134026766

根节点：A

叶子节点：最末端的节点，也就是没有分叉的节点，对应上图的B C H I P Q K L M N节点

树的深度（树的高度）：4（树有4层）

节点的度：E节点的度是2（E节点分了2个叉），F节点的度是3

树的度：整个树里最大的那个节点的度，对应上图就是A节点的度，即为6

孩子节点/父节点：E叫做I的父节点，I叫做E的孩子节点

子树：E I J P Q构成的是一个子树

二叉树

  • 度不超过2的树

  • 每个节点最多有2个孩子节点

  • 两个孩子节点被分为左孩子节点和右孩子节点

  • 完全二叉树：左边最下层必须满，右边满不满无所谓

二叉树的顺序存储

image-20240419141741412

如图所示，这是一个完全二叉树，对应到列表以及元素位置可以写作

image-20240419142618021

那么可以归纳：

父节点与左孩子节点的位置关系 ： i → 2i+1

image-20240419142736702

父节点与右孩子节点的位置关系： i → 2i+2

image-20240419143101222

那么已知左孩子节点或者右孩子节点位置，如何确定父节点位置：i → (i-1)/2

大根堆

定义：一个完全二叉树，满足任一节点都比其孩子节点大

image-20240419144413450

堆的向下调整

image-20240419144629292

上图所示既不是大根堆也不是小根堆

但是不看根节点的话，左右两个子树是2个有序的大根堆

image-20240419144859320

如何调整上图直到成为一个堆呢？那么相当于现在省长无法领导县长

image-20240419145404807

那就换个有能力的县长上去，换9上去

image-20240419145633256

现在县长空了，2还是无法领导8和5两个村长，那就从8和5里选8上去当县长

image-20240419145754871

现在村长空了，2还是无法领导6和4两个村民，那就从6和4里选6上去当村长

image-20240419145908922

现在到叶子节点了，那么2就是到省长被一撸到底成村民的位置了

image-20240419150034531

至此，已经把原来的完全二叉树调整为了一个大根堆了。

我自己做了以下的演示动画可以参考学习，我这里为了更形象表达，树的内容做了简单调整，但是向下调整的思想是保持不变的


至此完成了9以下元素的向下调整。

至此完成了8以下元素的向下调整。

所以可以借鉴堆排序实现排序问题，但是堆排序的前提是先要构造堆。

构造堆

思想：农村包围城市，想要省有序，必须县有序，想要县有序，必须村先有序。

至此，一个大根堆构造完成，接下来便可以采用堆排序完成整个排序。

image-20240419163907007

堆排序的过程

1. 构造堆，农村包围城市
2. 得到堆顶元素，堆顶为最大元素
3. 去掉堆顶，将最后叶子节点元素放置堆顶，通过一次向下调整使堆有序；
4. 得到堆顶为第二大元素
5. 重复步骤3，直到堆变空

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def sift(data, low, high):
    """
    调整子树至有序堆，即最大元素至堆顶
    Args:
        data (_type_): 输入树
        low (_type_): 树根节点位置
        high (_type_): 树子节点位置
    """
    i = low
    j = 2*i+1
    tmp = data[i]
    while j<= high:
        if  j+1 <= high and data[j+1] > data[j]:
            j = j+1
        if data[j]>tmp:
            data[i] = data[j]
            i = j
            j = 2*i+1
        else:
            break
    data[i]=tmp

def heap_sort(data):
    n = len(data)
    for i in range((n-2)//2, -1, -1):
        sift(data, i, n-1)
    for i in range(n-1, -1, -1):
        data[0], data[i] = data[i], data[0]
        sift(data, 0, i-1)

时间复杂度

堆排序的时间复杂度是O(nlogn)