COMP90038 Algorithms and Complexity
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
mailto:munoz.m@unimelb.edu.au
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.
• How is this accomplished?
INJECT(e) EJECT()
Unsorted array or list
Sorted array or list
Heap 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
• 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.
• This way, the heap condition is
very simple:
• For all i {0,1,…,n, we must
have H[i] ≤ H[i/2].
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:
• 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
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) 2 9 7 6 5 8 Stage 2 (maximum deletions) Heapsort Stage 1 (heap construction) 2 9 7 6 5 8 2 9 8 6 5 7 Stage 2 (maximum deletions) Heapsort Stage 1 (heap construction) 2 9 7 6 5 8 2 9 8 6 5 7 2 9 8 6 5 7 Stage 2 (maximum deletions) Heapsort Stage 1 (heap construction) 2 9 7 6 5 8 2 9 8 6 5 7 2 9 8 6 5 7 9 2 8 6 5 7 Stage 2 (maximum deletions) Heapsort Stage 1 (heap construction) 2 9 7 6 5 8 2 9 8 6 5 7 2 9 8 6 5 7 9 2 8 6 5 7 9 6 8 2 5 7 Stage 2 (maximum deletions) Heapsort Stage 1 (heap construction) 2 9 7 6 5 8 2 9 8 6 5 7 2 9 8 6 5 7 9 2 8 6 5 7 9 6 8 2 5 7 Stage 2 (maximum deletions) 9 6 8 2 5 7 Heapsort Stage 1 (heap construction) 2 9 7 6 5 8 2 9 8 6 5 7 2 9 8 6 5 7 9 2 8 6 5 7 9 6 8 2 5 7 Stage 2 (maximum deletions) 9 6 8 2 5 7 7 6 8 2 5 | 9 Heapsort Stage 1 (heap construction) 2 9 7 6 5 8 2 9 8 6 5 7 2 9 8 6 5 7 9 2 8 6 5 7 9 6 8 2 5 7 Stage 2 (maximum deletions) 9 6 8 2 5 7 7 6 8 2 5 | 9 8 6 7 2 5 | 9 Heapsort Stage 1 (heap construction) 2 9 7 6 5 8 2 9 8 6 5 7 2 9 8 6 5 7 9 2 8 6 5 7 9 6 8 2 5 7 Stage 2 (maximum deletions) 9 6 8 2 5 7 7 6 8 2 5 | 9 8 6 7 2 5 | 9 5 6 7 2 | 8 9 Heapsort Stage 1 (heap construction) 2 9 7 6 5 8 2 9 8 6 5 7 2 9 8 6 5 7 9 2 8 6 5 7 9 6 8 2 5 7 Stage 2 (maximum deletions) 9 6 8 2 5 7 7 6 8 2 5 | 9 8 6 7 2 5 | 9 5 6 7 2 | 8 9 7 6 5 2 | 8 9 2 6 5 | 7 8 9 Heapsort Stage 1 (heap construction) 2 9 7 6 5 8 2 9 8 6 5 7 2 9 8 6 5 7 9 2 8 6 5 7 9 6 8 2 5 7 Stage 2 (maximum deletions) 9 6 8 2 5 7 7 6 8 2 5 | 9 8 6 7 2 5 | 9 5 6 7 2 | 8 9 7 6 5 2 | 8 9 2 6 5 | 7 8 9 6 2 5 | 7 8 9 5 2 | 6 7 8 9 Heapsort Stage 1 (heap construction) 2 9 7 6 5 8 2 9 8 6 5 7 2 9 8 6 5 7 9 2 8 6 5 7 9 6 8 2 5 7 Stage 2 (maximum deletions) 9 6 8 2 5 7 7 6 8 2 5 | 9 8 6 7 2 5 | 9 5 6 7 2 | 8 9 7 6 5 2 | 8 9 2 6 5 | 7 8 9 6 2 5 | 7 8 9 5 2 | 6 7 8 9 5 2 | 6 7 8 9 2 | 5 6 7 8 9 2 5 6 7 8 9 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)