我有以下实现最大堆的 Java 代码。运行正确,
号码列表: 4, 1, 3, 2, 16, 9, 10, 14, 8, 7
最大堆结果:
16 14 10 8 7 9 3 2 4 1
我想要的是更改此代码,以便通过给出索引使最大堆仅成为数组的一部分。
例如,如果我给出索引=4
它不应影响前 4 个元素:4 1 3 2 但用剩余元素 16, 9 ,10, 14, 8, 7 构建最大堆
所以最终结果应该是
4 1 3 2 16 14 10 9 8 7
不应使用其他数组,而应仅使用给定的数组:
public class Heapify {
public static int[] Arr = {
4, 1, 3, 2, 16, 9, 10, 14, 8, 7
};
public static int counter = 0;
public static void main(String[] args) {
heapMe();
for (int krk = 0; krk < Arr.length; krk++) {
System.out.println(Arr[krk]);
}
}
public static void heapMe() {
int kk;
for (kk = (Arr.length) / 2 - 1; kk >= 0; kk--) {
heapify(Arr, kk);
}
}
public static void heapify(int[] Arr, int i) {
int largest;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (((left < Arr.length) && (Arr[left] > Arr[i]))) {
largest = left;
} else {
largest = i;
}
if (((right < Arr.length) && (Arr[right] > Arr[largest]))) {
largest = right;
}
if (largest != i) {
swap(i, largest);
heapify(Arr, largest);
}
}
private static void swap(int i, int largest) {
int t = Arr[i];
Arr[i] = Arr[largest];
Arr[largest] = t;
}
}
最佳答案
您需要在引用Arr.length
的函数中添加一个额外的参数n
,并替换所有对Arr.length
的引用与n
。当您将 4
传递给 heapMe
时,它将在前四个元素上进行堆化:
public static void heapMe(int n) {
int kk;
for (kk = n / 2 - 1; kk >= 0; kk--) {
heapify(Arr, n, kk);
}
}
public static void heapify(int[] Arr, int n, int i) {
... // Replace Arr.length with n throughout the body of the function
}
关于java - 子数组中的最大堆,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15103379/