3. Heaps and Priority Queues

You should already know what a queue is.

For those who don’t it is an ADT that store elements in the order they arrive.

Queues implement a FIFO (First In First Out) strategy.

However, sometimes elements need to be dealt in priority.

Activity

  • Do you have an idea of applications that requires to process some elements in priority without changing the global FIFO strategy?

In this topic we will discuss and implement a priority queue.

3.1. Model

A Priority Queue is an ADT that has the two following operations:

  • Insertion: Inserts a new element

  • Delete: Find, return and remove the minimum element in the queue

As in many ADT you can add more operations.

Priority Queues have many applications, especially in greedy algorithms.

3.2. Simple implementations

We could think of a very simple implementation of a priority queue.

Activity

  • Discuss and come up with a simple implementation.

  • What is the complexity for insertion? Deletion?

When we say simple implementation, we usually think Linked List.

If we have a linked list:

  • Insertion: \(O(1)\)

  • DeleteMin: \(O(N)\)

Activity

  • Why is the deletion \(O(N)\)?

We want to delete the minimum element, thus to reduce the complexity we could use a sorted linked list.

If we consider a sorted list:

  • Insertion: \(O(N)\)

  • DeleteMin: \(O(1)\)

So, neither implementation is very efficient.

Note

The first implementation is better, as in average you’re inserting more than you’re deleting.

3.3. Binary Heap

Binary Heap is the most popular implementation of this ADT.

Usually we call priority queues heaps.

3.3.1. Structure

A heap is a binary tree that is completely filled with the possible exception of the bottom level.

Note

By definition it is a complete binary tree.

An example of a complete binary tree.

../../_images/complete_binary_tree.png

As a complete binary tree is regular, it is very easy to represent in an array.

../../_images/array_implementation.png

We can take any element in the array at position \(i\):

  • The left child is at position \(2i\).

  • The right child is at position \((2i + 1)\).

  • The parent is in position \(\lfloor i/2\rfloor\).

It gives us the following structure of the ADT:

 1/**
 2 * The OPriorityQueue implements the Queue interface by building a heap in an ArrayList.
 3 * The heap is structured so that the “smallest” item is at the top.
 4 * @param <E> Type of element stored in the queue.
 5 */
 6public class OPriorityQueue<E extends Comparable<E>> extends AbstractQueue<E> implements Queue<E>{
 7
 8    //Data Fields
 9    /** The ArrayList to hold the data */
10    private ArrayList<E> theData;
11
12    /**
13     * Construct the class without any capacity.
14     */
15    public OPriorityQueue(){
16        theData = new ArrayList<>();
17    }
18
19    /**
20     * Construct the queue.
21     * @param cap is the capacity of the queue.
22     */
23    public OPriorityQueue(int cap){
24        if (cap < 1)
25            throw new IllegalArgumentException();
26        theData = new ArrayList<>(cap + 1);
27    }
28    /**
29     * Inserts the specified element into this queue if it is possible to do
30     * so immediately without violating capacity restrictions.
31     * When using a capacity-restricted queue, this method is generally
32     * preferable to {@link #add}, which can fail to insert an element only
33     * by throwing an exception.
34     *
35     * @param e the element to add
36     * @return {@code true} if the element was added to this queue, else
37     * {@code false}
38     * @throws ClassCastException       if the class of the specified element
39     *                                  prevents it from being added to this queue
40     * @throws NullPointerException     if the specified element is null and
41     *                                  this queue does not permit null elements
42     * @throws IllegalArgumentException if some property of this element
43     *                                  prevents it from being added to this queue
44     */
45    @Override
46    public boolean offer(E e) {
47    }
48    /**
49     * Retrieves and removes the head of this queue,
50     * or returns {@code null} if this queue is empty.
51     *
52     * @return the head of this queue, or {@code null} if this queue is empty
53     */
54    @Override
55    public E poll() {
56    }
57}

3.3.2. Heap-Order Property

The Heap-Order property allows operations to be performed quickly.

To find the minimum element quickly, it needs to be at the root.

The heap-order property:

For every node \(X\), the key in the parent of \(X\) is smaller than (or equal to) the key in \(X\), with the exception of the root.

The following is a good illustration of a heap:

../../_images/two_trees.png

The left tree is a heap, the right tree is not.

3.3.3. Basic Operations

