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.
As a complete binary tree is regular, it is very easy to represent in an array.
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:
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\).
We’re creating a hole for 14.
As it would break the heap-order property, we place the parent (\(31\)) in the hole instead.
We continue the process.
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.
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.
We continue the process.
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)\).