blog | percy

life

0%

数据结构之堆

发表于 更新于 分类于

[TOC]

概述

堆是一种特殊的树，只要满足下面两个条件，它就是一个堆：

  • 堆是一颗完全二叉树；
  • 堆中某个节点的值总是不大于（或不小于）其父节点的值。

其中，我们把根节点最大的堆叫做大顶堆，根节点最小的堆叫做小顶堆。

二叉树概念

  • 满二叉树是指所有层都达到最大节点数的二叉树。
  • 完全二叉树是指除了最后一层其它层都达到最大节点数，且最后一层节点都靠左排列。

我们可以看见，完全二叉树的节点都是比较紧凑的，且只有最后一层是不满的，所以使用数组是最节省空间的。

堆

堆也是一颗完全二叉树，但是它的元素必须满足每个节点的值都不大于（或不小于）其父节点的值。比如下面这个堆：

yOPA3D.png

堆的实现

插入元素

在完全二叉树中，插入的节点与它的父节点相比，如果比父节点小，就交换它们的位置，再往上和父节点相比，如果比父节点小，再交换位置，直到比父节点大为止。

在数组中，插入的节点与n/2位置的节点相比，如果比n/2位置的节点小，就交换它们的位置，再往前与n/4位置的节点相比，如果比n/4位置的节点小，再交换位置，直到比n/(2^x)位置的节点大为止。

这就是插入元素时进行的堆化，也叫自下而上的堆化。

从插入元素的过程，我们知道每次与n/(2^x)的位置进行比较，所以，插入元素的时间复杂度为O(log n)。

删除堆顶元素

只能删除堆顶元素，不能删除其他位置的元素，其他位置实际上都是乱序的，只有堆顶能保证是最大或者最小

建堆

假定给定一组乱序的数组，我们该怎么建堆呢？

如下图所示，我们模拟依次往堆中添加元素。

（1）插入6这个元素，只有一个，不需要比较；

（2）插入8这个元素，比6大，不需要交换；

（3）插入3这个元素，比下标3/2=1的位置上的元素6小，交换位置；

（4）插入2这个元素，比下标4/2=2的位置上的元素8小，交换位置，比下标2/2=1的位置上的元素3小，交换位置；

（5）…

（10）最后，全部插入完成，即完成了建堆的过程。

堆排序

我们直接把堆顶的元素与第n个元素交换位置，再把前(n-1)个元素堆化，再把堆顶元素与第(n-1)个元素交换位置，
再把前(n-2)个元素堆化，..，，进行下去，最后，数组中的元素就整个变成倒序的了，也就排序完了。

堆使用

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
#  默认小顶堆（最小堆）
def demo():
    import heapq

    q = []

    heapq.heappush(q, (2, 'code'))
    heapq.heappush(q, (1, 'eat'))
    heapq.heappush(q, (3, 'sleep'))

    while q:
        next_item = heapq.heappop(q)
        print(next_item)
        
def minHeap():
    arr = []
    for i in range(20, -1, -1):
        heapq.heappush(arr, i)
    print(arr[0] == 0)


def maxHeap():
    arr = []
    N = 20
    for i in range(N, -1, -1):
        heapq.heappush(arr, -i)
    print(-arr[0] == N)

参考

拜托，面试别再问我堆（排序）了！

https://leetcode-cn.com/circle/article/bNtb4J/

https://cloud.tencent.com/developer/article/1163053

https://studygolang.com/articles/24288