时间戳

首页 > 解决方案 > 它是堆最大值吗？

java - 它是堆最大值吗？

问题描述

对于一个项目，我是否正在使用堆。在这个项目中，我必须“调查”一个数组是否是一个最大堆。

这 2 条规则适用于最大堆：

  1. 父母应大于或等于其孩子/孩子
  2. 堆中的每个节点都应包含一个元素

因此，我创建了 2 个用于检查这些规则是否适用的循环。对我来说不幸的是，我的代码不起作用。

我有 2 个 for 循环：

 //Checks if there's a 0 value in the array. If so: Return false

    for (int i = 1; i <= A.length; i++) {
        System.out.println("A.length: " + A[i]);
        if (A[i] == 0) {
            System.out.println("weweh: "+ A[i]);
            return false;
        }

//Checks if either left or right child have a bigger value than itself

    for (int i = 1; i <= (A.length - 2) / 2; i++) {
        System.out.println("A: " + i);
        if (A[i] < A[2 * i] || A[i] < A[2 * i + 1]) {
            return false;
        }
    }


 //the array


 int A[] = {0, 40, 35, 30, 25, 15, 10, 5};

最后一个 for 循环有效，但由于某种原因，我在第一个 for 循环中出错。循环可以找到一个数字。Lets say that i picked 15 to be equal with A[i], then it would work and return false, but when the selected number 0 isn't there, then it sends me the error, and it wont go further for the second loop .

 //Error:

 A.length: 40
A.length: 35
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 8
A.length: 30
A.length: 25
A.length: 15
A.length: 10
A.length: 5
    at ismaxheap.IsMaxHeap.MaxHeap(IsMaxHeap.java:24)
    at ismaxheap.IsMaxHeap.main(IsMaxHeap.java:15)
/Users/yusuf/Library/Caches/NetBeans/8.2/executor-snippets/run.xml:53: Java returned: 1
BUILD FAILED (total time: 0 seconds)

整个代码：

public class IsMaxHeap {

public static void main(String[] args) {
    MaxHeap();
    System.out.println("Max Heap:  " + MaxHeap());
}

public static boolean MaxHeap() {

    int A[] = {0, 40, 35, 30, 25, 15, 10, 5};

    for (int i = 1; i <= A.length; i++) {
        System.out.println("A.length: " + A[i]);
        if (A[i] == 0) {
            System.out.println("weweh: "+ A[i]);
            return false;
        }
    } 

    for (int i = 1; i <= (A.length - 2) / 2; i++) {
        System.out.println("A: " + i);
        if (A[i] < A[2 * i] || A[i] < A[2 * i + 1]) {
            return false;
        }
    }
    return true;
}

}

标签： javaheapmax-heap

解决方案

在您的第一个循环中，您使用<=

for (int i = 1; i <= A.length; i++)

既然您正在尝试访问A[i]，i == A.length那么您就超出了范围。

应该：

for (int i = 1; i < A.length; i++)

现在我不知道为什么你从索引 1 开始，因为 Java 中的索引从 0 开始。

处理一个孩子的特殊情况

当数组长度为 3 时就是这种情况（因为忽略了零索引）

所有你需要检查的是是否A[2] < A[1]是一个最大堆，否则立即返回 false。

否则执行正常循环。

推荐阅读