How do you use a binary heap to implement a priority queue?

Question

Despite the fact that I've got a BS in Computer Science (and this was covered in the university), I've never been able to understand the relationship between binary heaps and priority queues. It just... doesn't click. I completely understand what a binary heap is and I know how to implement one in an array. I also know what a priority queue is. But how do the two of them fit together?

A quick google query shows a lot of articles like this one. Which kind of explains it, yet I'm left more questions:

1. A priority queue needs to ensure that if two items with the same priority are added, then they will be removed in the same order that they were added. How does a binary heap ensure this? (In fact, if I'm not mistaken, then the border case where ALL the items have the same priority would produce a heap which would violate this rule).
2. What happens when you remove the root from the heap, then put in the last element in place of the root, and then need to swap it with one of the children - but both children have the same value. How do you pick which one to swap with? (Holding in mind the FIFO rule of same-priority items)

What am I missing here?

Answer 1

A priority queue is an abstract data type like "stack" or "associative array." There can are many different ways to implement a priority queue - you can use binary heaps, binomial heaps, Fibonacci heaps, pairing heaps, etc.

I don't believe that there is any intrinsic requirement that a priority queue be "stable" and require that elements with equal priorities be dequeued in the same relative order in which they were added, much in the same way that there's no instrinsic requirement that a sorting algorithm be stable (though many are). It's a nice property to have, but usually it's not guaranteed. This is why, for example, a standard heapsort isn't a stable sort.

Fortunately, it's not too hard to adjust binary heaps to be stable. Keep a counter associated with the binary heap. Whenever you add an element to the heap, tag it with the current value of the counter and increment the counter. When doing heap operations, use the counter as a tiebreaker to determine which value is smaller if two values compare equal. Essentially, this changes the comparison to a lexicographical comparison first on the real value and then on the insertion order.

Hope this helps!

Answer 2

Simple java code to illustrate priority queues

package heap;

import java.util.Comparator;

/**
 * Generic implementation of priority queue based on heap with add and pop
 * Reverse is min heap
 *  Average Worst case
 Space  O(n)    O(n)
 Search O(n)    O(n)
 Insert O(1)    O(log n)
 Delete O(log n)    O(log n)
 * Created by  on 9/7/14.
 */
public class BinaryHeap<T extends Comparable> {
    private final Comparable[] pq;
    private int size = 0;

    private final Comparator<Comparable> comparator;

    private final static Comparator<Comparable> comparatorMax = new Comparator<Comparable>() {
        @Override
        public int compare(Comparable o1, Comparable o2) {
            return o1.compareTo(o2);
        }
    };


    public BinaryHeap(int size) {
        this(size,false);
    }

    public BinaryHeap(int size, boolean reverse) {
        pq = new Comparable[size];

        if(reverse)
            comparator = comparatorMax.reversed();
        else
            comparator = comparatorMax;
    }


    public void add(T entry) throws Exception {
        if(size == pq.length)
            throw new Exception("Heap Overflow Exception: "+ entry);
        pq[size] = entry;
        size++;
        maxHeapify(pq, getNewPos(size - 1), true);
        print();
    }

    public Comparable pop() throws Exception {
        if(size == 0)
            return null;
        size--;
        swap(pq,0,size);
        Comparable entry = pq[size];
        pq[size] = null;
        maxHeapify(pq, 0, false);
        System.out.println("Popped: "+ entry);
        print();
        return entry;
    }

    public Comparable find(T entry) {
        for(int i=0; i < size; i++)
            if(comparator.compare(entry,pq[i]) == 0)
                return entry;

        return null;
    }

    private void maxHeapify(Comparable[] entries, int pos, boolean swimUp) throws Exception {
        int leftPos = 2 * pos + 1;
        int rightPos = 2 * pos + 2;

        Comparable parent = entries[pos];
        Comparable left = null;
        if(leftPos < size)
            left = entries[leftPos];

        Comparable right = null;

        if(rightPos < size)
            right = entries[rightPos];

        if(left == null && right == null)
            return; //For swim Down case

        if (parent == null)
            throw new Exception("Entry not found Exception: " + pos);

        //Find the largest of left and right for swaps
        int largest = pos;
        if (left != null && comparator.compare(parent,left) < 0) {
            largest = leftPos;
        }

        if (right != null && comparator.compare(parent,right) < 0) {
            if(largest == pos)
                largest = rightPos;
            else if(comparator.compare(right,entries[largest]) > 0) {
                largest = rightPos;
            }

        }

        if (largest != pos) {
            swap(entries, largest, pos);
            if (swimUp && pos == 0)
                return;

            maxHeapify(entries, swimUp ? getNewPos(pos) : largest, swimUp);
        }
    }


    private void swap(Comparable[] entries, int pos1, int pos2) {
        Comparable temp = entries[pos2];
        entries[pos2] = entries[pos1];
        entries[pos1] = temp;
    }

    private int getNewPos(int pos) {
        int newPos = pos / 2;//Takes the floor automatically because of int
        if (pos > 0 && pos % 2 == 0)
            newPos = (pos / 2) - 1;

        return newPos;
    }

    public void print() {
        System.out.print("[");
        int i=0;
        for(;i < size-1; i++)
            System.out.print(pq[i] + ",");

        System.out.print(pq[i]+"]");
        System.out.println();
    }

    public static void main(String[] args) {
        BinaryHeap<Integer> pq = new BinaryHeap<Integer>(100);
        try {
            pq.add(5);

            pq.add(3);

            pq.add(9);

            pq.add(16);
            pq.add(2);
            pq.add(3);
            pq.add(19);
            pq.add(500);
            pq.add(90);
            pq.add(1);
            pq.add(91);
            pq.add(600);
            pq.pop();
            pq.pop();
            pq.pop();
            pq.pop();
            pq.pop();
            pq.pop();
            pq.pop();
            pq.pop();
            pq.pop();
            pq.pop();
            pq.pop();
            pq.pop();


        }catch (Exception e) {
            e.printStackTrace();
        }
    }
}