从数组构建最大堆。执行。如何动态管理数组的大小。当我使用插入方法时，我应该增加 arr 大小

Question

从数组构建最大堆。在实施部分。如何动态管理数组的大小？当我使用 Insert 方法时，我应该增加 arr 大小。尝试过，但它没有返回所需的堆数组。

我得到的输出为 => [72] 期望输出 => [99, 61, 72, 18, 27, 55, 58]

我尝试了 Array.copyof ，它返回：原始数组的副本，被截断或用零填充以获得指定的长度。

得到的结果为：[72, 0, 0, 0, 0, 0, 0, 0] - 截断或用零填充以获得指定的长度

导入java.util.Arrays；

公共类堆{ 私有 int[] 堆；

public Heaps() {
    this.heap = new int[1];
}

public int[] getGeap() {
    return this.heap;
}

private int leftChild(int index) {
    return index * 2 + 1;
}

private int rightChild(int index) {
    return index * 2 + 2;
}

private int parent(int index) {
    return (index - 1) / 2;
}

private void swap(int index1, int index2) {
    int temp = heap[index1];
    heap[index1] = heap[index2];
    heap[index2] = temp;
}

public void insert(int value) {
    heap[0] = value;
    int current = heap.length - 1;

    while (current > 0 && heap[current] > heap[parent(current)]) {
        swap(current, parent(current));
        current = parent(current);
    }
}

public static void main(String[] args) {
    int[] A = { 99, 61, 58, 18, 27, 55, 72 };
    Heaps hp = new Heaps();

    for (int i = 0; i < A.length; i++) {
        hp.insert(A[i]);
    }

    System.out.println(Arrays.toString(hp.getGeap()));

}

}

Answer 1

有

ArrayList

可以为您做到这一点。因此，我将

heap

字段定义为

ArrayList<Integer>

，并相应地调整您的代码。如果您真的需要一个返回原始整数数组的方法，请在

getHeap

中编写转换。

具体做法如下：

import java.util.*;

class Heaps {
    private List<Integer> heap;

    public Heaps() {
        this.heap = new ArrayList<Integer>(); // Dynamic array
    }

    public int[] getHeap() {
        // Convert to int[]:
        int[] intHeap = new int[heap.size()];
        for (int i = 0; i < intHeap.length; i++) {
            intHeap[i] = this.heap.get(i);
        }
        return intHeap;
    }

    private int leftChild(int index) {
        return index * 2 + 1;
    }

    private int rightChild(int index) {
        return index * 2 + 2;
    }

    private int parent(int index) {
        return (index - 1) / 2;
    }

    private void swap(int index1, int index2) {
        Collections.swap(heap, index1, index2);
    }

    public void insert(int value) {
        heap.add(value); // Now it's easy.
        int current = heap.size() - 1;
        while (current > 0 && heap.get(current) > heap.get(parent(current))) {
            swap(current, parent(current));
            current = parent(current);
        }
    }
}