使用Java创建最大堆 [英] creating a max-heap using java
本文介绍了使用Java创建最大堆的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我正在尝试使用以下代码在Java中创建一个Max-Heap:
I am trying to create a Max-Heap in java using the following code:
public class Heapify {
// 16 14 10 8 7 9 3 2 4 1
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) {
int kk;
for (kk = 0; kk <= Arr.length - 1; kk++) {
heapM(Arr, kk);
}
for (int krk = 0; krk < Arr.length; krk++) {
System.out.println(Arr[krk]);
}
}
public static void heapM(int[] Arr, int i) {
int largest;
int left = i * 2;
int right = i * 2 + 1;
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);
heapM(Arr, largest);
}
}
private static void swap(int i, int largest) {
int t = Arr[i];
Arr[i] = Arr[largest];
Arr[largest] = t;
}
}
所需的输出应为:
16 14 10 8 7 9 3 2 4 1
我正在得到
4 3 16 14 8 9 10 2 1 7
有人可以帮忙为什么堆没有正确构建吗?
Can someone please help as to why the heap is not being built properly ?
谢谢
推荐答案
我运行了您的代码,除了Jodaka所说的话,我发现了另一个错误
I ran your code, and in addition to what Jodaka said, I found one more error
for (kk = 0; kk <= Arr.length - 1; kk++) {
heapM(Arr, kk);
}
应该是
for (kk = Arr.length -1; kk >= 0; kk--) {
heapM(Arr, kk);
}
因为执行MaxHepify时,您从头开始,然后向后走。
和
because when doing MaxHepify, you start from the end, and go backwards. and
int left = i * 2;
int right = i * 2 + 1;
应该是Jodaka所说的
should be, as Jodaka said
int left = 2*i+1;
int right = 2*i + 2;
我在这里运行,输出现在正确了
I ran it here and the output is now correct
这篇关于使用Java创建最大堆的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文