从数组构建最大堆。在实施部分。如何动态管理数组的大小?当我使用 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()));
}
}
有
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);
}
}
}