java - ArrayHeap 类不返回排序数组

Question

我正在使用java。

这是我的类(class)的代码:

/**
 * Ensure that the ordering property of the heap holds after
 * the insertion of an new element into the heap.
 */
private void interchangeUp() {
    int current = size - 1;
    int parent = (current - 1) / 2;

    while(parent <= 0 && heapForm[current].compareTo(heapForm[parent]) < 0) {
        swap(parent, current);
        current = parent;
        parent = (current - 1) / 2;
    }
}

我检查了我的代码，似乎无法找出导致此问题的原因。

谁能帮帮我吗？

Answer 1

你的算法有一个小错误:

private void interchangeUp() {
    int current = size - 1;
    int parent = (current - 1) / 2;

    //while (parent <= 0 && heapForm[current].compareTo(heapForm[parent]) < 0) {
    while (parent >= 0 && heapForm[current].compareTo(heapForm[parent]) < 0) {
        swap(parent, current);
        current = parent;
        parent = (current - 1) / 2;
    }
}