基本概念
堆是一种特殊的树形数据结构，其每个节点的值都必须大于或等于（最大堆）或小于或等于（最小堆）其子节点的值。这种性质保证了堆的顶部节点（根节点）始终是堆中最大或最小的元素。
堆的实现
数组表示法
由于堆本质上是一个完全二叉树，因此可以使用数组来表示。数组中的索引位置与树的节点位置相对应。例如，对于一个位于索引 i 的节点，其左子节点位于索引 2i+1，右子节点位于索引 2i+2，而父节点位于索引 (i-1)/2（向下取整）。
堆的操作
插入元素
插入新元素时，将其添加到数组的末尾，并通过上浮操作确保堆的性质不被破坏。
function insert(heap, value) {
heap.push(value);
let index = heap.length - 1;
while (index > 0 && heap[index] > heap[Math.floor((index - 1) / 2)]) {
[heap[index], heap[Math.floor((index - 1) / 2)]] = [heap[Math.floor((index - 1) / 2)], heap[index]];
index = Math.floor((index - 1) / 2);
}
}删除最大/最小元素
删除最大/最小元素时，将堆顶元素与最后一个元素交换，然后移除最后一个元素，并通过下沉操作重新调整堆。
-- -------------------- ---- -------
-------- ---------------- -
-- ------------ --- -- ------ -----
-- ------------ --- -- ------ -----------
----- ---- - --------
------- - -----------
--- ----- - --
----- --- - ----- - - - ----------- -- ----------- - ------ - ----- - --- --
-- - ----- - - - ----------- -- ----------- - ------ - ----- - ---- -
-- -- - ----- - - -- ----------- -- ------ - ----- - -- - ------ - ----- - --- -
------------- ------ - ----- - --- - ------- - ----- - --- -------------
----- - - - ----- - --
- ---- -
------------- ------ - ----- - --- - ------- - ----- - --- -------------
----- - - - ----- - --
-
-
------ -----
-堆的应用场景
优先队列
堆常用于实现优先队列。在优先队列中，元素按优先级顺序出队。堆的特性使得插入和删除操作的时间复杂度为 O(log n)，非常适合这种应用场景。
合并排序
在某些排序算法（如堆排序）中，堆被用来高效地排序数据。堆排序的时间复杂度为 O(n log n)，并且是原地排序算法。
拓扑排序
虽然堆本身不直接用于拓扑排序，但其概念可以应用于某些基于图的算法，比如在Dijkstra算法中用于高效查找最短路径。
示例：构建一个简单的堆
下面是一个使用数组实现的最大堆的例子：
const maxHeap = []; insert(maxHeap, 5); insert(maxHeap, 3); insert(maxHeap, 8); insert(maxHeap, 4); console.log(maxHeap); // 输出：[8, 3, 5, 4]
在这个例子中，我们首先插入了数值 5，然后是 3 和 8，最后是 4。每次插入后，都会调用上浮操作以保持堆的性质。
总结
堆是一种非常重要的数据结构，尤其适用于需要频繁插入和删除元素的情况。理解堆的工作原理和如何实现堆，对于掌握更复杂的算法和数据结构至关重要。希望本章的内容能够帮助你更好地理解和应用堆这一数据结构。