Data Structures and Algorithms
Chapter 9
Priority Queues
• Each element in a queue is associated with a key.
• When an element is removed, an element with a minimal (or maximal) key is removed.
• Usually keys are numbers.
• Objects can be used as keys as far as there is a total ordering among those objects.
Priority Queues ADT
• insert(k, v): Create an entry with key k and value v in the priority queue.
• min( ): Returns (but does not remove) an entry (k, v) with the minimum key. Returns null if the priority queue is empty.
• removeMin( ): Removes and returns an entry (k, v) with the minimum key. Returns null if the priority queue is empty.
• size( ): Returns the number of entries in the priority queue.
• isEmpty( ): Returns true if the priority queue is empty. Returns false, otherwise.
• Illustration
Method insert(17, A)
Return Value
Priority Queue Contents {(17, A)}
{(4, P) , (17, A)}
{(4, P) , (15, X), (17, A)} {(4, P) , (15, X), (17, A)} {(4, P) , (15, X), (17, A)} {(4, P) , (15, X), (17, A)} {(15, X), (17, A)}
insert(4, P) insert(15, X) size( ) isEmpty( ) min( ) removeMin( ) removeMin( ) removeMin( ) removeMin( ) size( ) isEmpty( )
3
false (4, P) (4, P) (15, X) (17, A) null
0
true
{(17, A)} {}
{}
{ }
Priority Queues ADT
{ }
1
2
3 4}
Priority Queues Implementation
• An element in a priority queue has key and value.
• Entry interface is used to store a key-value pair.
public interface Entry
V getValue();
• PriorityQueue interface
1 2 3 4
public interface PriorityQueue
5
6 7}
IllegalArgumentException; Entry
Priority Queues Implementation
boolean isEmpty();
Entry
Entry
Priority Queues Implementation
• Keys must have total ordering.
• Total ordering means there is a linear ordering among all
keys.
• Total ordering of a comparison rule, ≤, satisfies the following properties:
– Comparability property: k1 ≤ k2 or k2 ≤ k1.
– Antisymmetric property: If k1 ≤ k2 and k2 ≤ k1, then k1 = k2.
– Transitive property: If k1 ≤ k2 and k2 ≤ k3, then k1 ≤ k3.
• If keys have total ordering, minimal key is well defined
• keymin is a key such that: keymin ≤ k, for all k
Priority Queues Implementation
• Two ways to compare objects in Java – compareTo and compare
• compareTo is defined in java.util.Comparable interface.
• A class must override and implement the compareTo
method.
• Ordering defined in the compareTo method is called
natural ordering.
• Usage: a.compareTo(b) returns – a negative number, if a < b
– zero,ifa=b
– a positive number, if a > b
• Many Java classes implemented Comparable interface.
Priority Queues Implementation
• compare is defined in java.util.Comparator interface.
• Use this to compare not by natural ordering
• Need to write a separate customized comparator
• Example: To compare strings by length (natural ordering is lexicograhic ordering).
• First, write a customized comparator method
1
2
3
4
5 6} 7}
if (a.length() < b.length()) return -1;
else if (a.length() == b.length()) return 0; else return 1;
public class StringLengthComparator implements Comparator
• Then, use it as follows:
Priority Queues Implementation
8 public class ComparatorTest {
9 public static void main(String[] args) {
10 StringLengthComparator c = new StringLengthComparator();
11 String s1 = “tiger”;
12 String s2 = “sugar”;
13 String s3 = “coffee”;
14 String s4 = “cat”;
15 System.out.println(“Compare s1 and s2: ” + c.compare(s1, s2)); // 0
16 System.out.println(“Compare s1 and s3: ” + c.compare(s1, s3)); // -1
17 System.out.println(“Compare s1 and s4: ” + c.compare(s1, s4)); // 1
27 }
28 }
• •
Provides common features for different concrete implementations.
Priority Queues AbstractPriorityQueue Base Class
An entry in a queue is implemented as PQEntry:
protected static class PQEntry
private V v; // value
public PQEntry(K key, V value) {
1
2
3
4
5
6 7}
8 public K getKey() { return k; }
9 public V getValue() { return v; }
10 protected void setKey(K key) { k = key; }
11 protected void setValue(V value) { v = value; }
12 }
k = key;
v = value;
Priority Queues
Implementing Using a Heap • Implementation with an unsorted list
• Implementation with a sorted list
• We will focus on implementation with heap.
• Heap is a binary tree with the following properties:
– Heap-order property: In a heap T, for every position p, except the root, the key stored at p is greater than or equal to the key stored at p’s parent. (minimum-oriented heap)
– Complete binary tree property: A heap is a complete binary tree.
Priority Queues
Implementing Using a Heap • Complete binary tree
– Levels0,1,…,h–1ofThavethemaximalnumber of nodes (in other words, level i has 2i nodes, where 0 ≤i ≤h–1),and
– Nodesatlevelhareintheleftmostpossiblepositions at that level.
(a) (b)
yes
no
Priority Queues
Implementing Using a Heap
• Priority queue implemented using a heap example:
h logn • Height of a heap with n entries is
Priority Queues
Implementing Using a Heap • Adding an entry to a heap
– Step 1: Add new entry at the “end” of the heap
– Step 2: Reorganize the heap (because adding new entry may violate the heap-order property)
• Reorganization is done by up-heap bubbling.
(27,L)
(43,G)
(36,O)
(51,M)
(75,E)
(5,U)
(24,D)
(18,A)
(61,V)
(47,H)
Priority Queues
Implementing Using a Heap • Illustration
New entry (5,U) is added to the end of the heap.
(12,B)
Since 5 < 61, (5,U) is swapped with its parent (61,V).
(18,P)
(14,K)
(27,L)
(43,G)
(36,O)
(51,M)
(75,E)
(61,V)
(24,D)
(18,A)
(5,U)
(47,H)
Priority Queues
Implementing Using a Heap • Illustration
Since 5 < 14, (5,U) is swapped with its parent (14,K).
(12,B)
(18,P)
(14,K)
(27,L)
(43,G)
(36,O)
(51,M)
(75,E)
(61,V)
(24,D)
(18,A)
(14,K)
(47,H)
Priority Queues
Implementing Using a Heap • Illustration
Since 5 < 12, (5,U) is swapped with its parent (12,B).
(12,B)
(18,P)
(5,U)
(27,L)
(43,G)
(36,O)
(51,M)
(75,E)
(61,V)
(24,D)
(18,A)
(14,K)
(47,H)
Priority Queues
Implementing Using a Heap • Illustration
We reached the root. So, stop. This is the final heap.
(5,U)
(18,P)
(12,B)
Priority Queues
Implementing Using a Heap • Removing the entry with minimal key
– Step1: Remove the root
– Step 2: Last node is move up to the root and perform
down-heap bubbling.
• Down-heap bubbling is opposite of up-heap bubbling.
Root entry (12,B) is removed.
(12,B)
The last entry (75,E) is moved up to be the new root.
(27,L)
(43,G)
(36,O) (51,M)
(75,E)
(24,D)
(18,A)
(61,V)
(47,H)
Priority Queues
Implementing Using a Heap • Illustration
Left child has smaller key. So, (18,P) is swapped with (75,E)
(75,E)
(27,L)
(43,G)
(36,O)
(51,M)
(24,D)
(18,A)
61,V
(47,H)
(18,P)
(32,K)
(18,P)
(32,K)
(27,L)
(43,G)
(36,O) (51,M)
Priority Queues
Implementing Using a Heap • Illustration
Right child has smaller key. So, (18,A) is swapped with (75,E)
(18,P)
(24,D)
(18,A) (61,V)
(47,H)
Left child has smaller key. So, (36,O) is swapped with (75,E)
(18,P)
(27,L)
(43,G)
(36,O)
(51,M)
(24,D)
(75,E) (61,V)
(47,H)
(75,E)
(32,K)
(18,A)
(32,K)
This is the final heap.
(27,L)
(43,G)
(75,E)
(51,M)
(24,D)
(36,O) (61,V)
(47,H)
Priority Queues
Implementing Using a Heap • Illustration
(18,A)
(32,K)
(18,P)
Priority Queues Array-Based Heap
• The level number of a position p, f(p), is defined as follow:
– Ifpistheroot,f(p)=0
– If p is the left child of position q, f(p) = 2*f(q) + 1 – If p is the right child of position q, f(p) = 2*f(q) + 2
• The level number is used as the index in an array where the entry with position p is stored.
Priority Queues Array-Based Heap
• Then, the entry at position p is stored in A[f(p)].
• Index of the root node is 0.
• Indexofleftchildofp=2*f(p)+1
• Index of right child of p = 2*f(p) + 2
( f ( p ) 1) / 2 • Indexofparentofp=
• Example
Priority Queues Array-Based Heap
0
(12,B)
12
(18,P) (14,K)
3456
(24,D) (18,A)
(61,V) (47,H)
7 8 9 10
11
(27,L) (43,G) (36,O) (51,M)
(75,E)
(47,H) (27,L) (43,G) (36,O) (51,M)
0 1 2 3 4 5 6 7 8 9 10 11
(12,B) (18,P) (14,K) (24,D) (18,A) (61,V)
(75,E)
Priority Queues Array-Based Heap
• HeapPriorityQueue class implements a priority queue using a heap.
• A heap is implemented using ArrayList.
• Will briefly discuss upheap, downheap, insert, and
removeMin methods.
• HeapPriorityQueue.java code
Priority Queues Analysis of Heap-Based Priority Queue
• insertion:
– upheap method takes O(log n) – So, insertion takes O(log n)
• removeMin:
– downheap method takes O(log n) – So, removeMin takes O(log n)
Method Running Time size, isEmpty O(1)
min O(1) insert O(log n) removeMin O(log n)
Priority Queues Bottom-up Heap Construction
• Given n elements, we can build a heap with n successive insertions => takes O(n log n) time.
• O(n) time algorithm
– Begin at the parent of the last node, move backward
to the root.
– At each node, perform down-heap bubbling.
• Illustration
7
8 9 10 11 12 13 14
Priority Queues Bottom-up Heap Construction
14 5 8 25 9 11 17 16 15 4 12 6 7 23 20 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0
14
12
58
3456
25 9 11 17
16 15 4 12 6 7 23 20
7
8
9
10 11 }
downheap(j);
Priority Queues Bottom-up Heap Construction
• Java implementation
1 public HeapPriorityQueue(K[ ] keys, V[ ] values) {
2
3
4
5 6}
super();
for (int j=0; j < Math.min(keys.length, values.length); j++)
heap.add(new PQEntry<>(keys[j], values[j])); heapify();
protected void heapify() {
int startIndex = parent(size()-1); // start at PARENT of last entry for (int j=startIndex; j >= 0; j–) // loop until processing the root
• java.util.PriorityQueue
• An entry is a single element.
Priority Queues Java’s Priority Queue
• Some operations in Java’s PriorityQueue
– add(E e): Inserts the specified element e to the priority queue.
– isEmpty( ): Returns true if the priority queue contains no element.
– peek( ): Retrieves, but does not remove, a minimal element from the priority queue.
– remove( ): Removes a minimal element from the priority queue.
– size( ): Returns the number of elements in the priority queue.
Priority Queues Heap-Sort
• Uses array-based heap data structure.
• In-place sorting: no additional storage is used.
• Uses a maximum-oriented heap.
• maximum-oriented heap: In a heap T, for every position p, except the root, the key stored at p is smaller than or equal to the key stored at p’s parent.
• Sorting steps:
1. Given n elements are inserted into a maximum-oriented heap. 2. Repeat the following until only one node is left in the heap:
Root is swapped with the last node, heap size is decremented, perform down-heap bubbling.
• Illustration
Down‐heap bubbling is applied on the root.
8
14 11
Priority Queues Sorting with Priority Queue
The maximum‐oriented heap after the first step. The root node and the last node is swapped. Heap size is decremented.
25
14 11
25 14 11 9 5 8
8 14 11 9 5 25
958
9 5 25
• Illustration
Priority Queues Sorting with Priority Queue
The root node is swapped with the last node. Heap size is decremented.
14
9 11
14 9 11 8 5 25
Down‐heap bubbling is applied on the root.
5
9 11
5 9 11 8 14 25
8 5 25
8 14 25
• Illustration
Priority Queues Sorting with Priority Queue
The root node is swapped with the last node. Heap size is decremented.
11 95
11 9 5 8 14 25
Down‐heap bubbling is applied on the root.
8 95
8 9 5 11 14 25
8 14 25
11 14 25
• Illustration
The root node is swapped with the last node. Heap size is decremented.
9 85
Down‐heap bubbling is applied on the root.
5 89
Priority Queues Sorting with Priority Queue
9 8 5 11 14 25
5 8 9 11 14 25
11 14 25
11 14 25
• Illustration
Priority Queues Sorting with Priority Queue
The root node is swapped with the last node. Heap size is decremented.
8 59
8 5 9 11 14 25
At this time the array is sorted.
5 8 9 11 14 25
5 89
11 14 25
11 14 25
Priority Queues Adaptable Priority Queue
• Can remove arbitrary entry (not just the root).
• Can replace the key of an entry.
• Can replace the value of an entry.
• Uses location-aware entities to find an entry in a priority queue efficiently.
• Location-aware entry keeps one more field, current index of the entry in an array-based heap.
Priority Queues Adaptable Priority Queue
• Illustration of removeMin
(5,K,0) (14,R,1) (8,D,2) (29,S,3)
(15,B,4)
(13,E,5)
5
14 moved up
deleted
29 15 13
(13,E,0) (14,R,1) (8,D,2) (29,S,3)
(15,B,4)
down‐heap bubble
13
14 8
29 15
8
Priority Queues Adaptable Priority Queue
• Illustration of removeMin
(8,D,0) (14,R,1)
(13,E,2) (29,S,3) (15,B,4)
29
15
14
13
8
Priority Queues HeapAdaptablePriorityQueue Class
• Extends HeapPriorityQueue class.
• An entry in the queue
protected static class AdaptablePQEntry
public AdaptablePQEntry(K key, V value, int j) {
1
2
3
4
5 6}
7 public int getIndex() { return index; }
8 public void setIndex(int j) { index = j; }
9}
super(key, value); // this sets the key and value index = j; // this sets the new field
Priority Queues HeapAdaptablePriorityQueue Class
• HeapAdaptablePriorityQueue.java code.
References
• M.T. Goodrich, R. Tamassia, and M.H. Goldwasser, “Data Structures and Algorithms in Java,” Sixth Edition, Wiley, 2014.