Python高级数据结构——堆（Heap）

Echo_Wish

发布于 2023-11-30 19:47:14

3490

发布于 2023-11-30 19:47:14

文章被收录于专栏：数据结构和算法数据结构和算法

Python中的堆（Heap）：高级数据结构解析

堆是一种基于树结构的数据结构，具有高效的插入和删除操作。在本文中，我们将深入讲解Python中的堆，包括堆的基本概念、类型、实现方式、应用场景以及使用代码示例演示堆的操作。

基本概念

堆是一种特殊的树形数据结构，其中每个节点的值都小于或等于（最小堆）或大于或等于（最大堆）其子节点的值。堆分为最小堆和最大堆两种类型，其中：

最小堆：父节点的值小于或等于其子节点的值。
最大堆：父节点的值大于或等于其子节点的值。堆常用于实现优先队列和堆排序等算法。

堆的实现方式

在Python中，堆可以通过heapq模块实现，该模块提供了对堆的支持，包括插入、删除等操作。

import heapq

# 创建最小堆
heap = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(heap)

# 插入元素
heapq.heappush(heap, 0)

# 弹出最小元素
min_element = heapq.heappop(heap)

print("Min Heap:", heap)
print("Min Element:", min_element)

堆的应用场景

1. 优先队列

堆常用于实现优先队列，其中元素按照优先级顺序排列。在每次插入元素时，堆会自动调整以确保最高（或最低）优先级的元素位于堆的根部。

import heapq

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

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

    def pop(self):
        _, item = heapq.heappop(self.heap)
        return item

# 示例
priority_queue = PriorityQueue()
priority_queue.push("Task 1", 3)
priority_queue.push("Task 2", 1)
priority_queue.push("Task 3", 2)

print("Priority Queue:")
while len(priority_queue.heap) > 0:
    print(priority_queue.pop())

2. 堆排序

堆排序是一种原地排序算法，使用堆来进行排序操作。

import heapq

def heap_sort(arr):
    heapq.heapify(arr)
    sorted_arr = [heapq.heappop(arr) for _ in range(len(arr))]
    return sorted_arr

# 示例
unsorted_array = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_array = heap_sort(unsorted_array)

print("Unsorted Array:", unsorted_array)
print("Sorted Array:", sorted_array)