在 Java 中调试最大堆

Question

前一段时间我在用 C++ 编程，我发现了一个关于制作最大堆的教程。这是代码，它似乎生成了正确顺序的堆。`

#include <iostream>

const int size = 14;
static int A[size] = {1, 2, 5, 10, 2, 11, 12, 7, 23, 22, 34, 54, 12, 22};

int left(int i)
{
    return (2*i)+1;
}

int right(int i)
{
    return (2*i)+2;
}

//a leaf of a value less than the size of the array
//and larger than the center of the array
bool isLeaf(int i)
{
    if(i >= (size/2) && i <= size)
    {
        return true;
    }
    return false;
}

void maxHeapify(int i)
{
    //if it isn't a leaf it may need to be swapped
    if(!isLeaf(i))
    {
        //if the value is less than it's right or left child
        if(A[i] < A[left(i)] || A[i] < A[right(i)])
        {
            //if the left child is smaller
            if(A[left(i)] > A[right(i)])
            {
                //swap the left child with the index
                std::cout << "Swapping " << A[i] << " and " << A[left(i)] << std::endl;
                int a = A[i];
                A[i] = A[left(i)];
                A[left(i)] = a;
                //and run maxHeapify in it. This will push the value to
                //it's lowest point and order all things below the parent
                maxHeapify(left(i));
            }
            else
            {
                //else swap with the right child since it is larger
                std::cout << "Swapping " << A[i] << " and " << A[right(i)] << std::endl;
                int a = A[i];
                A[i] = A[right(i)];
                A[right(i)] = a;
                //run maxheap on that value. This will push the value to it's lowest position
                maxHeapify(right(i));
            }
        }
    }
}


bool buildHeap()
{
    //need to run for each node that is not a leaf
    for(int i = (size/2); i >= 0; i--)
    {
        maxHeapify(i);
    }
    return true;
}


int main()
{
    std::cout << "before: " << std::endl;
    for(int i = 0; i < size; i++)
    {
        std::cout << A[i] << ", ";
    }
    std::cout << std::endl;
    buildHeap();
    std::cout << "After: " << std::endl;
    for(int i = 0; i < size; i++)
    {
        std::cout << A[i] << ",";
    }
    std::cout << std::endl;
    return 0;
}

上面的输出是：
之前：
1, 2, 5, 10, 2, 11, 12, 7, 23, 22, 34, 54, 12, 22,
交换 12 和 22
交换 11 和 54
交换 2 和 34
交换 10 和 23
交换 5 和 54
交换 5 和 12
交换 2 和 34
交换 2 和 22
交换 1 和 54
交换 1 和 22
交换 1 和 12

之后：
54,34,22,23,22,12,12,7,10,2,2,11,5,1,

目前我正在为期中考试学习，我正在尝试在 java 中重现我的代码。我已经看了一段时间了，但似乎找不到哪里出错了。这是损坏的 java： Main.java

public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] a = { 1, 2, 5, 10, 2, 11, 12, 7, 23, 22, 34, 54, 12, 22 };
        System.out.println("Begfore");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + ", ");
        }
        Heap h = new Heap(a);
        h.buildHeap();
        h.print();
        System.out.println();
        System.out.println(a.length);
    }
}

Heap.java

public class Heap {

    int[] heap;

    public Heap(int[] a) {
        // heap = new int[a.length];
        heap = a;
    }

    public void buildHeap() {
        for (int i = heap.length / 2; i >= 0; i--) {
            maxHeapify(i);
        }
    }

    public int getLeft(int a) {
        return (2 * a) + 1;
    }

    public int getRight(int a) {
        return (2 * a) + 2;
    }

    private boolean isLeaf(int a) {
        if (a >= ((heap.length) / 2) && a <= heap.length) {
            return true;
        } else {
            return false;
        }
    }

    public void maxHeapify(int a) {
        if (!isLeaf(a)) {
            if (heap[a] < heap[getLeft(a)] || heap[a] < heap[getRight(a)]) {
                if (getLeft(a) <= heap.length && getRight(a) < heap.length) {
                    if (heap[getLeft(a)] > heap[getRight(a)]) {
                        int watcher = heap[a];
                        heap[a] = heap[getLeft(a)];
                        heap[getLeft(a)] = watcher;
                        maxHeapify(getLeft(a));
                    } else {
                        int watcher = heap[a];
                        heap[a] = heap[getRight(a)];
                        heap[getRight(a)] = watcher;
                        maxHeapify(getRight(a));
                    }
                }
            }
        }
    }

    public void print() {
        System.out.println("heap");
        for (int i = 0; i < heap.length; i++) {
            System.out.print(heap[i] + ", ");
        }
    }
}

这不会产生正确的最大有序堆。
Java 输出：54, 34, 12, 23, 22, 12, 1, 7, 10, 2, 2, 11, 5, 22,

Answer 1

这段代码有一些基本问题。让我解释一下。

首先在Max Heapify函数中，不需要判断是否是叶子这个条件。这让我想到了你的 max heapify 函数调用。

heapify 函数总是从索引 heap.length/2 - 1 到 0 调用，请注意您没有使用 -1。这允许 heapify 始终从叶子中保存，因为在二叉堆中，无论最大值还是最小值，叶子都放在索引堆中。length/2 到 heap.length-1。

此代码的另一个错误是索引的使用方式。有两种使用索引的方式。

要么使用从 0 到 heap.length -1 的实际索引，在这种情况下不应该有任何条件，例如

<=heap.length or >=heap.length

但是你在heapify代码中使用了这样的条件。

或者使用范围从 1 到 heap.length 的假索引，每当你在 [ ] 中使用它们时，只需减去 -1。这在我的 java 代码中非常有效。

希望这对您有所帮助。如果你想要，我可以给你 java 代码。

在 Java 中调试最大堆

Debugging Max Heap in Java

c++

java

heap