基于数组的出堆算法以下步骤可实现出堆算法：将堆顶元素与最后一个元素交换。对子树进行堆化操作，以维持堆的性质。移除最后一个元素。该算法在 o(log n) 时间复杂度内执行，其中 n 是堆中的元素数量。
Java 中基于数组的出堆算法
出堆操作是将堆顶元素（最小或最大元素取决于堆的类型）从堆中移除。对于基于数组的堆，可以使用以下步骤实现出堆算法：
步骤：
- 将堆顶元素与最后一个元素交换：将根节点（堆顶元素）与数组中最后一个元素交换。这将堆顶元素移至数组的末尾。
- 调整堆：对子树（以最后一个元素为根节点）进行堆化操作，以维持堆的性质。
- 移除最后一个元素：将数组中最后一个元素（即之前的堆顶元素）移除。
调整堆的过程：
立即学习“Java免费学习笔记（深入）”；
- 确定当前节点的左右子节点：计算当前节点左右子节点在数组中的索引。
- 选择较小的子节点（小顶堆）或较大的子节点（大顶堆）：将当前节点与左右子节点进行比较，选择较小或较大的子节点。
- 与较小（大）的子节点交换：将当前节点与较小（大）的子节点交换。
- 递归调整子树：将步骤 1-3 应用于交换后的子节点。
算法复杂度：
出堆操作在基于数组的堆上通常需要 O(log n) 的时间复杂度，其中 n 是堆中的元素数量。
代码示例：
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); } }
登录后复制
© 版权声明
文章版权归作者所有，未经允许请勿转载。
【小浪云服务商 - 服务器12元起 - 挂机宝5元起】
THE END
暂无评论内容