COMP90038 Algorithms and Complexity
Lecture 13: Priority Queues, Heaps and Heapsort (with thanks to Harald Søndergaard)
Andres Munoz-Acosta
munoz.m@unimelb.edu.au
Peter Hall Building G.83
Where to find me?
• My office is at the Peter Hall building (Room G.83)
Where to find me?
• My office is at the Peter Hall building (Room G.83)
Where to find me?
• My office is at the Peter Hall building (Room G.83)
• Consultation hours:
• Wednesdays 10:00am-11:00am
• By appointment on Monday/Friday (limited slots)
Heaps and Priority Queues
• The heap is a very useful data structure for priority queues, used in many algorithms.
• A priority queue is a set (or pool) of elements.
• An element is injected into the priority queue together with a priority (often the
key value itself) and elements are ejected according to priority.
• We think of the heap as a partially ordered binary tree.
• Since it can easily be maintained as a complete tree, the standard implementation uses an array to represent the tree.
The Priority Queue
• As an abstract data type, the priority queue supports the following operations on a “pool” of elements (ordered by some linear order):
• find an item with maximal priority
• insert a new item with associated priority • test whether a priority queue is empty
• eject the largest element
• Other operations may be relevant, for example:
• replace the maximal item with some new item
• construct a priority queue from a list of items
• join two priority queues
Some Uses of Priority Queues
• Job scheduling done by your operating system. The OS will usually have a notion of “importance” of different jobs.
• (Discrete event) simulation of complex systems (like traffic, or weather). Here priorities are typically event times.
• Numerical computations involving floating point numbers. Here priorities are measures of computational “error”.
• Many sophisticated algorithms make essential use of priority queues (Huffman encoding and many shortest-path algorithms, for example).
Stacks and Queues as Priority Queues
• Special instances are obtained when we use time for priority:
• If “large” means “late” we obtain the stack.
• If “large” means “early” we obtain the queue.
Possible Implementations of the Priority Queue
• Assume priority = key.
Unsorted array or list Sorted array or list Heap
• How is this accomplished?
INJECT(e)
EJECT()
O(log n)
O(log n)
The Heap
• A heap is a complete binary tree which satisfies the heap condition: Each child has a priority (key) which is no greater than its parent’s.
• This guarantees that the root of the tree is a maximal element.
• (Sometimes we talk about this as a max-heap – one can equally well have min-heaps, in which each child is no smaller than its parent.)
Heaps and Non-Heaps
• Which of these are heaps?
Heaps as Arrays
• We can utilise the completeness of the tree and place its elements in level-order in an array H.
• Note that the children of node i will be nodes 2i and 2i + 1.
Heaps as Arrays
• TWheiscwanayu, tihliesehtehaepccomndpilteitoeniesss voef rtyhesimtrepelea: nd place its elements in level-order in an array H.
• For all i {0,1,…,n, we must have H[i] ≤ H[i/2].
• Note that the children of node i will be nodes 2i and 2i + 1.
Properties of the Heap
• The root of the tree H[1] holds a maximal item; the cost of EJECT is O(1) plus time to restore the heap.
• The height of the heap is log2 n.
• Each subtree is also a heap.
• The children of node i are 2i and 2i+1.
• The nodes which happen to be parents are in array positions 1 to n/2.
• It is easier to understand the heap operations if we think of the heap as a tree.
Injecting a New Item
• Place the new item at the end; then let it “climb up”, repeatedly swapping with parents that are smaller:
Injecting a New Item
• Place the new item at the end; then let it “climb up”, repeatedly swapping with parents that are smaller:
Injecting a New Item
• Place the new item at the end; then let it “climb up”, repeatedly swapping with parents that are smaller:
Building a Heap Bottom-Up
• To construct a heap from an arbitrary set of elements, we can just use the inject operation repeatedly. The construction cost will be n log n. But there is a better way:
• Start with the last parent and move backwards, in level-order. For each parent node, if the largest child is larger than the parent, swap it with the parent.
Building a Heap Bottom-Up
• To construct a heap from an arbitrary set of elements, we can just use the inject operation repeatedly. The construction cost will be n log n. But there is a better way:
• Start with the last parent and move backwards, in level-order. For each parent node, if the largest child is larger than the parent, swap it with the parent.
Building a Heap Bottom-Up
• To construct a heap from an arbitrary set of elements, we can just use the inject operation repeatedly. The construction cost will be n log n. But there is a better way:
• Start with the last parent and move backwards, in level-order. For each parent node, if the largest child is larger than the parent, swap it with the parent.
Building a Heap Bottom-Up: Sifting Down
• Whenever a parent is found to be out of order, let it “sift down” until both children are smaller:
Building a Heap Bottom-Up: Sifting Down
• Whenever a parent is found to be out of order, let it “sift down” until both children are smaller:
Building a Heap Bottom-Up: Sifting Down
• Whenever a parent is found to be out of order, let it “sift down” until both children are smaller:
Turning H[1] … H[n] into a Heap, Bottom-Up
Analysis of Bottom-Up Heap Creation
• For simplicity, assume the heap is a full binary tree: n = 2h+1 – 1. Here is an upper bound on the number of “down-sifts” needed (consider the root to be at level $h$, so leaves are at level 0):
• The last equation is easily proved by mathematical induction.
• Note that 2h+1 – h – 2 < n, so we perform at most a linear number of down-sift operations. Each
down-sift is preceded by two key comparisons, so the number of comparisons is also linear.
• Hence we have a linear-time algorithm for heap creation.
Ejecting a Maximal Element from a Heap
• Here the idea is to swap the root with the last item z in the heap, and then let z "sift down" to its proper place.
• After this, the last element (here shown in green) is no longer considered part of the heap, that is, n is decremented.
• Clearly ejection is O(log n).
Ejecting a Maximal Element from a Heap
• Here the idea is to swap the root with the last item z in the heap, and then let z "sift down" to its proper place.
• After this, the last element (here shown in green) is no longer considered part of the heap, that is, n is decremented.
• Clearly ejection is O(log n).
Ejecting a Maximal Element from a Heap
• Here the idea is to swap the root with the last item z in the heap, and then let z "sift down" to its proper place.
• After this, the last element (here shown in green) is no longer considered part of the heap, that is, n is decremented.
• Clearly ejection is O(log n).
Ejecting a Maximal Element from a Heap
• Here the idea is to swap the root with the last item z in the heap, and then let z "sift down" to its proper place.
• After this, the last element (here shown in green) is no longer considered part of the heap, that is, n is decremented.
• Clearly ejection is O(log n).
Exercise: Build and Then Deplete a Heap
• First build a heap from the items S, O, R, T, I, N, G.
• Then repeatedly eject the largest, placing it at the end of the heap.
Exercise: Build and Then Deplete a Heap
• First build a heap from the items S, O, R, T, I, N, G.
• Then repeatedly eject the largest, placing it at the end of the heap.
• Anything interesting to notice about the tree that used to hold a heap?
Heapsort
• Heapsort is a Θ(n log n) sorting algorithm, based on the idea from this exercise.
• Given an unsorted array H[1] ... H[n]:
• Step 1: Turn H into a heap.
• Step 2: Apply the eject operation n-1 times.
Heapsort
Stage 1 (heap construction) Stage 2 (maximum deletions)
29 7 6 5 8
Heapsort
Stage 1 (heap construction) Stage 2 (maximum deletions)
29 7 6 5 8 298657
Heapsort
Stage 1 (heap construction) Stage 2 (maximum deletions)
29 7 6 5 8 298657 298657
Heapsort
Stage 1 (heap construction)
29 7 6 5 8 298657 298657 928657
Stage 2 (maximum deletions)
Heapsort
Stage 1 (heap construction)
29 7 6 5 8 298657 298657 928657 96 8 2 5 7
Stage 2 (maximum deletions)
Heapsort
Stage 1 (heap construction)
29 7 6 5 8 298657 298657 928657 96 8 2 5 7
Stage 2 (maximum deletions)
968257
Heapsort
Stage 1 (heap construction) Stage 2 (maximum deletions)
29 7 6 5 8 9 6 8 2 5 7 298657 76825|9 298657
928657
96 8 2 5 7
Heapsort
Stage 1 (heap construction) Stage 2 (maximum deletions)
29 7 6 5 8 9 6 8 2 5 7 298657 76825|9 298657 86725|9 928657
96 8 2 5 7
Heapsort
Stage 1 (heap construction)
29 7 6 5 8 298657 298657 928657 96 8 2 5 7
Stage 2 (maximum deletions)
968257 76825|9 86725|9 5 6 7 2| 8 9
Heapsort
Stage 1 (heap construction)
29 7 6 5 8 298657 298657 928657 96 8 2 5 7
Stage 2 (maximum deletions)
968257 76825|9 86725|9 5 6 7 2| 8 9 7652|89 265|789
Heapsort
Stage 1 (heap construction)
29 7 6 5 8 298657 298657 928657 96 8 2 5 7
Stage 2 (maximum deletions)
968257 76825|9 86725|9 5 6 7 2| 8 9 7652|89 265|789 625|789 52|6789
Heapsort
Stage 1 (heap construction)
29 7 6 5 8 298657 298657 928657 96 8 2 5 7
Stage 2 (maximum deletions)
968257 76825|9 86725|9 5 6 7 2| 8 9 7652|89 265|789 625|789 52|6789 52|6789 2| 5 6 7 8 9 256789
Properties of Heapsort
• On average slower than quicksort, but stronger performance guarantee.
• Truly in-place. • Not stable.
Next lecture
• Transform-and-Conquer
• Pre-sorting (Levitin Section 6.1)