2 
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 ループが 1 回しか実行されないのはなぜですか? 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 を増やしますが、何も機能していないようです。

4

1 に答える 1

0

ルートを回転させていません。ループ本体は次のようになります。

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++、そこにステートメントを入れるべきではないということです。<の代わりに<=との>代わりにする必要もありますが>=、それはほんのわずかな最適化です。

于 2013-04-14T01:09:04.233 に答える