数据结构之：堆

堆（Heap）是计算机科学中的一种特别的完全二叉树结构，它满足某种特定顺序，用于实现优先队列等数据结构。堆主要有两种类型：最大堆（Max Heap）和最小堆（Min Heap）。

定义

• 最大堆：在最大堆中，任何一个父节点的值都大于或等于它的子节点的值。这意味着堆的根节点包含了堆中的最大值。
• 最小堆：在最小堆中，任何一个父节点的值都小于或等于它的子节点的值。这意味着堆的根节点包含了堆中的最小值。

特性

1. 完全二叉树：堆是一种特殊的完全二叉树，除了最后一层外，其他每一层都被完全填充，并且所有节点都尽可能地向左对齐。
2. 堆性质：堆中的每个节点都满足子节点小于（最大堆）或大于（最小堆）父节点的性质。

表示

堆通常使用数组来表示。对于给定位置的元素i（从0开始计数）：

• 它的父节点位置是 (i - 1) / 2。
• 它的左子节点位置是 2*i + 1。
• 它的右子节点位置是 2*i + 2。

操作

• 插入（Insert）：在堆中插入一个新元素。新元素被加到堆的末尾，然后通过一系列上浮（对于最大堆）或下沉（对于最小堆）操作，恢复堆的性质。
• 删除（Delete）：在最大堆中删除根节点（即最大元素），在最小堆中删除根节点（即最小元素）。通常，堆的最后一个元素被移动到根节点，然后通过一系列下沉操作，恢复堆的性质。
• 构建（Build）：将一个无序数组构建成一个堆。可以通过从最后一个非叶子节点开始，向前进行下沉操作，直到根节点，来实现。

应用

• 优先队列：堆是实现优先队列的理想结构，可以快速访问队列中的最大值或最小值。
• 堆排序：堆排序算法是基于堆的选择排序，通过构建最大堆或最小堆，来实现数组的排序。
• 图算法：在Dijkstra和Prim算法中，堆用于高效地选取最小边或最短路径。

堆结合了二叉树的结构特点和数组的简单性，提供了一种高效的方式来实现动态排序和优先级队列管理。