许多计算任务,特别是在优化和算法设计中,都涉及根据优先级管理元素。无论是查找最相关的 k 个项、调度任务,还是实现某些图算法,我们通常都需要高效地访问具有最高或最低优先级的项。本章将重点介绍堆,这是一种专门的、基于树的数据结构,旨在精确地实现此目的。我们将考察堆如何保持其结构特性,以便快速插入和提取最小或最大元素,这些操作通常达到 $O(\log n)$ 的时间复杂度。您将学习到:最小堆和最大堆的定义特性。实现重要的堆操作:插入、提取和构建堆(heapify)。将堆用作优先队列的底层结构。应用堆来高效解决选择问题(例如,查找第 k 个最小/最大值)。认识到优先队列如何提高 Dijkstra 最短路径等算法的效率。使用 Python 的 heapq 模块进行实际的堆管理。完成本章将使您具备在机器学习场景中处理相关优化问题时有效应用堆和优先队列的知识。