CS代考 COMP90038 Algorithms and Complexity – cscodehelp代写

COMP90038 Algorithms and Complexity
Priority Queues, Heaps and Ohrimenko
(Slides from Harald Søndergaard)
Lecture 13
Semester 2, 2021
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 1 / 1

New lecturer
Dr Olya Ohrimenko (part 2)
PhD from Brown University
6 years Microsoft Research UK
Joined UoM in 2020 as senior lecturer Research in security, privacy, cryptography
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 2 / 1

Priority Queues
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.
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 3 / 1

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
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 4 / 1

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.
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 5 / 1

Some Uses of Priority Queues
Job scheduling done by your operating system. The OS will usually have a notion of “importance” of different jobs.
Traffic management (e.g., arrival times of network requests)
(Discrete event) simulation of complex systems (like traffic, or weather). Here priorities are typically event times.
Many sophisticated algorithms make essential use of priority queues (Huffman encoding and many shortest-path algorithms, for example).
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 6 / 1

Possible Implementations of the Priority Queue
Assume priority = key.
Inject(e) Eject()
Unsorted array or list Sorted array or list
How is this accomplished?

…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort
© University of Melbourne 7 / 1

Possible Implementations of the Priority Queue
Assume priority = key.
Inject(e) Eject()
O(log n)
O(log n)
Unsorted array or list Sorted array or list Heap
How is this accomplished?

…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort
© University of Melbourne 8 / 1

Heaps (High Level)
The heap is a very useful data structure for priority queues, used in many algorithms.
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.
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 9 / 1

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.)
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 10 / 1

Heaps and Non- of these are heaps? 
10 25 25
5 20 20 10 20 10
3 7 12 25 3 12 7 5 3 12 5
25 25 25
7 20 20 5 25 25 3 5 12 10 7 12 25 7 25 7
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 11 / 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.
0
X
1 TO 23
GSMN
4567 AERAI
8 9 10 11 12
X
T
O
G
S
M
N
A
E
R
A
I
H:
0 1 2 3 4 5 6 7 8 9 10 11 12
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 12 / 1

Heaps as Arrays
This way, the heap condition is very simple:
For all i ∈ {0,1,…,n}, we must have
H[i] ≤ H[i/2].
0
X
1 TO 23
GSMN
4567 AERAI
8 9 10 11 12
X
T
O
G
S
M
N
A
E
R
A
I
H:
0 1 2 3 4 5 6 7 8 9 10 11 12
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 13 / 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.
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 14 / 1

Injecting a
Place the new item at the end; then let it “climb up”, repeatedly swapping with parents that are smaller:
X TO
GSMN AERAIP
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 15 / 1

Left blank
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 16 / 1

Injecting a
Place the new item at the end; then let it “climb up”, repeatedly swapping with parents that are smaller:
XX TO⇒TP
GSMNGSON AERAIP AERAIM
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 17 / 1

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:
2 97 6583
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.
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 18 / 1

Left blank
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 19 / 1

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:
222 97⇒98⇒98 658365736573
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.
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 20 / 1

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:
299 98⇒28⇒68 657365732573
…………… . …. …………….. …
Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 21 / 1

Turning H[1] . . . H[n] into a Heap, Bottom-Up
for i ← ⌊n/2⌋ downto 1 do k←i
v ← H[k]
heap ← False
while not heap and 2 × k ≤ n do
j ← 2 × k
if j < n then if H[j] < H[j + 1] then j ← j + 1 if v ≥ H[j] then heap ← True else H[k] ← H[j] k←j H[k] ← v Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort ▷ j is k’s left child ▷ j is k’s largest child ▷ Promote H[j] ............... . .... ................. ... © University of Melbourne 22 / 1 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): ∑h ∑ ∑h i = i · 2h−i = 2h+1 − h − 2 i=1 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. ............... . .... ................. ... i=1 nodes at level i Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 23 / 1 Left blank ............... . .... ................. ... Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 24 / 1 Ejecting a Maximal Element from a Heap: Example 9 68 2573 ............... . .... ................. ... Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 25 / 1 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). 93 68⇒68⇒ 25732579 88 6 3 ⇒ 6 7 25792539 ............... . .... ................. ... Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 26 / 1 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.  ............... . .... ................. ... Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 27 / 1 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? ............... . .... ................. ... Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 27 / 1 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. ............... . .... ................. ... Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 28 / 1 Properties of Heapsort On average slower than quicksort, but stronger performance guarantee. Truly in-place. Not stable. ............... . .... ................. ... Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 29 / 1 Summary & Next Lecture Today: Priority Queues via Heaps; Heap operations and algorithms Next lecture: Tranform-and-Conquer, more on trees. ............... . .... ................. ... Algorithms and Complexity (Sem 2, 2021) Priority Queues, Heaps and Heapsort © University of Melbourne 30 / 1