基于数组的出堆算法以下步骤可实现出堆算法：将堆顶元素与最后一个元素交换。对子树进行堆化操作，以维持堆的性质。移除最后一个元素。该算法在 O(log n) 时间复杂度内执行，其中 n 是堆中的元素数量。
Java 中基于数组的出堆算法
出堆操作是将堆顶元素（最小或最大元素取决于堆的类型）从堆中移除。对于基于数组的堆，可以使用以下步骤实现出堆算法：
步骤：
- 将堆顶元素与最后一个元素交换：将根节点（堆顶元素）与数组中最后一个元素交换。这将堆顶元素移至数组的末尾。
- 调整堆：对子树（以最后一个元素为根节点）进行堆化操作，以维持堆的性质。
- 移除最后一个元素：将数组中最后一个元素（即之前的堆顶元素）移除。
调整堆的过程：
立即学习“Java免费学习笔记（深入）”；
- 确定当前节点的左右子节点：计算当前节点左右子节点在数组中的索引。
- 选择较小的子节点（小顶堆）或较大的子节点（大顶堆）：将当前节点与左右子节点进行比较，选择较小或较大的子节点。
- 与较小（大）的子节点交换：将当前节点与较小（大）的子节点交换。
- 递归调整子树：将步骤 1-3 应用于交换后的子节点。
算法复杂度：
出堆操作在基于数组的堆上通常需要 O(log n) 的时间复杂度，其中 n 是堆中的元素数量。
代码示例：
<code class="java">public static int pop(int[] arr) {
int n = arr.length - 1;
if (n < 0) {
throw new IllegalStateException("Empty heap");
}
// 交换堆顶元素和最后一个元素
int temp = arr[0];
arr[0] = arr[n];
arr[n] = temp;
// 移除最后一个元素
n--;
// 调整堆
downHeapify(arr, 0, n);
return arr[n+1];
}
private static void downHeapify(int[] arr, int i, int n) {
// 计算左右子节点索引
int left = 2 * i + 1;
int right = 2 * i + 2;
// 选择较小的子节点
int smallest = i;
if (left <= n && arr[left] < arr[smallest]) {
smallest = left;
}
if (right <= n && arr[right] < arr[smallest]) {
smallest = right;
}
// 交换当前节点和较小的子节点
if (smallest != i) {
int temp = arr[i];
arr[i] = arr[smallest];
arr[smallest] = temp;
// 递归调整子树
downHeapify(arr, smallest, n);
}
}</code> 
