Binary Heap downheap 方法无法正常工作

Question

我正在尝试在 Java 中练习编写一些数据结构的代码，但遇到了二进制堆的问题，如果你能帮助我，我将不胜感激。

首先，我为将存储在堆中的对象创建了一个class。

public class Person {

private String name;
private String surname;
private int age;

public Person(String name, String surname, int age) {
    this.name = name;
    this.surname = surname;
    this.age = age;
}

public void setName(String n) {
    name = n;
}

public void setSurname(String n) {
    surname = n;
}

public void setAge(int a) {
    age = a;
}

public String getName() {
    return name;
}

public String getSurname() {
    return surname;
}

public int getAge() {
    return age;
}
}

然后我为将保存 Person 对象的堆节点以及节点优先级创建了一个 class。

public class BinNode {

private Person element;
private int priority;

BinNode(Person element, int priority) {
    this.element = element;
    this.priority = priority;
}

public boolean isEmpty() {
    if (element == null)
        return true;
    else
        return false;
}

public Person getElement() {
    return element;
}

public int getPriority() {
    return priority;
}

@Override
public String toString() {
    return "Data: " + element.getName() + " " + element.getSurname() + 
            ". Age: " + element.getAge() + "." + " Priority: " + priority + ".";
}   
}

最后我为二进制堆创建了一个 class。

public class BinHeap {

public BinNode[] tab;
public int counter;

BinHeap(Person root, int priority) {
    counter = 1;
    tab = new BinNode[10];
    BinNode rt = new BinNode(root, priority);   
    tab[counter++] = rt;
}

public void upheap(int i) {
    while((i > 1) && (tab[i].getPriority() < tab[i-1].getPriority())) {
        BinNode temp = tab[i-1];
        tab[i-1] = tab[i];
        tab[i] = temp;
        i--;
    }
}

//error somewhere here
public void downheap(int i) {
    int l = 2 * i;
    int r = 2 * i + 1;      
    while (r < counter-1 && l < counter) {
        l = 2 * i;
        r = 2 * i + 1;
        if(tab[l].getPriority() < tab[r].getPriority()) {
            BinNode temp = tab[i];
            tab[i] = tab[l];
            tab[l] = temp;
            i = l;
        } else if (tab[l].getPriority() >= tab[r].getPriority()) {
            BinNode temp = tab[i];
            tab[i] = tab[r];
            tab[r] = temp;
            i = r;
        }   
    }   
}

public void insert(Person p, int priority) {
    BinNode node = new BinNode(p, priority);
    tab[counter++] = node;
    upheap(counter-1);
}

public BinNode findMin() {
    return tab[1];
}

//or here   
public void delMin() {
    tab[1] = tab[counter];
    tab[counter--] = null;
    downheap(1);
}

public void showTree() {
    for (int i = 1; i < tab.length; i++) {
        if(tab[i] != null) {
        System.out.println(i + " - " + tab[i].toString());
        }
    }
}
}

这条主要class:

public class Main {

public static void main(String[] args) {

    Person mary = new Person("Mary", "Green", 20);
    Person mark = new Person("Mark", "Yellow", 60);
    Person john = new Person("John", "Dark", 12);
    Person adam = new Person("Adam", "Bright", 30);
    Person martha = new Person("Martha", "King", 33);
    Person greg = new Person("Greg", "Pawn", 1);

    BinHeap heap = new BinHeap(mary, 2);
    heap.showTree();
    System.out.println();

    heap.insert(mark, 4);
    heap.insert(john, 12);

    heap.showTree();
    System.out.println();

    heap.insert(adam, 1);
    heap.showTree();
    System.out.println();

    System.out.println("root: " + heap.findMin().toString());
    System.out.println();

    heap.insert(martha, 5);
    heap.insert(greg, 15);

    heap.showTree();
    System.out.println();

    heap.delMin();
    heap.showTree();

}
}

产生以下输出：

1 - Data: Mary Green. Age: 20. Priority: 2.

