java heapify method with comparator

Question

I am trying to write a class HeapQueue. I stored left child of root at 2 * indexOfRoot + 1 index, and right child at 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);
}
}

Queue storaged object of 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;
}
}

I have a method heapify() in 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);
        }
    }

}

By my task comparator may be changed by method setComparator() after adding task to queue. Default Comparator is:

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
    }
 }

As example other comparator may be:

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
    }
 }

I create my HeapQueue and add some elements.

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());

Result is:

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

    4
   / \
  3   2
 /
1 

It's right. But when I change Comparator to otherComparator:

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

Result is:

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

    2
   / \
  3   4
 /
1 

It's wrong. Right answer is something like this:

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

    1
   / \
  2   3
 /
4 

I think I have a problem with heapify() function. But I cannot find a mistake. Can someone help?

Answer 1

You just change from max heap to min heap, which broken whole heap structure!.

The problem is, when you change the comparator, calling heapify(0) is not enough, because, for example, this structure:

             4
            / \
           3   2
          /
         1

After heapify, 1 will not move up, because after heapify(0), the program jump to the right child, which is 2 and from that we cannot reach 1.

You can just create another heap!

You can look at this answer, basically, when changing the comparator, you just broke the heap structure!

Answer 2

You need to do more than just heapify down (as you have in heapify -- pushing a node down the tree) or heapify up (as you have in the offer method -- pulling a node up the tree). Those will only work to fix up a single node on removal or addition respectively. The rest of the heap has to already abide by the heap rule.

You need to entirely reheapify the structure. This can be done in linear time by starting at the bottom of the structure and pushing down each root to the correct subtree. Think of it like running heapify down for each node with children starting at the tail/end of the complete tree.

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

Where heapifydown is your heapify function.

Answer 3

I solve problem by creating function 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;
}