Max Heapify 问题

Question

我已经尝试调试这段代码好几个小时了。我不知道为什么它不重新排列条款。我已经尝试了我能想到的一切。有人可以帮忙吗？谢谢

public void heapify(int i)  // utility routine to percolate down from index i
{
    printHeap();
    int left, r, min;
    Process tmp;

    left = lchild(i);           // left child
    r = rchild(i);                  // right child

    if(left < size() && A[left].compareTo(A[i])<0)      // find smallest child
        min = left;                 // save index of smaller child
    else
        min = i;

    if(r < size() && A[r].compareTo(A[min])<0)
        min = r;                // save index of smaller child

    if(min != i)                // swap and percolate, if necessary
    {
        tmp = A[i];             // exchange values at two indices
        A[i] = A[min];
        A[min] = tmp;
        heapify(min);

        // call heapify
    }// end if
printHeap();
}// end method heapify


private int lchild(int i) {
    return 2 * i + 1;
}

private int rchild(int i) {
    return 2 * i + 2;
}

即使我在堆的每个元素上调用 heapify 它也不起作用:/ 这是比较对象。它应该首先使用优先级安排最大堆，然后如果有平局，它会进入一个唯一的时间到达值。

public int compareTo(Process o) {
    int val;
    if (this.priority > o.getPriority()) {
        val = -1;
    } else if (this.priority == o.getPriority()) {
        if (this.arrivalTime < o.getArrivalTime()) { //Earlier time
            val = -1;
        } else {
            val = 1;
        }
    } else {
        val = 1;
    }

    return val;
}

Answer 1

已知最快的将数组组织成堆的方法称为 Floyd's Algorithm。您从数组的中间开始，向根移动，根据需要筛选每个项目。在你的情况下：

for (int i = size()/2; i >= 0; --i)
{
    heapify(i);
}

您应该能够调用您提供的 heapify 函数。

要了解其工作原理，请查看

Answer 2

我想通了。这毕竟不是这个方法的问题。感谢大家！

Max Heapify 问题

Max Heapify issue

java

heap

heapsort