堆与优先队列

相关源文件

• data_structures/binary_tree/merge_two_binary_trees.py
• data_structures/heap/heap.py
• data_structures/linked_list/skip_list.py
• divide_and_conquer/convex_hull.py
• graphs/dijkstra_algorithm.py
• hashes/sha256.py
• machine_learning/linear_discriminant_analysis.py
• project_euler/problem_047/sol1.py
• sorts/bead_sort.py
• sorts/bucket_sort.py
• sorts/cocktail_shaker_sort.py
• sorts/gnome_sort.py
• sorts/odd_even_transposition_single_threaded.py
• sorts/topological_sort.py
• sorts/wiggle_sort.py
• strings/boyer_moore_search.py
• strings/knuth_morris_pratt.py
• strings/prefix_function.py
• strings/rabin_karp.py
• strings/top_k_frequent_words.py

本文档涵盖了 TheAlgorithms/Python 仓库中堆数据结构和优先队列的实现。堆是满足堆属性的特化树状数据结构，而优先队列是可以使用堆高效实现的抽象数据类型。

堆与优先队列概述

堆是完全二叉树，其中每个节点与其子节点之间满足特定的排序属性。优先队列是抽象数据类型，它维护一个元素集合，每个元素都有一个关联的优先级，允许高效地访问最高优先级的元素。

堆类型

1. 最大堆：每个节点的值大于或等于其子节点的值
2. 最小堆：每个节点的值小于或等于其子节点的值

堆与优先队列之间的关系

仓库中的最大堆示例

来源：data_structures/heap/heap.py25-46 graphs/dijkstra_algorithm.py11-29

仓库中的堆实现

该仓库提供了两种不同的堆实现，服务于不同的目的

最大堆实现（data_structures.heap.heap.Heap）

一个通用的最大堆实现，用于通用的堆操作和堆排序。

最小堆优先队列（graphs.dijkstra_algorithm.PriorityQueue）

一个最小堆实现，专门为需要优先队列操作的图算法设计。

两个实现都使用了

• 基于数组表示的二叉树
• 基于索引的导航方法
• 类型安全和比较协议

来源：data_structures/heap/heap.py1-24 data_structures/heap/heap.py25-50 graphs/dijkstra_algorithm.py11-29

堆操作

堆实现包含以下关键操作

导航方法

这些方法计算导航堆数组的索引

• parent_index：查找给定节点的父节点
• left_child_idx：查找给定节点的左子节点
• right_child_idx：查找给定节点的右子节点

来源：data_structures/heap/heap.py55-109

构建堆

build_max_heap 方法通过从数组中间到根应用 max_heapify 操作，将未排序的数组转换为最大堆。

来源：data_structures/heap/heap.py134-163

最大堆化

max_heapify 方法通过递归交换值来恢复最大堆属性，从而纠正子树根节点中堆属性的单一违反。

来源：data_structures/heap/heap.py111-132

提取最大值和插入

• extract_max：从堆中移除并返回最大元素（根）
• insert：将新值添加到堆中并维护堆属性

来源：data_structures/heap/heap.py165-194 data_structures/heap/heap.py196-230

堆排序

heap_sort 方法通过重复从堆中提取最大元素来以降序对数组进行排序。

来源：data_structures/heap/heap.py232-238

优先队列操作

优先队列是支持以下关键操作的抽象数据类型

核心优先队列操作

操作	描述	时间复杂度
insert(item, priority)	添加具有给定优先级的项	O(log n)
extract_min() / extract_max()	移除并返回最高优先级的项	O(log n)
decrease_key(item, new_priority)	更新项的优先级	O(log n)
is_empty()	检查队列是否为空	O(1)

PriorityQueue 实现细节

Dijkstra 算法中的 PriorityQueue 类实现了最小堆，用于计算最短路径

优先队列数据结构映射

来源：graphs/dijkstra_algorithm.py11-29 graphs/dijkstra_algorithm.py44-97 graphs/dijkstra_algorithm.py99-141

堆与优先队列的应用

图算法应用

Dijkstra 最短路径算法

Top K Frequent Words 实现

用于堆操作的 WordCount 实现

WordCount 类演示了如何使自定义对象与堆一起工作

来源：strings/top_k_frequent_words.py22-65 strings/top_k_frequent_words.py67-94 graphs/dijkstra_algorithm.py289-387

性能特征

堆操作复杂度

操作	时间复杂度	空间复杂度
build_max_heap()	O(n)	O(1) 辅助空间
extract_max()	O(log n)	O(1) 辅助空间
insert()	O(log n)	O(1) 辅助空间
max_heapify()	O(log n)	O(log n) 递归
heap_sort()	O(n log n)	O(1) 辅助空间

优先队列操作复杂度

操作	PriorityQueue 实现	时间复杂度
insert()	添加元素并上浮	O(log n)
extract_min()	移除根并堆化	O(log n)
decrease_key()	更新优先级并上浮	O(log n)
is_empty()	检查大小	O(1)
min_heapify()	恢复堆属性	O(log n)

空间复杂度：O(n)，其中 n 是堆/优先队列中存储的元素数量。

优化说明:

• PriorityQueue 中的 pos 字典支持 decrease_key() 操作的 O(1) 元素查找
• 基于数组的表示提供了缓存友好的内存访问模式
• 两个实现都在可能的情况下避免了递归关键路径

来源：data_structures/heap/heap.py134-163 data_structures/heap/heap.py165-194 graphs/dijkstra_algorithm.py44-97

实现架构

基于索引的树导航

两个堆实现都使用基于数组的二叉树表示，具有标准的索引计算

实现比较

功能	Heap（最大堆）	PriorityQueue（最小堆）
主要用途	通用堆操作、堆排序	图算法（Dijkstra）
堆类型	最大堆	最小堆
元素类型	通用 T，具有 Comparable	元组 （distance, node）
主要功能	heap_sort() 方法	decrease_key() 操作
位置跟踪	无	用于 O(1) 查找的 pos 字典

类型安全和泛型设计

最大堆泛型实现

优先队列专用实现

来源: data_structures/heap/heap.py48-50 data_structures/heap/heap.py55-109 graphs/dijkstra_algorithm.py26-28 graphs/dijkstra_algorithm.py183-223

结论

堆是一种多功能的数据结构，可有效支持查找最大/最小元素、插入和删除等操作。此存储库中的实现为需要这些操作的各种算法提供了坚实的基础。

堆数据结构在整个代码库中用于优先队列、图算法和排序等应用程序。理解堆的实现对于高效地使用这些算法至关重要。