java heapify 方法与比较器

Question

我正在尝试写一个 class HeapQueue。我将根的左 child 存储在 2 * indexOfRoot + 1 索引处，将右 child 存储在 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);
}
}

队列存储 object 个 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;
}
}

我在 HeapQueue 中有一个方法 heapify():

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() 功能有问题。但我找不到错误。有人可以帮忙吗？

Answer 1

你只是从最大堆更改为最小堆，这破坏了整个堆结构！

问题是，当你改变比较器时，调用heapify(0)是不够的，因为，例如，这个结构：

heapify后，1不会向上移动，因为heapify(0)后，程序跳转到右子，也就是2从那个我们无法达到 1.

您可以创建另一个堆！

你可以看看这个answer，基本上，在改变比较器的时候，你只是破坏了堆结构！

Answer 2

您需要做的不仅仅是向下堆化（就像您在堆化中所做的那样——将节点向下推到树上）或向上堆化（就像在提供方法中所做的那样——将节点向上拉到树上）。这些只能用于分别在删除或添加时修复单个节点。堆的其余部分必须已经遵守堆规则。

您需要完全重新堆砌结构。这可以在线性时间内完成，方法是从结构的底部开始并将每个根下推到正确的子树。把它想象成运行对每个节点进行堆化，子节点从完整树的 tail/end 开始。

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

heapifydown 是你的 heapify 函数。

Answer 3

我通过创建函数解决问题 `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;
}

java heapify 方法与比较器

java heapify method with comparator

java

algorithm

data-structures

heap

priority-queue

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

java heapify 方法与比较器

java heapify method with comparator

java

algorithm

data-structures

heap

priority-queue

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

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