1 - Data: Mary Green. Age: 20. Priority: 2.
2 - Data: Mark Yellow. Age: 60. Priority: 4.
3 - Data: John Dark. Age: 12. Priority: 12.

1 - Data: Adam Bright. Age: 30. Priority: 1.
2 - Data: Mary Green. Age: 20. Priority: 2.
3 - Data: Mark Yellow. Age: 60. Priority: 4.
4 - Data: John Dark. Age: 12. Priority: 12.

root: Data: Adam Bright. Age: 30. Priority: 1.

1 - Data: Adam Bright. Age: 30. Priority: 1.
2 - Data: Mary Green. Age: 20. Priority: 2.
3 - Data: Mark Yellow. Age: 60. Priority: 4.
4 - Data: Martha King. Age: 33. Priority: 5.
5 - Data: John Dark. Age: 12. Priority: 12.
6 - Data: Greg Pawn. Age: 1. Priority: 15.

1 - Data: Mary Green. Age: 20. Priority: 2.
2 - Data: Martha King. Age: 33. Priority: 5.
3 - Data: Mark Yellow. Age: 60. Priority: 4.
5 - Data: John Dark. Age: 12. Priority: 12.
6 - Data: Greg Pawn. Age: 1. Priority: 15.

如您所见，只要我们将新节点放入堆中，一切都会正常进行。但是当我们要删除根节点时，downheap 方法（或者 delMin 方法）不能正常工作。

正如您所见，优先级为 5 的节点 "Martha King" 在堆中的优先级高于优先级为 4 的 "Mark Yellow" 节点。

编辑：我似乎不明白二进制堆作为数组实现时的行为。所以上面加粗的句子是不正确的。原始输出是错误的，因为堆失去了完整性属性，因为数组 [4] 是空的。

我就是想不通。请你帮助我好吗？谢谢你。也将不胜感激关于编码风格等的一些一般性评论。这是我第一次 post 堆栈溢出，如果我搞砸了，我深表歉意。

Answer 1

在 upheap 中，您将新 child 的值与 parent 而非 i-1 进行比较。

int parent(int i)
{
    return i/2;
}

public void upheap(int i) {
    while((i > 1) && (tab[i].getPriority() < tab[parent(i)].getPriority())) {
        BinNode temp = tab[parent(i)]; // it should not be i-1 but parent of i that is i/2
        tab[parent(i)] = tab[i];
        tab[i] = temp;
        i = parent(i);
    }
}

而且在下堆

public void downheap(int i) {
    int l = 2 * i;
    int r = 2 * i + 1; 
    int small = i;     
    if(l<counter && tab[l].getPriority() < tab[small].getPriority())
         small = l;
    if(r<counter && tab[r].getPriority() < tab[small].getPriority())
         small = r;
    if(small!=i)
    {
        BinNode temp = tab[i];
        tab[i] = tab[small];
        tab[small] = temp;
        downheap(small); //you need to call downheap again on the small to find new pos for i (i became small after swap). 
        //i = 1, when you call downheap after delete. The node at i=1 will move down if it is bigger.
    }
}

编辑：根据@Łukasz Bieliński 的建议，还更正了您的 delMin() 函数

public void delMin() {
    tab[1] = tab[--counter];
    tab[counter] = null;
    downheap(1);
}

下面是采用上述更改后将生成的输出和堆树的结果图像。结果是正确的。

代码参考可参考本文。

Binary Heap

代码是用 c++ 编写的，但对于 Java 学生来说会很清楚，因为它是使用 class 完成的。 MinHeapify 在那里是堆下层函数，而 insertKey() 内部的 while 循环在那里是堆上层函数。计数器也从 0 开始，而不是 1。

Answer 2

我认为您在计数器变量中保存了下一个空索引。实施@Adarsh Anurag 更正。删除时，您必须在此空索引之前而不是之后获取元素。

public void delMin() {
    tab[1] = tab[--counter];
    tab[counter] = null;
    downheap(1); 
}

Binary Heap downheap 方法无法正常工作

Binary Heap downheap method does not work properly

java

binary-heap

data-structures