Understanding SORT method in priority queue

Question

I have a code which my classmate has written.

The problem is that I cannot understand what the SORT METHOD DOES.

As far as I can tell, it orders the priority queue hasn't been modified. Instead the heapify method is a method which helps to manipulate the heap (in this case a MIN HEAP), which allows an element A[i] to scroll down the heap, until it reaches its correct position.

Am I wrong?

package priorityQueue;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.NoSuchElementException;


public class BinaryHeap 
{
protected static <P,E> Element<P,E> extractMinimum(ArrayList<Element<P, E>> priorityQueue, Comparator<Element<P,E>> priorityComparator, HashMap<E, Integer> mapping) throws NoSuchElementException 
{
    if (priorityQueue.size() == 0) 
        throw new NoSuchElementException();
    if (priorityQueue.size() == 1) 
        return priorityQueue.remove(0);

    Element<P,E> first = priorityQueue.get(0);
    mapping.remove(first.getElement());

    Element<P,E> newFirst = priorityQueue.get(priorityQueue.size()-1);
    mapping.remove(newFirst.getElement());

    priorityQueue.set(0, priorityQueue.remove(priorityQueue.size()-1));
    mapping.put(newFirst.getElement() , 0);
    heapify(priorityQueue, priorityComparator, mapping,0);
    return first;
}

protected static <P,E> void sort (ArrayList<Element<P, E>> priorityQueue, Comparator<Element<P,E>> priorityComparator, HashMap<E, Integer> mapping, int index) 
{
    int i = index;
    while(i > 0)
    {
        int middle = (i - 1)/2;
        Element<P,E> element = priorityQueue.get(i);
        Element<P,E> parent = priorityQueue.get(middle);
        if(priorityComparator.compare(element, parent)<0) 
        {
            mapping.replace(element.getElement(), middle);
            mapping.replace(parent.getElement(), i);
            priorityQueue.set(i, parent);
            priorityQueue.set(middle, element);
            i = middle;
        } 
        else 
            break;
    }
}

protected static <P,E> void heapify(ArrayList<Element<P, E>> priorityQueue, Comparator<Element<P,E>> priorityComparator, HashMap<E,Integer> map, int index) 
{
    int left = (2*index) + 1;
    while (left < priorityQueue.size()) 
    {
        int max=left;
        int right = left+1;
        if (right < priorityQueue.size()) 
        { // there is a right child
            if (priorityComparator.compare(priorityQueue.get(right), priorityQueue.get(left)) < 0) 
                max = max + 1;
        }
        if (priorityComparator.compare(priorityQueue.get(index), priorityQueue.get(max)) > 0) 
        {
            Element<P,E> temp = priorityQueue.get(index);
            swap(priorityQueue,map,temp,index,max,left);
        } 
        else 
            break;
    }
}

protected static <P,E> boolean insert(ArrayList<Element<P, E>> priorityQueue, Element<P, E> element, Comparator<Element<P,E>> priorityComparator, HashMap<E, Integer> mapping)
{
    if(mapping.containsKey(element.getElement()) == false) 
    {
        priorityQueue.add(element);
        mapping.put(element.getElement(), priorityQueue.size()-1);
        sort(priorityQueue, priorityComparator, mapping, priorityQueue.size()-1);
        return true;
    }
    else
        return false;
}

protected static <P,E> ArrayList<Element<P,E>> heapSort(ArrayList<Element<P,E>> priorityQueue, Comparator<Element<P,E>> priorityComparator, HashMap<E, Integer> mapping)
{
    ArrayList<Element<P,E>> minimumHeap = new ArrayList<>();
    while(priorityQueue.isEmpty() == false)
        minimumHeap.add(BinaryHeap.extractMinimum(priorityQueue, priorityComparator, mapping));
    return minimumHeap;
}

protected static <T,E> void changePriority(ArrayList<Element<T,E>> priorityQueue, Element<T, E> element, Element<T,E> newElementPriority, HashMap<E, Integer> map, Comparator<Element<T,E>> priorityComparator) throws NoSuchElementException
{
    if(map.containsKey(element.getElement()) == false)
        throw new NoSuchElementException();

    int index = map.get(element.getElement());
    boolean topDown = priorityComparator.compare(priorityQueue.get(index), newElementPriority) > 0;
    priorityQueue.get(index).setPriority(newElementPriority.getPriority());

    if(topDown) 
        sort(priorityQueue, priorityComparator, map, index);
    else 
        heapify(priorityQueue, priorityComparator, map, index);
}

private static<P,E> void swap(ArrayList<Element<P, E>> priorityQueue, HashMap<E,Integer> map,Element<P, E> temp, int index, int max, int left) 
{
    map.replace(priorityQueue.get(index).getElement(), max);
    map.replace(priorityQueue.get(max).getElement(), index);
    priorityQueue.set(index, priorityQueue.get(max));
    priorityQueue.set(max, temp);
    index = max;
    left = (2*index) + 1;
}
}

Any Help please

Answer 1

The sort method there is usually called something like heapifyUp or bubbleUp or siftUp. It differs from heapify in that it moves nodes up the tree. heapify moves nodes down the tree. Others call the function that moves nodes down sink, and the function that moves up is called swim.

Whatever you call it, the way it works is very simple:

while node_index > 0
    if the node is smaller than its parent
      swap the node with its parent
      node_index = parent_index

This method is used when adding an item. For example, given this heap:

    2
 3     5
4 7   6

You want to add the value 1 to the heap. So you place it in the array at the lowest, left-most position. In this case, as the right child of 5:

    2
 3     5
4 7   6 1

Then, you compare the new node with its parent. Since 1 < 5, you swap the nodes:

    2
 3     1
4 7   6 5

The node index is still not 0 (the root), so you compare again. 1 < 2, so you swap again:

    1
 3     2
4 7   6 5

And now you again have a valid heap.