程序代写代做代考 algorithm data structure COMP90038 – Algorithms and Complexity Lecture 13

COMP90038 – Algorithms and Complexity Lecture 13
COMP90038 Algorithms and Complexity
Lecture 13: Priority Queues, Heaps and Heapsort (with thanks to Harald Søndergaard & Michael Kirley)
Casey Myers Casey.Myers@unimelb.edu.au David Caro Building (Physics) 274

COMP90038 – Algorithms and Complexity
Lecture 13
Review from Lecture 12

COMP90038 – Algorithms and Complexity
Lecture 13
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 be easily maintained as a complete tree, the standard implementation uses an array to represent the tree.

COMP90038 – Algorithms and Complexity Lecture 13
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 queue.

COMP90038 – Algorithms and Complexity
Lecture 13
Some Uses of Priority Queues
• • •
Job scheduling done by you 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).

COMP90038 – Algorithms and Complexity
Lecture 13
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()
Ο(log 𝑛)
Ο(log 𝑛)

COMP90038 – Algorithms and Complexity Lecture 13
The Heap
•
• •
A heap is a complete binary tree which satisfies the heap condition:
– Each child has a priority (key) which is not greater than its parents.
This guarantees 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 that its parents.)

COMP90038 – Algorithms and Complexity Lecture 13
Heaps and Non-Heaps
Which of these are heaps?

COMP90038 – Algorithms and Complexity Lecture 13
Heaps and Non-Heaps
Which of these are heaps?
✘✘

COMP90038 – Algorithms and Complexity Lecture 13
Heaps and Arrays
We can utilise the completeness of the tree and place its elements in level-order in
an array H.

COMP90038 – Algorithms and Complexity Lecture 13
Heaps and 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.

COMP90038 – Algorithms and Complexity Lecture 13
Heaps and Arrays
This way, the heap condition is very simple:
For all
𝑖∈ 0,1,⋯,𝑛,
we must have
𝐻𝑖 ≤𝐻𝑖/2

COMP90038 – Algorithms and Complexity Lecture 13
Properties of the Heap
• The root of the tree H[1] holds a maximal item; the cost of EJECT is Ο 1 heap.
plus time to restore the
• The height of the heap is 𝑙𝑜𝑔!𝑛 .
• 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 position 1 to 𝑛/2 .
• It is easier to understand heap operations if we think of the heap as a tree.

COMP90038 – Algorithms and Complexity Lecture 13
Injecting a New Item
• Place the new item at the end; then let it “climb up”, repeatedly swapping with parents that are smaller.

COMP90038 – Algorithms and Complexity Lecture 13
Injecting a New Item
• Place the new item at the end; then let it “climb up”, repeatedly swapping with parents that are smaller.
• We want to inject “P”.
• We place “P” at the end.
• We let it “climb up”, swapping with smaller parents (“M” and “O”)

COMP90038 – Algorithms and Complexity
Lecture 13
Building a Heap Bottom-Up
• To construct a heap from an arbitrary set of elements, we can just use the inject operation repeatedly. But the construction cost will be 𝑛log 𝑛.

COMP90038 – Algorithms and Complexity
Lecture 13
Building a Heap Bottom-Up: Sifting Down
• To construct a heap from an arbitrary set of elements, we can just use the inject operation repeatedly. But the construction cost will be 𝑛log 𝑛.
• But there is a better way.
• Start with the last parent and move backwards, in level-order.
• Whenever a parent is found to be out of order, let it “sift down” until both children are smaller:

COMP90038 – Algorithms and Complexity
Lecture 13
Algorithm to Turn 𝐻 1, ⋯ , 𝑛 into a Heap, Bottom-Up

COMP90038 – Algorithms and Complexity
Lecture 13
Algorithm to Turn 𝐻 1, ⋯ , 𝑛 into a Heap, Bottom-Up
𝑗 is 𝑘’s left child
𝑗 is 𝑘’s largest child
Promote H[j]