The two basic operations are simple to implement.

3.3.3.1. insert

To insert an element \(X\):

  • Create a hole in the next available location

  • If placing \(X\) in the hole violates the heap-order condition.

    • Put the parent’s hole in the hole, and \(X\) at the parent’s position.

    • Otherwise place \(X\) in the hole.

  • It continues until \(X\) can be placed in a hole.

Example

  • Consider the following tree.

  • We want to insert the number \(14\).

../../_images/insert_00.png

  • We’re creating a hole for 14.

  • As it would break the heap-order property, we place the parent (\(31\)) in the hole instead.

../../_images/insert_01.png

  • We continue the process.

../../_images/insert_02.png

Activity

  • Insert 5, 59 and 10 in the previous binary heap.

  • Draw the tree after each step.

Implementation

 1    /**
 2     * Inserts the specified element into this queue if it is possible to do
 3     * so immediately without violating capacity restrictions.
 4     * When using a capacity-restricted queue, this method is generally
 5     * preferable to {@link #add}, which can fail to insert an element only
 6     * by throwing an exception.
 7     *
 8     * @param e the element to add
 9     * @return {@code true} if the element was added to this queue, else
10     * {@code false}
11     * @throws ClassCastException       if the class of the specified element
12     *                                  prevents it from being added to this queue
13     * @throws NullPointerException     if the specified element is null and
14     *                                  this queue does not permit null elements
15     * @throws IllegalArgumentException if some property of this element
16     *                                  prevents it from being added to this queue
17     */
18    @Override
19    public boolean offer(E e) {
20        // Add the item to the heap.
21        theData.add(e);
22        //child is the newly inserted item.
23        int child = theData.size() - 1;
24        int parent = (child -1) / 2;
25        while (parent >= 0 && theData.get(parent).compareTo(theData.get(child))>0){
26            swap(parent, child);
27            child = parent;
28            parent = (child -1) / 2;
29        }
30        return false;
31    }

The time complexity of the insertion in the worst-case \(O(\log N)\).

3.3.3.2. deleteMin

Finding the minimum is easy, but removing it is hard.

  • When a minimum is removed, a hole is created.

  • We should place the last element in the heap \(X\) in the hole.

  • If we can place it, we’re done otherwise

  • We slide the smaller children in the hole.

  • We continue until \(X\) can be placed in the hole.

Example

  • Consider the previous tree.

  • We want to delete the number 13.

  • It creates a hole, 31 the last element cannot be inserted.

../../_images/delete_01.png

  • We’re move 14 up to fill the hole.

  • Inserting 31 would break the heap-order property, so we place the smaller children (19) in the hole instead.

../../_images/delete_02.png

  • We continue the process.

../../_images/delete_03.png

We call this strategy percolating down.

Activity

  • Delete 14 and draw the tree after each step.

Implementation

 1    /**
 2     * Retrieves and removes the head of this queue,
 3     * or returns {@code null} if this queue is empty.
 4     *
 5     * @return the head of this queue, or {@code null} if this queue is empty
 6     */
 7    @Override
 8    public E poll() {
 9        if(isEmpty())
10            return null;
11        //Save the top of the heap
12        E result = theData.get(0);
13        //If only one item the remove it
14        if(theData.size() == 1){
15            theData.remove(0);
16            return result;
17        }
18        //Return the last item from the ArrayList and place it into the first position
19        theData.set(0, theData.remove(theData.size() - 1));
20        //The parent starts at the top
21        int parent = 0;
22        while(true){
23            int leftChild = 2 * parent + 1;
24            if (leftChild >= theData.size())
25                break; //out of heap
26            int rightChild = leftChild + 1;
27            int minChild = leftChild; //assume leftChild is smaller
28            //see whether rightChild is smaller
29            if(rightChild < theData.size() && theData.get(leftChild).compareTo(theData.get(rightChild)) > 0){
30                minChild = rightChild;
31            }
32            //assert: minChild is the index of the smaller child
33            //move smaller child if necessary
34            if(theData.get(parent).compareTo(theData.get(minChild)) > 0){
35                swap(parent, minChild);
36                parent = minChild;
37            } else { //heap property restored
38                break;
39            }
40        }
41        return result;
42    }

The time complexity in the worst-case is \(O(\log N)\).

In average it is also \(O(\log N)\).