使用比较器的Java堆化方法

Question

我正在尝试编写一个名为HeapQueue的类。我将根节点的左子节点存储在索引为2 * indexOfRoot + 1的位置，右子节点存储在2 * indexOfRoot + 2的位置。

public class HeapQueue implements PriorityQueue, BinaryHeap {

public List<Task> queue;
public Comparator comparator;

public HeapQueue() {
    queue = new ArrayList();
}

public void setComparator(Comparator comparator) {
    this.comparator = comparator;
    heapify(0);
}

public Comparator getComparator() {
    return comparator;
}

public void offer(Task task) {
    int currentElement, previousElement;
    queue.add(task);
    currentElement = queue.size() - 1;
    previousElement = (currentElement - 1) / 2;
    while (previousElement >= 0 && 
             getComparator().compare(queue.get(currentElement), queue.get(previousElement)) > 0) {
        swap(currentElement, previousElement);
        currentElement = previousElement;
        previousElement = (currentElement - 1) / 2;
    }
}

private void swap(int i, int j) {
    Task t1 = queue.get(i);
    Task t2 = queue.get(j);
    Task t3 = t1;
    queue.set(i, t2);
    queue.set(j, t3);
}
}

队列存储对象 Task。

public class Task {

private final String name;
private final int priority;

public Task(String name, int priority) {
    this.name = name;
    this.priority = priority;
}

public int getPriority() {
    return priority;
}

@Override
public String toString() {
    return name + "\tpriority = " + priority;
}
}

我有一个名为 heapify() 的方法，在 HeapQueue 中:

public void heapify(int root) {
    int leftChild, rightChild;
    leftChild = 2 * root + 1;
    if (leftChild < queue.size()) {
        rightChild = leftChild + 1;
        if ((rightChild < queue.size())
                && getComparator().compare(queue.get(rightChild), queue.get(leftChild)) > 0) {
            leftChild = rightChild;
        }
        if (getComparator().compare(queue.get(leftChild), queue.get(root)) > 0) {
            swap(root, leftChild);
            heapify(leftChild);
        }
    }

}

在将任务添加到队列后，可以通过方法setComparator()更改我的任务比较器。 默认的Comparator是：

public class Comparator{
    public int compare(Task t1, Task t2) {
        if (t1.getPriority() == t2.getPriority()) {
            return 0;
        } else if (t1.getPriority() < t2.getPriority()) {
            return -1;
        } else {
            return 1;
        } //sorting max
    }
 }

作为另一个比较器的例子可能是：

public class otherComparator{
    public int compare(Task t1, Task t2) {
        if (t1.getPriority() == t2.getPriority()) {
            return 0;
        } else if (t1.getPriority() < t2.getPriority()) {
            return 1;
        } else {
            return -1; 
        } //sorting min
    }
 }

我创建了一个HeapQueue并添加了一些元素。

HeapQueue heap = new HeapQueue();
heap.setComparator(comparator);
Task t1 = new Task("a", 1);
Task t2 = new Task("b", 2);
Task t3 = new Task("c", 3);
Task t4 = new Task("d", 4);
System.out.println(heap.queue.toString());

结果是：

[d priority = 4, c  priority = 3, b priority = 2, a priority = 1]

    4
   / \
  3   2
 /
1 

是的，但是当我将 Comparator 改为 otherComparator：

otherComparator newComparator = new otherComparator();
heap.setComparator(newComparator);
System.out.println(heap.queue.toString());

结果是：

[b priority = 2, c  priority = 3, d priority = 4, a priority = 1]

    2
   / \
  3   4
 /
1 

这是错误的。正确的答案应该像这样：

[a priority = 1, b priority = 2, c  priority = 3, d priority = 4]

    1
   / \
  2   3
 /
4 

我认为我在使用heapify()函数时遇到了问题，但我找不到错误。有人可以帮忙吗？

- lorantalas

---

你能分享一下你的交换函数吗？ - Pham Trung

@PhamTung 它在那里。 - lorantalas

哦，你怎么能将otherComparator设置为堆的比较器呢？它没有实现相同的接口啊。 - Pham Trung

通过任务比较器可以更改堆，而通过setComparator()，我可以更改比较器并通过heapify()重新构建堆。但它不起作用。 - lorantalas

我明白了，好的，我现在可以重现这个错误 :) - Pham Trung

你的修复程序运行时间为O(n log n)。看看我给出的重新堆化答案，它的运行时间为O(n)。基本上，如果你批量构建树而不是逐个节点构建，就可以降低时间复杂度。 - JasonN

Answer 1

你需要做的不仅仅是堆化下移（就像在堆化中一样，将节点向下推）或者堆化上移（就像在offer方法中一样，将节点向上拉），这些只能在删除或添加单个节点时起到修复作用。堆的其余部分必须已经遵守了堆规则。

你需要完全重新堆化结构。可以通过从结构底部开始，并将每个根节点推入正确的子树来线性时间完成。想象一下，从完整树的尾部/末尾开始，对每个具有子节点的节点运行堆化下移。

rehapify arraynodes:
    for i from arraynodes.length / 2:
      heapifydown( arraynodes, i )

其中 heapifydown 是您的堆操作函数。

- JasonN

---

对于每个 heapifyDown，我看到它需要从顶部到底部遍历 O(log n)，基本上是 O(nlogn)，但这不是一个紧密的界限，你能提供一个数学证明，表明这是 O(n) 吗？ - Pham Trung

你的时间复杂度为log(n) + log(n-1) + ... + log 1 = log(n*(n-1)*(n-2)...) = log(n!) ~ O(n log n)。更多信息。 - Pham Trung

它看起来只是这样，但每次遍历都会让树的顺序更加有序。http://www.geeksforgeeks.org/g-fact-85/ - JasonN

Answer 2

我通过创建函数rebuild()来解决问题:

private void rebuild() {
    HeapQueue reHeap = new HeapQueue();
    reHeap.setComparator(comparator);
    for (int i = 0; i < queue.size(); i++) {
        reHeap.offer(queue.get(i));
    }
    queue = reHeap.queue;
}

- lorantalas

Answer 3

你刚刚从最大堆转换为最小堆，这破坏了整个堆结构！

问题在于，当你改变比较器后，仅仅调用heapify(0)是不够的，因为，比如说，这种情况：

             4
            / \
           3   2
          /
         1

在执行了heapify之后，数字1将不会上移，因为在执行heapify(0)之后，程序会跳到右子节点，也就是2，而从那里我们无法到达1。

你可以创建另一个堆！

你可以查看这个答案，基本上，当改变比较器时，你只是破坏了堆结构！

- Pham Trung

---

@AlexeySharov 嗯，你认为在交换比较器之后，最大堆的整个结构没有改变，并且调用 heapify 只会改变堆的一部分，而不是整个堆。当你进行比较时，你只与两个最近的子节点进行比较，这是不正确的！ - Pham Trung

好的。但是有一个自动测试系统。我的代码没有通过这个测试： checkComparatorChangeAfterAddingTasks [失败] 检查输出是否按升序排序，并且是否存在优先级低于前一个任务的任务。 - lorantalas

所以，我认为解决方案一定存在。 - lorantalas

我在大学有一个任务，这个任务太长了，在这里写整个任务太麻烦，但大部分需要的信息都在上面。然后我有一个检查任务的系统，其中包含一些测试。我无法通过名为“checkComparatorChangeAfterAddingTask”的测试。 - lorantalas

heapify() 必须保持堆属性。 - lorantalas