Hello算法8：堆

定义

堆heap是满足特定条件的完全二叉树(只有最底层节点未填满，且节点靠左填充)，主要有以下两种：

大顶堆：任意节点的值≥其子节点的值

小顶堆：任意节点的值≤子节点的值

在这里插入图片描述

堆的常用操作

方法名	描述	时间复杂度
push()	元素入堆	O(log⁡n)
pop()	堆顶元素出堆	O(log⁡n)
peek()	访问堆顶元素（对于大 / 小顶堆分别为最大 / 小值）	O(1)
size()	获取堆的元素数量	O(1)
isEmpty()	判断堆是否为空	O(1)

在实际应用中，我们可以直接使用编程语言提供的堆类（或优先队列类）。

# 初始化小顶堆
min_heap, flag = [], 1
# 初始化大顶堆
max_heap, flag = [], -1

# Python 的 heapq 模块默认实现小顶堆
# 考虑将“元素取负”后再入堆，这样就可以将大小关系颠倒，从而实现大顶堆
# 在本示例中，flag = 1 时对应小顶堆，flag = -1 时对应大顶堆

# 元素入堆
heapq.heappush(max_heap, flag * 1)
heapq.heappush(max_heap, flag * 3)
heapq.heappush(max_heap, flag * 2)
heapq.heappush(max_heap, flag * 5)
heapq.heappush(max_heap, flag * 4)

# 获取堆顶元素
peek: int = flag * max_heap[0] # 5

# 堆顶元素出堆
# 出堆元素会形成一个从大到小的序列
val = flag * heapq.heappop(max_heap) # 5
val = flag * heapq.heappop(max_heap) # 4
val = flag * heapq.heappop(max_heap) # 3
val = flag * heapq.heappop(max_heap) # 2
val = flag * heapq.heappop(max_heap) # 1

# 获取堆大小
size: int = len(max_heap)

# 判断堆是否为空
is_empty: bool = not max_heap

# 输入列表并建堆
min_heap: list[int] = [1, 3, 2, 5, 4]
heapq.heapify(min_heap)

堆的实现

索引和节点的关系

由下图可知数组索引和节点的关系：

给定一个节点的索引是i，它的左子节点是2i+1，右子节点是2i+2，父节点是(i-1)/2取整除

在这里插入图片描述

def left(i: int) -> int:
    """获取左子节点的索引"""
    return 2 * i + 1

def right(i: int) -> int:
    """获取右子节点的索引"""
    return 2 * i + 2

def parent(i: int) -> int:
    """获取父节点的索引"""
    return (i - 1) // 2  # 向下整除

访问堆顶元素

显然堆顶元素就是max_heap[0]

def peek(self) -> int:
        """访问堆顶元素"""
        return self.max_heap[0]

元素入堆

首先将元素加入堆底部，由于元素的值可能大于堆中的元素，堆的结构会被破坏。所以我们需要来执行一遍检查和调整，将新元素放到合适的位置，这个操作就叫做「堆化 heapify」

def push(self, val: int):
        """元素入堆"""
        # 添加节点
        self.max_heap.append(val)
        # 从底至顶堆化
        self.sift_up(self.size() - 1)

    def sift_up(self, i: int):
        """从节点 i 开始，从底至顶堆化"""
        while True:
            # 获取节点 i 的父节点
            p = self.parent(i)
            # 当“越过根节点”或“节点无须修复”时，结束堆化
            if p < 0 or self.max_heap[i] <= self.max_heap[p]:
                break
            # 交换两节点
            self.swap(i, p)
            # 循环向上堆化
            i = p

堆顶元素出堆

由于直接删除数组首元素会改变所有数组的索引，这将破坏整个堆的结构，这会增加很多堆化操作的工作量，所以我们用以下步骤来进行
- 交换堆顶元素和堆底元素（也就是交换数组第一个元素和最后一个元素）
- 交换完成后，删除堆底元素（由于在上一步已经进行交换，实际上删除的是堆顶元素）
- 从根元素开始，从顶至底，执行堆化

堆的应用

优先队列
堆排序
选取最大的k个元素，比如销量最高的商品，热度最高的新闻等

建堆操作

很多时候，我们需要通过一个数组来建立一个堆，这就叫做建堆。

很容易想到的一个建堆的方式，就是先建立一个空堆，然后遍历数组，把数组元素加入堆尾部，然后再进行堆化操作。这样很容易理解，但是效率不高，时间复杂度是nlogn。

实际上一般用下面的方法进行建堆操作：

首先，将数组所有元素加入到堆
倒序遍历堆，依次对每个非叶节点，执行从顶到底的堆化操作

def __init__(self, nums: list[int]):
        """根据输入列表建堆"""
        self.max_heap = nums
        for i in range(self.parent(self.size()-1), -1, -1):
            self.sift_down(i)