COMP90038 – Algorithms and Complexity
Lecture 13
Algorithm to Turn 𝐻 1, ⋯ , 𝑛 into a Heap, Bottom-Up
𝐻 1,⋯,7
2976583
𝑛
7
𝑖
𝑘
𝑣
𝑗
𝐻[𝑘]
𝐻[𝑗]
𝐻[𝑗 + 1]
not 𝐻𝐸𝐴𝑃
2×𝑘 ≤ 𝑛
𝑗<𝑛 𝐻𝑗 <𝐻[𝑗+1] 𝑣 ≥ 𝐻[𝑗] COMP90038 – Algorithms and Complexity Lecture 13 Algorithm to Turn 𝐻 1, ⋯ , 𝑛 into a Heap, Bottom-Up 𝐻 1,⋯,7 2976583 𝑛 7 𝑖 3 𝑘 3 𝑣 7 𝑗 𝐻[𝑘] 7 𝐻[𝑗] 𝐻[𝑗 + 1] not 𝐻𝐸𝐴𝑃 𝑇𝑅𝑈𝐸 2×𝑘 ≤ 𝑛 𝑇𝑅𝑈𝐸 𝑗<𝑛 𝐻𝑗 <𝐻[𝑗+1] 𝑣 ≥ 𝐻[𝑗] COMP90038 – Algorithms and Complexity Lecture 13 Algorithm to Turn 𝐻 1, ⋯ , 𝑛 into a Heap, Bottom-Up 𝐻 1,⋯,7 2976583 𝑛 7 𝑖 3 𝑘 3 𝑣 7 𝑗 6 𝐻[𝑘] 7 𝐻[𝑗] 8 𝐻[𝑗 + 1] 3 not 𝐻𝐸𝐴𝑃 𝑇𝑅𝑈𝐸 2×𝑘 ≤ 𝑛 𝑇𝑅𝑈𝐸 𝑗<𝑛 𝑇𝑅𝑈𝐸 𝐻𝑗 <𝐻[𝑗+1] 𝑣 ≥ 𝐻[𝑗] COMP90038 – Algorithms and Complexity Lecture 13 Algorithm to Turn 𝐻 1, ⋯ , 𝑛 into a Heap, Bottom-Up 𝐻 1,⋯,7 2976583 𝑛 7 𝑖 3 𝑘 3 𝑣 7 𝑗 6 𝐻[𝑘] 7 𝐻[𝑗] 8 𝐻[𝑗 + 1] 3 not 𝐻𝐸𝐴𝑃 𝑇𝑅𝑈𝐸 2×𝑘 ≤ 𝑛 𝑇𝑅𝑈𝐸 𝑗<𝑛 𝑇𝑅𝑈𝐸 𝐻𝑗 <𝐻[𝑗+1] 𝐹𝐴𝐿𝑆𝐸 𝑣 ≥ 𝐻[𝑗] COMP90038 – Algorithms and Complexity Lecture 13 Algorithm to Turn 𝐻 1, ⋯ , 𝑛 into a Heap, Bottom-Up 𝐻 1,⋯,7 2976583 𝑛 7 𝑖 3 𝑘 3 𝑣 7 𝑗 6 𝐻[𝑘] 7 𝐻[𝑗] 8 𝐻[𝑗 + 1] 3 not 𝐻𝐸𝐴𝑃 𝑇𝑅𝑈𝐸 2×𝑘 ≤ 𝑛 𝑇𝑅𝑈𝐸 𝑗<𝑛 𝑇𝑅𝑈𝐸 𝐻𝑗 <𝐻[𝑗+1] 𝐹𝐴𝐿𝑆𝐸 𝑣 ≥ 𝐻[𝑗] 𝐹𝐴𝐿𝑆𝐸 COMP90038 – Algorithms and Complexity Lecture 13 Algorithm to Turn 𝐻 1, ⋯ , 𝑛 into a Heap, Bottom-Up 𝐻 1,⋯,7 2986583 𝑛 7 𝑖 3 𝑘 6 𝑣 7 𝑗 6 𝐻[𝑘] 8 𝐻[𝑗] 8 𝐻[𝑗 + 1] 3 not 𝐻𝐸𝐴𝑃 𝑇𝑅𝑈𝐸 2×𝑘 ≤ 𝑛 𝑇𝑅𝑈𝐸 𝑗<𝑛 𝑇𝑅𝑈𝐸 𝐻𝑗 <𝐻[𝑗+1] 𝐹𝐴𝐿𝑆𝐸 𝑣 ≥ 𝐻[𝑗] 𝐹𝐴𝐿𝑆𝐸 8 8 COMP90038 – Algorithms and Complexity Lecture 13 Algorithm to Turn 𝐻 1, ⋯ , 𝑛 into a Heap, Bottom-Up 𝐻 1,⋯,7 2986583 𝑛 7 𝑖 3 𝑘 6 𝑣 7 𝑗 6 𝐻[𝑘] 8 𝐻[𝑗] 8 𝐻[𝑗 + 1] 3 not 𝐻𝐸𝐴𝑃 𝑇𝑅𝑈𝐸 2×𝑘 ≤ 𝑛 𝐹𝐴𝐿𝑆𝐸 𝑗<𝑛 𝑇𝑅𝑈𝐸 𝐻𝑗 <𝐻[𝑗+1] 𝐹𝐴𝐿𝑆𝐸 𝑣 ≥ 𝐻[𝑗] 𝐹𝐴𝐿𝑆𝐸 8 8 COMP90038 – Algorithms and Complexity Lecture 13 Algorithm to Turn 𝐻 1, ⋯ , 𝑛 into a Heap, Bottom-Up 𝐻 1,⋯,7 2986583 𝑛 7 𝑖 3 𝑘 6 𝑣 7 𝑗 6 𝐻[𝑘] 7 𝐻[𝑗] 8 𝐻[𝑗 + 1] 3 not 𝐻𝐸𝐴𝑃 𝑇𝑅𝑈𝐸 2×𝑘 ≤ 𝑛 𝐹𝐴𝐿𝑆𝐸 𝑗<𝑛 𝑇𝑅𝑈𝐸 𝐻𝑗 <𝐻[𝑗+1] 𝐹𝐴𝐿𝑆𝐸 𝑣 ≥ 𝐻[𝑗] 𝐹𝐴𝐿𝑆𝐸 COMP90038 – Algorithms and Complexity Lecture 13 Analysis of Bottom-Up Heap Creation • For simplicity, assume the heap is a full binary tree: 𝑛 = 2!"# − 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): !! ) ) 𝑖 = )𝑖+2!/$=2!"#−h−2 $%# &'()* +, -).)- $ $%# • The last equation is easily proved by mathematical induction (or see Levitin Appendix A). • Note that 2!"# − h − 2 < n, so we perform at most a linear number of down-sift operations. Each down-sift is preceded by two key comparison, so the number of comparison is also linear. • Hence we have a linear-time algorithm for heap creation. COMP90038 – Algorithms and Complexity Lecture 13 Ejecting a Maximal Element from a Heap • Here the idea is to swap the root with the last item 𝑧 in the heap, and then let the 𝑧 “sift-down” to its proper place. COMP90038 – Algorithms and Complexity Lecture 13 Ejecting a Maximal Element from a Heap • Here the idea is to swap the root with the last item 𝑧 in the heap, and then let the 𝑧 “sift-down” to its proper place. COMP90038 – Algorithms and Complexity Lecture 13 Ejecting a Maximal Element from a Heap • Here the idea is to swap the root with the last item 𝑧 in the heap, and then let the 𝑧 “sift-down” to its proper place. • After this, the last element (shown here in green) is no longer considered part of the heap, that is, n is decremented. • Clearly ejection is Ο(log 𝑛). COMP90038 – Algorithms and Complexity Lecture 13 Ejecting a Maximal Element from a Heap • Here the idea is to swap the root with the last item 𝑧 in the heap, and then let the 𝑧 “sift-down” to its proper place. • After this, the last element (shown here in green) is no longer considered part of the heap, that is, n is decremented. • Clearly ejection is Ο(log 𝑛). COMP90038 – Algorithms and Complexity Lecture 13 Ejecting a Maximal Element from a Heap • Here the idea is to swap the root with the last item 𝑧 in the heap, and then let the 𝑧 “sift-down” to its proper place. • After this, the last element (shown here in green) is no longer considered part of the heap, that is, n is decremented. • Clearly ejection is Ο(log 𝑛). COMP90038 – Algorithms and Complexity Lecture 13 Ejecting a Maximal Element from a Heap • Here the idea is to swap the root with the last item 𝑧 in the heap, and then let the 𝑧 “sift-down” to its proper place. • After this, the last element (shown here in green) is no longer considered part of the heap, that is, n is decremented. • Clearly ejection is Ο(log 𝑛). COMP90038 – Algorithms and Complexity Lecture 13 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. COMP90038 – Algorithms and Complexity Lecture 13 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. COMP90038 – Algorithms and Complexity Lecture 13 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. COMP90038 – Algorithms and Complexity Lecture 13 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. • Ejected: T COMP90038 – Algorithms and Complexity Lecture 13 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. • Ejected: T COMP90038 – Algorithms and Complexity Lecture 13 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. • Ejected: T COMP90038 – Algorithms and Complexity Lecture 13 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. • Ejected: T, S COMP90038 – Algorithms and Complexity Lecture 13 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. • Ejected: T, S • COMP90038 – Algorithms and Complexity Lecture 13 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. • Ejected: T, S, R COMP90038 – Algorithms and Complexity Lecture 13 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. • Ejected: T, S, R COMP90038 – Algorithms and Complexity Lecture 13 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. • Ejected: T, S, R, O COMP90038 – Algorithms and Complexity Lecture 13 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. • Ejected: T, S, R, O COMP90038 – Algorithms and Complexity Lecture 13 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. • Ejected: T, S, R, O, N COMP90038 – Algorithms and Complexity Lecture 13 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. • Ejected: T, S, R, O, N COMP90038 – Algorithms and Complexity Lecture 13 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. • Ejected: T, S, R, O, N, I, G COMP90038 – Algorithms and Complexity Lecture 13 Heapsort • Heapsort is a Θ(𝑛 log 𝑛) sorting algorithm, based on the idea from this exercise. • Given unsorted array 𝐻 1,⋯,𝑛 : – Step 1 Turn 𝐻 into a heap. – Step2Applytheejectoperation𝑛−1times. COMP90038 – Algorithms and Complexity Lecture 13 Properties of Heapsort • On average slower that quicksort, but stronger performance guarantee. • Truly in place. • Not stable. COMP90038 – Algorithms and Complexity Lecture 13 Coming Up Next • We will look at the “Transform and Conquer” paradigm (Levitin Section 6.1).

Related Posts