python堆-完全二叉树--完全解读

• 作者：20岁爱吃必胜客（坤制作人），近十年开发经验, 跨域学习者，目前于海外某世界知名高校就读计算机相关专业。
• 荣誉：阿里云博客专家认证、腾讯开发者社区优质创作者，在CTF省赛校赛多次取得好成绩。
• 跨领域学习，喜欢摄影、弹吉他、咏春拳。文章深入浅出、语言风趣；爱吃必胜客社区创立者，旨在“发现美 欣赏美

---

• 🏆 学习系列专栏
  。🏅 Python学习宝库
  。🏅 网络安全学习宝库

、

??堆

Python中的堆是通过heapq模块实现的。这个模块提供了一种高效的方式来创建和管理堆数据结构。堆是一种二叉树，其中树完全填充，只有最底层可能从左到右不完全填充。

为什么使用 heapq?

Python的heapq模块使用普通列表实现了最小堆。最小堆确保最小的元素始终在根部（即heap[0]）。heapq模块提供了操作堆的函数，同时保持堆属性不变。

它是如何工作的？

在底层，heapq利用了二叉堆的属性。二叉堆是一个完全二叉树，满足堆属性。在最小堆中，父节点小于其子节点。这个属性对于每个节点都必须是真的，这使得根部成为堆中最小的元素。

使用heapq的基本操作

创建堆：

你从一个空列表开始，然后使用heapq.heappush()添加元素。这个函数添加元素的同时重新排列堆，以保持堆属性。

import heapq

minHeap = []
heapq.heappush(minHeap, 3)
heapq.heappush(minHeap, 1)
heapq.heappush(minHeap, 2)

这些操作之后，minHeap将会是[1, 3, 2]。最小元素（1）在根部。

访问最小元素：

最小元素始终可以在minHeap[0]找到。这是一个常数时间操作。

移除最小元素：

使用heapq.heappop()来移除并返回最小元素。这个操作也会重新排列堆以保持其属性。

smallest_element = heapq.heappop(minHeap)  # 移除并返回 '1'

Heapify：

如果你有一个现有列表，你可以使用heapq.heapify()将其转换为堆。这会重新排列元素以满足堆属性。

some_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(some_list)

现在some_list是一个堆

效率

堆在不断需要访问最小（或在最大堆的情况下是最大）元素的任务中非常高效，插入和删除的时间复杂度为O(log n)，访问最小元素的时间复杂度为O(1)。

应用

堆被用在算法中，如堆排序，在优先队列中，用于高效地找到列表中的第k个最小/最大元素，以及在图算法中，如迪杰斯特拉（Dijkstra）最短路径算法。

当然可以。我会给出几个Python中使用heapq模块的示例代码，以展示堆的一些常见应用。

1. 堆排序（Heap Sort）

import heapq

def heap_sort(nums):
    heapq.heapify(nums)  # 将列表转换为堆
    return [heapq.heappop(nums) for _ in range(len(nums))]

# 示例
nums = [3, 1, 4, 1, 5, 9, 2, 6, 5]
sorted_nums = heap_sort(nums)
print(sorted_nums)

2. 使用堆实现优先队列

import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []

    def push(self, item, priority):
        heapq.heappush(self.heap, (priority, item))

    def pop(self):
        return heapq.heappop(self.heap)[1]

# 示例
pq = PriorityQueue()
pq.push('任务1', 3)
pq.push('任务2', 1)
pq.push('任务3', 2)

while pq.heap:
    print(pq.pop())

3. 查找列表中第k个最小元素

import heapq

def kth_smallest(nums, k):
    return heapq.nsmallest(k, nums)[-1]

# 示例
nums = [3, 1, 4, 1, 5, 9, 2, 6, 5]
k = 4
print(kth_smallest(nums, k))

4. 使用堆实现Dijkstra算法（简化版）

import heapq

def dijkstra(graph, start):
    # 初始化距离表，所有距离设为无穷大
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    # 创建一个优先队列，并把起始顶点放入队列中
    pq = [(0, start)]
    
    while pq:
        current_distance, current_vertex = heapq.heappop(pq)

        # 跳过处理已经找到更短路径的节点
        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            # 更新距离表
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

# 示例图
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

print(dijkstra(graph, 'A'))

这些示例覆盖了堆的一些基本用法，包括排序、优先队列、查找特定元素和图算法。通过这些示例，可以更好地理解堆的实用性和在算法中的应用。

您给出的这个结构是一个图的表示方式，

具体来说，它是一个带权重的有向图的字典表示形式。在这个字典中，每个键（例如 ‘A’, ‘B’, ‘C’, ‘D’）代表图中的一个顶点，而与每个键相关联的字典则表示从该顶点出发到其他顶点的边及其相应的权重。

这种表示方式非常适合用来描述图的结构，特别是当你需要实现图的算法（如路径查找、网络流分析等）时。这里是如何解读这个图：

顶点 ‘A’ 有两条边，一条通向 ‘B’，权重为 1，另一条通向 ‘C’，权重为 4。
顶点 ‘B’ 有三条边，分别通向 ‘A’（权重为 1）、‘C’（权重为 2）和 ‘D’（权重为 5）。
顶点 ‘C’ 有三条边，分别通向 ‘A’（权重为 4）、‘B’（权重为 2）和 ‘D’（权重为 1）。
顶点 ‘D’ 有两条边，一条通向 ‘B’，权重为 5，另一条通向 ‘C’，权重为 1。
这种表示法是图论和网络分析中常用的，尤其是在编程和算法设计时。例如，你可以用这个图来实现Dijkstra算法，寻找从一个顶点到另一个顶点的最短路径。

kth_smallest 使用了 Python 的 heapq 模块来找到一个列表中第 k 个最小的元素。这个函数的工作原理如下：

1. heapq.nsmallest(k, nums)：这个函数调用从 nums 列表中找到 k 个最小的元素。内部实现上，它首先将列表转换成一个最小堆，然后一次取出最小元素直到取出 k 个。

2. [-1]：这部分从由 nsmallest 返回的列表中取出最后一个元素。由于这个列表是有序的，最后一个元素就是这 k 个最小元素中最大的一个，也就是整个列表中第 k 个最小的元素。

这个函数的时间复杂度取决于 heapq.nsmallest 函数的实现，通常情况下这个操作的时间复杂度是 O(n log k)，其中 n 是列表 nums 的长度。

这里是一个使用示例：

import heapq

def kth_smallest(nums, k):
    return heapq.nsmallest(k, nums)[-1]

# 示例
nums = [3, 1, 4, 1, 5, 9, 2, 6, 5]
k = 4
print(kth_smallest(nums, k))  # 输出第4个最小的元素

在这个例子中，kth_smallest(nums, k) 会返回列表 nums 中第 4 个最小的元素。