java - while循环只在deleteMax()堆方法中执行一次

Question

package x;

public class MaxHeap {

    private Element[] heapArray;
    private int maxSize;
    private int currentSize;

    public MaxHeap(int max) {
        maxSize = max;
        currentSize = 0;
        heapArray = new Element[maxSize]; // create the heap
    }

    public boolean isEmpty() {
        return currentSize == 0;
    }

    // Move an element up in the heap tree.
    public void adjustHeap(int index) {

        int parent = (index - 1) / 2;
        Element bottom = heapArray[index];

        while (index > 0 && heapArray[parent].getData() < bottom.getData()) {
            heapArray[index] = heapArray[parent]; // move it down
            index = parent;
            parent = (parent - 1) / 2;
        }
        heapArray[index] = bottom;
    }

    public boolean insert(int key) {
        if (currentSize == maxSize)
            return false;
        Element newElement = new Element(key);
        heapArray[currentSize] = newElement;
        adjustHeap(currentSize++);
        return true;
    }

    public Element[] getMaxHeap() {

        return heapArray;
    }

    public void printHeap() {
        int i;
        for (i = 0; i < maxSize; i++)
            System.out.print(heapArray[i].getData() + " ");
        System.out.println();
    }

    public void deleteMax() {
        heapArray[0].setData(heapArray[maxSize - 1].getData());
        currentSize--;

        int i = 0;
        while (i<=heapArray[maxSize - 1].getData()) {

            int left = 2 * i + 1;
            int right = 2 * i + 2;      

            if (heapArray[left].getData() <= heapArray[right].getData()) {
                i = (2 * i + 1);
                adjustHeap(right);
                i++;
            }
            if (heapArray[left].getData() >= heapArray[right].getData()) {
                i = (2 * i + 2);
                adjustHeap(left);
                i++;
            }

        }
    }
}

    package x;

    class Element {
        private int inData;
        public Element(int data){
            inData = data;
        }
        public int getData(){
            return inData;
        }
        public void setData(int data){
            inData = data;
        }
    }

package x;

public class Test {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        MaxHeap heap = new MaxHeap(13);
        heap.insert(2);
        heap.insert(20);
        heap.insert(10);
        heap.insert(5);
        heap.insert(6);
        heap.insert(15);
        heap.insert(7);
        heap.insert(8);
        heap.insert(18);
        heap.insert(11);
        heap.insert(4);
        heap.insert(3);
        heap.insert(1);

        heap.printHeap();
        System.out.println("\n");


        heap.deleteMax();
        heap.printHeap();

    }
}

我的问题是:为什么我的 while 循环只执行一次？我希望我的 deleteMax 方法删除最大节点(根节点)，然后对堆进行正确排序，使其再次成为最大堆。最大堆如下:20 18 15 8 11 10 7 2 6 5 4 3 1

一旦 deleteMax 被调用，它应该输出:18 11 15 8 5 10 7 2 6 1 3 4

但它却输出:18 1 15 8 11 10 7 2 6 5 4 3 1

很明显，它正在删除最大节点，将其替换为最底部的叶子，并将新根与其最大的子节点交换。然后它应该继续在堆中交换 1，但它在这样做之前停止了。

我为 while 循环尝试了很多不同的逻辑，包括:

while(Math.floor(i/2) <= 2*i+1 && Math.floor(i/2) <= 2*i+2)

并增加 i 但似乎没有任何效果。

Answer 1

您没有旋转根。您的循环体应如下所示。

if (heapArray[left].getData() < heapArray[i].getData()) {
    temp = heapArray[i].getData();
    heapArray[i].setData(heapArray[left].getData());
    heapArray[left].setData(temp);
    i = (2 * i + 1);
 }
 else if (heapArray[right].getData() > heapArray[i].getData()) {
     temp = heapArray[i].getData();
     heapArray[i].setData(heapArray[right].getData());
     heapArray[right].setData(temp);
     i = (2 * i + 2);
 }

你的 adjustHeap方法可能已经在执行此交换，我无法确定。最重要的是你需要在堆中旋转你的根(而不是比较分支)，你不应该有 i++里面的声明。也应该是<而不是 <=和 >而不是 >= ，但这只是一个小的优化。