堆（Heap）
## 📖 核心概念 堆是一种特殊的完全二叉树，通常用数组来实现。它满足堆性质：任意节点的值总是不大于（大顶堆）或不小于（小顶堆）其子节点的值。堆是一种高效的数据结构，用于实现优先队列，支持快速的插入、删除和查找最大（或最小）元素操作。 ## 🔤 术语信息 - 英文名称：Heap（无常用缩写） - 中文别名：无 - 相关术语对比：与栈和队列不同，堆不遵循先进先出（FIFO）原则，而是根据元素的优先级（通常是大小）来组织数据。 ## 🛠️ 工作原理 堆通过数组实现，数组的索引与树的节点位置相对应。对于给定的节点i，其左子节点和右子节点的索引分别为2i+1和2i+2。堆操作包括插入、删除最大（或最小）元素以及堆化（将无序数组转换为堆）。关键技术要点包括维护堆性质和通过上浮（sift-up）和下沉（sift-down）操作调整节点位置。 ## 💡 实际应用 1. **排序算法**：堆排序利用堆结构对元素进行排序，时间复杂度为O(n log n)。 2. **优先队列实现**：在需要根据优先级处理任务的场景中，堆提供了一种高效的实现方式。 3. **图算法**：在Dijkstra算法中，堆用于存储待访问的顶点，以快速找到最短路径。 4. **资源调度**：在操作系统中，堆可用于动态内存分配，快速响应内存请求。 ## 🎓 学习要点 学习堆之前，需要理解数组和树的基本概念。重点掌握堆的性质、堆操作（插入、删除、堆化）以及堆排序算法。难点在于理解堆的上浮和下沉操作，以及如何通过数组实现堆结构。堆与优先队列、排序算法等知识点紧密相关，理解堆有助于深入学习这些算法。