java基于数组的出堆怎么写-java教程-PHP中文网

java基于数组的出堆怎么写

幻夢星雲

发布： 2024-11-02 07:27:22

原创

1013人浏览过

基于数组的出堆算法以下步骤可实现出堆算法：将堆顶元素与最后一个元素交换。对子树进行堆化操作，以维持堆的性质。移除最后一个元素。该算法在 O(log n) 时间复杂度内执行，其中 n 是堆中的元素数量。

java基于数组的出堆怎么写

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>

登录后复制

以上就是java基于数组的出堆怎么写的详细内容，更多请关注php中文网其它相关文章！