Java heapify method with comparator

Question

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

Saved object in the Task queue.

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

Through my task, the comparator can be changed using the setComparator() method after adding the task to the queue. By default, 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 } } 

As an example, another comparator could 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:

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

It is right. But when I change Comparator to otherComparator :

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

Result:

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

It is not right. The correct 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 the heapify() function. But I can not find the error. Can anyone help?

Answer 1

I solve the problem by creating a rebuild() function:

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

Answer 2

You just go from maximum heap to minimum heap , which breaks the whole structure of the heap!

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

  4 / \ 3 2 / 1 

After heapify 1 will not move up, because after heapify(0) program will go to the correct child , which is 2, and from this we will not be able to reach 1.

You can just create another bunch!

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

Answer 3

You need to do more than just remove (like in heapify - pushing a node down the tree) or push it up (like in your suggestion method - pull the node up in the tree). They will only work to fix one node when deleting or adding, respectively. The rest of the heap should already follow the heap rule.

You need to completely restore the structure. This can be done in linear time, starting from the bottom of the structure and pushing each root onto the correct subtree. Think about it how to run heapify down for each node with children, starting at the tail / end of the full tree.

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

Where heapifydown is your heapify function.