6

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?

6
  • Can you share your swap function too? Commented Jan 14, 2015 at 3:37
  • @PhamTung It's there. Commented Jan 14, 2015 at 3:41
  • Hmm how can you set otherComparator as Comparator for the heap? it is not implementing same interface? Commented Jan 14, 2015 at 4:02
  • @PhamTrung By the task comparator for the heap can be changed, and by setComparator(), I can change comparator and re-build heap by heapify(). But it don't work. Commented Jan 14, 2015 at 4:10
  • I see, ok, I can reproduce the bug now :) Commented Jan 14, 2015 at 4:13

3 Answers 3

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!

Sign up to request clarification or add additional context in comments.

11 Comments

@AlexeySharov yes, the reason is, my tree structure is different, so it luckily run correctly, but heapify(0) is not enough, as I pointed above!
If you do this: heap.offer(t1); heap.offer(t2); heap.offer(t3); heap.offer(t4); You will have my problem. I cannot forget to heapify because I have heapify() in setComparator().
Why heapify(0) in setComparator() isn't enough? It have to be enough.
@AlexeySharov, no, calm down man :), just reread my explanation, as heapify is based on the fact that the structure in the heap is correct, but in this heap, when you change from max to min heap, all condition is violated, so you cannot count on heapify any more.
This question isn't my question. "That is, if I keep the array unchanged, what happens when I append an element to the internal array?" But I want to change my heap after changing comparator and adding new element.
|
1

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.

3 Comments

For each heapifyDown, I see that it needs to travel O(log n) from top to bottom, which basically is O(nlogn), however, this is not a tight bound, can you provide a mathematical prove that this is O(n)?
Your time complexity is log(n) + log(n-1) + ... + log 1 = log(n*(n-1)*(n-2)...) = log(n!) ~ O(n log n). More info
It only looks that way, but each pass orders the tree more and more. geeksforgeeks.org/g-fact-85
1

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

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.