java - MinHeap 提取/heapDown() 失败 : incorrect order of elements

Question

我和一位同学现在在一项任务上坐了几个小时，但没有从我们的程序中找出(小？)错误。

任务是实现一个 MinHeap，可以更新元素并使用 heapDown 函数在 MinHeap 中对它们进行新排序。现在我们将其全部投入工作，但堆数组的某些元素未就位，并且提取后的列表(最小元素)未按应有的方式排序。希望您能帮助我们。

import java.util.Random;

public class MinPQ2 {
    private PQElement Elemente[];
    private int maxsize;
    private int currentsize;

    public MinPQ2(int max) {
        this.maxsize = max;
        this.currentsize = 0;
        Elemente = new PQElement[this.maxsize];
    }

    private void swap(int eins, int zwei) {//tauscht Elemente innerhalb des Arrays
        PQElement tmp = Elemente[eins];
        Elemente[eins] = Elemente[zwei];
        Elemente[zwei] = tmp;
    }

    public PQElement getLeftChild(int position) {
        return Elemente[position * 2 + 1];
    }

    public PQElement getRightChild(int position) {
        return Elemente[position * 2 + 2];
    }
    public PQElement getQuestioner(int position){
        return Elemente[position];
    }
    public PQElement getParent(int position) {
        return Elemente[position / 2 - ((position > 0 && position % 2 == 0) ? 1 : 0)];
    }

    private void heapUp(int position) {
        while (getParent(position).getPriority() > Elemente[position].getPriority()) {
            int temppos = position / 2 - ((position % 2 == 0) ? 1 : 0);
            swap(position, temppos);
            position = temppos;
        }
    }

    private void heapDown(int position) {
        int tmp;
        if (position * 2 + 2 < maxsize && getLeftChild(position) != null){
            if (getRightChild(position) != null){
                if (getLeftChild(position).getPriority() < getRightChild(position).getPriority()){
                    tmp = position *2+1;
                    swap(position,tmp);
                    position = tmp;
                    heapDown(position);
                }
                else {
                    tmp = position *2+2;
                    swap(position,tmp);
                    position = tmp;
                    heapDown(position);
                }
            }
            else if (getLeftChild(position).getPriority() < getQuestioner(position).getPriority()){
                tmp = position *2+1;
                swap(position,tmp);
                position = tmp;
                heapDown(position);
            }
        }
    }


    public boolean insert(PQElement n) {
        if (currentsize >= maxsize)
            return false;
        Elemente[currentsize] = n;
        currentsize++;
        if (currentsize > 1)
            heapUp(currentsize - 1);
        return true;
    }

    public boolean insert(String s, double d) {
        return insert(new PQElement(s, d));
    }

    public PQElement extractElement() {
        if(isEmpty())
            return null;
        PQElement result = Elemente[0];
        swap(0, currentsize-1);
        Elemente[currentsize - 1] = null;
        heapDown(0);
        currentsize--;
        return result;
    }

    public String extractData() {
        return extractElement().getData();
    }

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

    public void update(String s, double n) {
        int position = currentsize - 1;
        for (int i = 0; i <= currentsize; i++) {
            if (i == currentsize)
                return;
            if (Elemente[i].getData().equals(s)) {
                position = i;
                break;
            }
        }
        Elemente[position].setPriority(n);
        heapUp(position);
        heapDown(position);
    }
}

public class PQElement {
    private String data;
    private double Priority;

    public PQElement(String s, double d){
        this.data = s;
        this.Priority = d;
    }
    public String getData(){
        return data;
    }
    public double getPriority(){
        return Priority;
    }
    public void setPriority(double d){
        Priority = d;
    }
    public void setData(String s){
        data = s;
    }
}

import java.util.Arrays;
import java.util.Random;

public class testclass {
    public static void main(String[] args) {
        Random zufall = new Random();
        int max = 11;
        MinPQ2 test = new MinPQ2(max);
        for (int i = 0; i < max; i++) {
            test.insert(i + " Element", zufall.nextDouble());
        }
        System.out.println(test(test, max));
        System.out.println("_____________");
        //test2(test,max);
        System.out.println("_____________");
        test3(test,max,zufall);
    }

    private static boolean test(MinPQ2 test, int max) {
        for (int i = 1; i < max; i++) {
            if (test.getParent(i).getPriority() < test.getQuestioner(i).getPriority()) {
                System.out.println(test.getParent(i).getPriority() + " : " + test.getQuestioner(i).getPriority());
            } else return false;
        }
        return true;
    }
    private static void test2(MinPQ2 test, int max) {
        for (int i = 0; i < max; i++) {
            System.out.println(test.extractElement().getPriority());
        }
    }
    private static void test3(MinPQ2 test, int max, Random zufall){
        for (int i = 1; i < max;i++){
            if (i%2 == 0){
                test.update(i + " Element", zufall.nextDouble());
            }
        }
        test2(test,max);
    }
}

这是我们的准则。在测试类(第三个代码片段)中使用 test() 我们只显示堆，此时一切正常。但现在在 test3() 中我们更新了一些数据，使用 heapDown() 重新排序(第一个代码片段)并将它们打印在屏幕上。现在我们看到提取的数据没有排序。因此错误可能出现在 heapDown() 或 update() 中。但我们尝试了很多，但没有找到解决方案:(

Answer 1

您的 heapDown 方法存在多个问题。我已添加评论。

private void heapDown(int position) {
    int tmp;
    // You need to check against `currentsize`, rather than maxsize.
    if (position * 2 + 2 < maxsize && getLeftChild(position) != null){
        // In this code, you always move the parent down, because
        // you never compare the parent with its children.
        if (getRightChild(position) != null){
            if (getLeftChild(position).getPriority() < getRightChild(position).getPriority()){
                tmp = position *2+1;
                swap(position,tmp);
                position = tmp;
                heapDown(position);
            }
            else {
                tmp = position *2+2;
                swap(position,tmp);
                position = tmp;
                heapDown(position);
            }
        }
        else if (getLeftChild(position).getPriority() < getQuesttioner(position).getPriority()){
            tmp = position *2+1;
            swap(position,tmp);
            position = tmp;
            heapDown(position);
        }
    }
}

您的代码过于复杂。您可以像这样简化它:

// first find the smallest child
leftChildIndex = position * 2 + 1;
if (leftChildIndex >= currentSize) return;
smallestChildIndex = leftChildIndex;
rightChildIndex = position * 2 + 2;
if (rightChildIndex < currentSize) {
    if (getRightChild(position).getPriority() < getLeftChild(position).getPriority()) {
        smallestChildIndex = rightChildIndex;
    }
}
// if the parent is larger than the smallest child,
// then swap and repeat.
if (getQuestioner(smallestChildIndex).getPriority() < getQuestioner(position).getPriority()) {
    swap(position, smallestChildIndex);
    position = smallestChildIndex;
    heapDown(position);
}