为确保堆在修改后仍保持其定义属性（最小堆或最大堆），我们需要高效的操作来添加元素、移除优先级最高的元素（根节点），以及从初始元素集合构建堆。这些主要操作包括插入、提取（最小或最大）和建堆。它们通过在树结构中向上或向下移动元素来恢复堆的属性。
下面我们以最小堆为例，说明这些操作的工作方式。最大堆的逻辑与此类似，只是比较标准相反（寻找最大元素而非最小元素）。
插入元素
向堆中添加新元素时，我们必须确保两点：结构保持为一个完全二叉树，以及堆的属性得到维护。
维护结构：将新元素添加到树最低层的第一个可用位置。在常见的数组表示中，这只需将元素添加到数组末尾即可。
恢复堆属性（上浮）：新添加的元素可能破坏堆属性。将新元素与其父节点比较。如果它小于父节点（在最小堆中），则交换它们。重复此比较和潜在的交换过程，将元素在树中向上移动（朝向根节点），直到它大于或等于其父节点，或成为新的根节点。这个过程通常称为“上浮”或“冒泡上浮”。
考虑将值8插入到以下最小堆中：
插入前的初始最小堆。
首先，将8添加到下一个可用位置：
将8添加到下一个可用位置（作为30的子节点）。
现在，上浮8：
将8与其父节点30比较。因为8<308 < 308<30，交换它们。
将8与其新父节点20比较。因为8<208 < 208<20，交换它们。
将8与其新父节点10比较。因为8<108 < 108<10，交换它们。
8现在是根节点，所以过程停止。
插入8并执行上浮后的最终最小堆。
插入操作的时间复杂度主要由上浮过程决定。由于一个包含nnn元素的完全二叉树的高度为O(logn)O(\log n)O(logn)，因此所需的最大交换次数与高度成比例。所以，插入操作的时间复杂度为O(logn)O(\log n)O(logn)。
提取最小/最大元素
在最小堆中，最小元素总是在根节点。类似地，最大元素在最大堆的根节点。提取这个元素需要移除根节点，然后恢复堆的属性。我们来看看提取最小操作：
保存根节点：保存根节点的值（最小值）以便返回。
维护结构：将堆中最后一个元素（最低层最右边的元素）移动到根节点位置。这保持了树的完整性。
恢复堆属性（下沉）：现在位于根节点的元素可能大于其子节点，从而违反了最小堆属性。将新根节点与其子节点比较。如果它大于任一子节点，则与两个子节点中较小的一个交换。重复此比较和交换过程，将元素在树中向下移动，直到它小于或等于其所有子节点，或成为叶节点。这被称为“下沉”或“冒泡下沉”。
我们从刚才创建的堆中提取最小元素（8）：
确定要提取的根节点（8）和最后一个元素（30）。
移除8，将30移到根节点：
用最后一个元素（30）替换根节点。
现在，下沉30：
将30与其子节点10和15比较。较小的子节点是10。因为30>1030 > 1030>10，交换30与10。
30现在是10的子节点。将30与其新子节点20和25比较。较小的子节点是20。因为30>2030 > 2030>20，交换30与20。
30现在是20的子节点。它没有子节点，所以它是一个叶节点。下沉过程停止。
提取原始最小值并执行下沉后的最终最小堆。
与插入类似，提取操作的时间复杂度主要由下沉过程决定，该过程涉及从根节点到叶节点的路径遍历。这条路径的长度为O(logn)O(\log n)O(logn)，因此提取操作也需要O(logn)O(\log n)O(logn)时间。
构建堆（建堆）
通常，我们从一个未排序的元素集合开始，希望构建一个包含所有这些元素的堆。我们可以使用上面描述的插入操作一个接一个地插入每个元素。由于有nnn个元素，每次插入需要O(logn)O(\log n)O(logn)时间，因此这种方法总共需要O(nlogn)O(n \log n)O(nlogn)时间。
然而，存在一种更高效的方法，通常称为建堆或弗洛伊德算法。它的工作原理是从树中最后一个非叶节点开始，对其应用下沉操作。然后，它向后遍历数组（或在树中向上），对每个节点应用下沉操作，直到到达根节点。
为什么从最后一个非叶节点开始？因为所有叶节点都已经是大小为1的有效堆。通过逐步向上应用下沉操作，我们确保当我们处理一个节点时，其子节点已经是有效子堆的根节点。
我们来将数组[30, 20, 15, 10, 25, 18, 17]建为最小堆。
对应的树结构初始如下所示（显示了索引）：
30 (0)
/ \
20(1) 15(2)
/ \ / \
10(3) 25(4) 18(5) 17(6)
最后一个非叶节点位于索引2（值为15）。索引范围是：floor(n/2) - 1到0。这里n=7n=7n=7，所以索引是2, 1, 0。
下沉索引2处的节点（15）：子节点是18和17。较小的子节点是17。因为15<1715 < 1715<17，无需交换。
下沉索引1处的节点（20）：子节点是10和25。较小的子节点是10。因为20>1020 > 1020>10，交换20和10。20现在位于索引3（叶节点），所以下沉停止。
30 (0)
/ \
10(1) 15(2) <- 20和10已交换
/ \ / \
20(3) 25(4) 18(5) 17(6)
下沉索引0处的节点（30）：子节点是10和15。较小的子节点是10。因为30>1030 > 1030>10，交换30与10。
10 (0) <- 30和10已交换
/ \
30(1) 15(2)
/ \ / \
20(3) 25(4) 18(5) 17(6)
现在30位于索引1。将30与其子节点20和25比较。较小的子节点是20。因为30>2030 > 2030>20，交换30与20。
10 (0)
/ \
20(1) 15(2) <- 30和20已交换
/ \ / \
30(3) 25(4) 18(5) 17(6)
30现在位于索引3（叶节点），所以下沉停止。
最终建堆后的数组是[10, 20, 15, 30, 25, 18, 17]。
应用高效的建堆算法后最小堆的结构。
尽管它涉及到大约n/2n/2n/2次的下沉操作（一个O(logn)O(\log n)O(logn)的操作），但更仔细的分析表明，建堆算法的总工作量实际上是O(n)O(n)O(n)。这是因为大多数节点都靠近树的底部，并且对于靠近叶子的节点，下沉操作运行得更快。对于大型集合，使用这种自底向上的方法构建堆比重复插入要快得多。
这些核心操作，包括插入和提取的对数时间复杂度以及初始构建的线性时间，使得堆在管理具有优先级的元素方面效率很高，并为优先级队列提供了支撑。