用比较器的java heapify方法

Question

我正在努力写一堂课HeapQueue.我将root的左子项存储在 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()功能有问题.但我找不到错误.有人可以帮忙吗？

Answer 1

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