Hello算法8：堆

Hello算法8：堆

定义

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

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

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

堆的常用操作

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

# 初始化小顶堆
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)

堆的实现

1. 索引和节点的关系

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

   给定一个节点的索引是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  # 向下整除
   

2. 访问堆顶元素

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

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

3. 元素入堆

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

4. 堆顶元素出堆

   由于直接删除数组首元素会改变所有数组的索引，这将破坏整个堆的结构，这会增加很多堆化操作的工作量，所以我们用以下步骤来进行

   • 交换堆顶元素和堆底元素（也就是交换数组第一个元素和最后一个元素）
   • 交换完成后，删除堆底元素（由于在上一步已经进行交换，实际上删除的是堆顶元素）
   • 从根元素开始，从顶至底，执行堆化

堆的应用

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

建堆操作

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

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

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

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

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)

经数学证明，这种方式的时间复杂度是O(n)

堆的应用-Topk问题

返回数组中最大的k个元素

方法一：遍历选择

对数据进行遍历，每次找到一个第n大的元素。时间复杂度是O(kn)，如果k比较接近n，时间复杂度是O(n^2)

方法二：排序

显然我们可以对数组排序，然后返回后K个元素。这种算法显然超额完成任务了，因为并不需要对数组所有元素进行排序

方法三：借助堆实现

思路如下：

建立一个小顶堆，堆顶元素为最小

先将数组前k个元素依次入堆

从第k+1个元素开始，若当前元素大于堆顶元素，堆顶元素出堆，该元素入堆

遍历完成后，堆中保存的就是最大的k个元素