CS代写 Topic 5: : - PowCoder代写

Topic 5: :
􏰀 Heaps (CLRS Ch. 6.1-6.5) 􏰀 Max-Heapify
􏰀 Build-Max-Heap 􏰀 Heapsort
􏰀 Priority Queues

Heaps data structure:
􏰀 An array A[1..n] of n comparable keys (either ‘≥’ or ‘≤’)
􏰀 An implicit binary tree, where
􏰀 A[2j] is the left child of A[j]
􏰀 A[2j + 1] is the right child of A[j] 􏰀 So: A[⌊ 2j ⌋] is the parent of A[j]
􏰀 We focus on max-heap (there is also min-heap). Keys satisfy the max-heap property: for every node j we have A[⌊ 2j ⌋] ≥ A[j] (i.e., key of parent ≥ key of node)
􏰀 So the root (A[1]) is the maximum among the n keys.
􏰀 This gives the alternative definition of a heap: In any sub-heap, the root is
the largest key
􏰀 Viewing heap as a binary tree, height of the tree is h = ⌊lg n⌋. h is called the height of the heap (the number of edges on the longest root-to-leaf path)
􏰀 All layers i from 0 to h−1 are full.
􏰀 A heap of height h can hold [2h , …, 2h+1 − 1] keys. Since lg n − 1 < k ≤ lg n ⇐⇒ n < 2k+1 and 2k ≤ n ⇐⇒2k ≤n<2k+1 Topic 5: Heaps Heaps - examples: 􏰀 Examples: 􏰀 A = [31], or any array with a single element 􏰀 A=[6,3,5] 􏰀 A = [6,3,5,1,2,4] 􏰀 A = [100,42,78,13,41,77,12] 􏰀 Non-examples: 􏰀 A=[1,2] 􏰀 A=[4,3,5] 􏰀 A = [100,42,78,13,41,77,12,14] 􏰀 Remember: The heap is stored in an array. The tree is implicit. 􏰀 Thus, all layers except for maybe the last are full. Topic 5: Heaps Max-Heapify: 􏰀 It makes an almost-heap into a heap. 􏰀 Almost-heap: only the root of the heap might violates the heap-property 􏰀 Pseudocode: procedure Max-Heapify(A,i) **turns almost-heap into a heap **pre-condition: tree rooted at A[i] is an almost-heap **post-condition: tree rooted at A[i] is a heap lc ← leftchild(i) rc ← rightchild(i) largest ← i if (lc ≤ heapsize(A) and A[lc] > A[largest]) then
largest ← lc
if (rc ≤ heapsize(A) and A[rc] > A[largest]) then
largest ← rc **largest = index of max{A[i], A[rc], A[lc]} if (largest ̸= i) then
exchange A[i] ↔ A[largest] Max-Heapify(A, largest)
􏰀 WC running time: O(h) = O(lg n).
Topic 5: Heaps

Building a heap from an array:
􏰀 Given an array of n keys A[1], A[2], . . . , A[n], permute the keys in A so that A is a heap
􏰀 Outline:
1. Look at the implicit binary tree that A induces
2. Consider the leafs (the bottom-level nodes in the binary tree): Each of them has a single-key ⇒ each of them is a heap
3. Consider the nodes on the second-to-last level:
The subtrees rooted at these nodes are almost-heaps: Max-Heapify them into heaps!
4. Now, consider the nodes on the third-to-last level: The subtrees rooted at those nodes are almost-heaps: Max-Heapify them into heaps!
5. The whole tree becomes an almost heap: Max-Heapify tree root into a heap!
Topic 5: Heaps

Building a heap from an array (cont’d):
􏰀 Pseudocode:
procedure Build-Max-Heap(A) **turn an array into a heap
heapsize(A) ← length[A]
for (i←􏰆length[A]􏰇 downto 1) do
Max-Heapify(A, i)
A[1..10] = {4, 1, 7, 9, 3, 10, 14, 8, 2, 16}:
Max-Heapify(A, 5):
21 37

4 9 5 3 6 10 7 14
8 8 9 2 10 16
Topic 5: Heaps

Building a heap from an array (cont’d):
􏰀 Pseudocode:
procedure Build-Max-Heap(A) **turn an array into a heap
heapsize(A) ← length[A]
for i←􏰆length[A]􏰇 downto 1
do Max-Heapify(A,i)
A[1..10] = {4, 1, 7, 9, 3, 10, 14, 8, 2, 16}
Max-Heapify(A, 4):
21 37

4 9 5 16 6 10 7 14
8 8 9 2 10 3
Topic 5: Heaps

Building a heap from an array (cont’d):
􏰀 Pseudocode:
procedure Build-Max-Heap(A) **turn an array into a heap
heapsize(A) ← length[A]
for i←􏰆length[A]􏰇 downto 1
do Max-Heapify(A,i)
A[1..10] = {4, 1, 7, 9, 3, 10, 14, 8, 2, 16}
Max-Heapify(A, 3):
2137

4 9 5 16 6 10 7 14
8 8 9 2 10 3
Topic 5: Heaps

Building a heap from an array (cont’d):
􏰀 Pseudocode:
procedure Build-Max-Heap(A) **turn an array into a heap
heapsize(A) ← length[A]
for i←􏰆length[A]􏰇 downto 1
do Max-Heapify(A,i)
A[1..10] = {4, 1, 7, 9, 3, 10, 14, 8, 2, 16}
Max-Heapify(A, 2):
21 314

4 9 5 16 6 10 7 7
8 8 9 2 10 3
Topic 5: Heaps

Building a heap from an array (cont’d):
􏰀 Pseudocode:
procedure Build-Max-Heap(A) **turn an array into a heap
heapsize(A) ← length[A]
for i←􏰆length[A]􏰇 downto 1
do Max-Heapify(A,i)
A[1..10] = {4, 1, 7, 9, 3, 10, 14, 8, 2, 16}
Max-Heapify(A, 1):
216 314

4 9 5 3 6 10 7 7
8 8 9 2 10 1
Topic 5: Heaps

Building a heap from an array (cont’d):
􏰀 Pseudocode:
procedure Build-Max-Heap(A) **turn an array into a heap
heapsize(A) ← length[A]
for i←􏰆length[A]􏰇 downto 1
do Max-Heapify(A,i)
A[1..10] = {4, 1, 7, 9, 3, 10, 14, 8, 2, 16}
29 314

4 8 5 3 6 10 7 7
8 4 9 2 10 1
Topic 5: Heaps

Building a heap from an array (cont’d):
􏰀 Pseudocode:
procedure Build-Max-Heap(A) **turn an array into a heap
heapsize(A) ← length[A]
for i←􏰆length[A]􏰇 downto 1
do Max-Heapify(A,i)
􏰀 Worst case running time: because we make at most n2 calls to Max-Heapfiy, each takes O(lg(n)) we have O(n log(n)).
Topic 5: Heaps

Building a heap from an array (cont’d):
􏰀 Correct bound is O(n):
􏰀 Max-Heapify’s runtime is O(k) for a node at height k.
􏰀 At height 1 we have at most n/2 nodes. 􏰀 At height 2 we have at most n/4 nodes. 􏰀 At height 3 we have at most n/8 nodes. 􏰀 …
􏰀 At height lg(n) we have at most 1 node. 􏰀 So runtime is upper bounded by:
lg(n) lg(n) 3 lg(n)  3 lg(n)  􏰊k·n =n􏰊k=n􏰊k+􏰊k ≤n􏰊k+􏰊2k/2
Topic 5: Heaps
2k 2k2k2k2k2k k=1 k=1 k=4 k=1 k=4
3lg(n)􏰈 ∞􏰉 =n􏰊k+􏰊1≤n1+2+3+􏰊1
 2k 2k/2 2 4 8 2k/2 k=1 k=4 k=4
≤ n 2+ =n 2+ 1 ≤n 2+ 1 ≤6n  2􏰋1 1−0.75
􏰀 Tighter analysis will yield running time is actually 2n − lg n − 2.

Heapsort algorithm:
􏰀 We can use heaps to design another sorting algorithm. 􏰀 Heapsort is a sorting algorithm using heaps.
􏰀 The ideas:
􏰀 Build the array into a heap (WC cost Θ(n))
􏰀 The first key A[1] is the maximum and thus should be in the last position
when sorted
􏰀 Exchange A[1] with A[n], and decrease heap size by 1
􏰀 Max-Heapify the array A[1..(n − 1)], which is an almost-heap, into a heap.
􏰀 Repeat for positions n − 1,n − 2,…,2.
􏰀 An example: A[1..10] = {4, 1, 7, 9, 3, 10, 14, 8, 2, 16}
Build into a heap:
1
2 3
4 5 6 7
Topic 5: Heaps

Heapsort algorithm (cont’d):
􏰀 We can use heaps to design another sorting algorithm. 􏰀 Heapsort is a sorting algorithm using heaps.
􏰀 The ideas:
􏰀 Build the array into a heap (WC cost Θ(n))
􏰀 The first key A[1] is the maximum and thus should be in the last position
when sorted
􏰀 Exchange A[1] with A[n], and decrease heap size by 1
􏰀 Max-Heapify the array A[1..(n − 1)], which is an almost-heap, into a heap.
􏰀 Repeat for positions n − 1,n − 2,…,2.
􏰀 An example: A[1..10] = {4, 1, 7, 9, 3, 10, 14, 8, 2, 16}
Heapsize = 10:
29 314

4 8 5 3 6 10 7 7
8 4 9 2 10 1
Topic 5: Heaps

Heapsort algorithm (cont’d):
􏰀 We can use heaps to design another sorting algorithm. 􏰀 Heapsort is a sorting algorithm using heaps.
􏰀 The ideas:
􏰀 Build the array into a heap (WC cost Θ(n))
􏰀 The first key A[1] is the maximum and thus should be in the last position
when sorted
􏰀 Exchange A[1] with A[n], and decrease heap size by 1
􏰀 Max-Heapify the array A[1..(n − 1)], which is an almost-heap, into a heap.
􏰀 Repeat for positions n − 1,n − 2,…,2.
􏰀 An example: A[1..10] = {4, 1, 7, 9, 3, 10, 14, 8, 2, 16}
Exchange A[1] and A[10], decrement Heapsize to 9, and Max-Heapify it
29 314

4 8 5 3 6 10 7 7
8 4 9 2 10 16
Topic 5: Heaps
(restore the heap property):

Heapsort algorithm (cont’d):
􏰀 We can use heaps to design another sorting algorithm. 􏰀 Heapsort is a sorting algorithm using heaps.
􏰀 The ideas:
􏰀 Build the array into a heap (WC cost Θ(n))
􏰀 The first key A[1] is the maximum and thus should be in the last position
when sorted
􏰀 Exchange A[1] with A[n], and decrease heap size by 1
􏰀 Max-Heapify the array A[1..(n − 1)], which is an almost-heap, into a heap.
􏰀 Repeat for positions n − 1,n − 2,…,2.
􏰀 An example: A[1..10] = {4, 1, 7, 9, 3, 10, 14, 8, 2, 16} Resultant tree: Heapsize = 9:
29 310

48536177
8 4 9 2 10 16
Topic 5: Heaps

Heapsort algorithm (cont’d):
􏰀 We can use heaps to design another sorting algorithm. 􏰀 Heapsort is a sorting algorithm using heaps.
􏰀 The ideas:
􏰀 Build the array into a heap (WC cost Θ(n))
􏰀 The first key A[1] is the maximum and thus should be in the last position
when sorted
􏰀 Exchange A[1] with A[n], and decrease heap size by 1
􏰀 Max-Heapify the array A[1..(n − 1)], which is an almost-heap, into a heap.
􏰀 Repeat for positions n − 1,n − 2,…,2.
􏰀 An example: A[1..10] = {4, 1, 7, 9, 3, 10, 14, 8, 2, 16}
Exchange A[1] and A[9], decrement Heapsize to 9, and Max-Heapify it
29 310

48536177
8 4 9 1410 16
Topic 5: Heaps
(restore the heap property):

Heapsort algorithm (cont’d):
􏰀 We can use heaps to design another sorting algorithm. 􏰀 Heapsort is a sorting algorithm using heaps.
􏰀 The ideas:
􏰀 Build the array into a heap (WC cost Θ(n))
􏰀 The first key A[1] is the maximum and thus should be in the last position
when sorted
􏰀 Exchange A[1] with A[n], and decrease heap size by 1
􏰀 Max-Heapify the array A[1..(n − 1)], which is an almost-heap, into a heap.
􏰀 Repeat for positions n − 1,n − 2,…,2.
􏰀 An example: A[1..10] = {4, 1, 7, 9, 3, 10, 14, 8, 2, 16} Resultant tree: Heapsize = 8:
29 37

48536172
8 4 9 1410 16
Topic 5: Heaps

Heapsort algorithm (cont’d):
􏰀 Pseudocode:
procedure Heapsort(A) **post-condition: sorted array
Build-Max-Heap(A)
for (i ← heapsize(A) downto 2) do
exchange A[1] ↔ A[i] heapsize(A) ← heapsize(A) − 1 Max-Heapify(A, 1)
􏰀 WC running time analysis:
􏰀 Build-Max-Heap in O(n)
􏰀 For each position i = n, n − 1, …, 2, Max-Heapify takes O(lg i), so in total
this is Θ(n log(n)). nn
􏰊 log(i) ≤ 􏰊 log(n) = n log(n) i=2 i=1
􏰊log(i) ≥ 􏰊 log(n/2)=⌊n2⌋·(log(n)−1)≥ 13nlog(n) i=2 i=⌈n/2⌉
􏰀 So, in total Θ(n log n)
Topic 5: Heaps

Heapsort algorithm — Conclusion:
􏰀 WC running time:
􏰀 Build-Max-Heap takes O(n).
􏰀 n − 1 calls to Max-Heapify: O(n log n).
􏰀 OverallO(nlogn).
􏰀 In the worst-case, It is easy to see that Max-heapify can take Ω(log n). 􏰀 Thus the WC running time is also Ω(n log n).
􏰀 Total: Θ(nlogn).
􏰀 Correctness – prove on your own:
􏰀 Correctness for Max-Heapify?
(a recursion, use induction on height of i)
􏰀 LI for Build-Max-Heap?
For any j ≥ i, the subtree rooted at j is heap (CLRS p.157)
􏰀 LI for heapsort
A[1, …, i] is a heap & A[i + 1, …n] contains the n − i largest keys, sorted.
Topic 5: Heaps

Priority Queue:
􏰀 An abstract data structure for maintaining a set S of elements each associated with a key
􏰀 Key — represents the priority of the element
􏰀 Example: a set of jobs to be scheduled on a shared computer.
􏰀 The jobs arrive and should be placed in the queue.
􏰀 Each has a priority. Queue should be with respect to this.
􏰀 To perform a job, we “extract” the one in the queue with highest priority.
􏰀 In general, a PQ supports these operations:
􏰀 initialize — insert all keys at once
􏰀 insert — a new element
􏰀 maximum — return the element with the maximum key
􏰀 extract maximum — return the maximum and remove the element from
􏰀 increase key — increase the priority for an element
􏰀 Implementation? Heap !!!
Topic 5: Heaps

Priority Queue:
􏰀 Initialize(A) — Build-Max-Heap. So this takes Θ(n) time.
􏰀 Maximum(A) — Return A[1]. Takes Θ(1) time.
􏰀 Extract-Maximum(A) —
Like deleting from an array: put A[n] as the new first element before returning the max.
The difference: we Max-Heapify(A, 1) to make this array into a heap. Θ(lg n) time.
procedure Heap-Extract-Max(A) ∗∗ precondition: A isn’t empty max ← A[1]
A[1] ← A[heapsize[A]] heapsize[A] ← heapsize[A] − 1 if (heapsize[A] > 0) then
Max-Heapify(A, 1) return max
􏰀 Increase-Key(A,i,new key)
􏰀 Insert(A,new key)
Topic 5: Heaps

Priority Queue:
􏰀 Initialize(A)
􏰀 Maximum(A)
􏰀 Extract-Maximum(A)
􏰀 Increase-Key(A, i, new key) — The inverse of Max-Heapify: Increase the priority value for A[i] and bubble up to till max-heap property is restored. Θ(lg n) time.
procedure Heap-Increase-Key(A,i,key)
∗∗ Precondition: key ≥ A[i]
A[i] ← key
while (i > 1 and A[P arent(i)] < A[i]) do exchange A[i]↔A[Parent(i)] i ← P arent(i) 􏰀 Insert(A, new key) — Add a new key with lowest priority, increase its priority to new key. Θ(lg n) time. procedure Heap-Insert(A,key) heapsize[A] ← heapsize[A] + 1 A[heapsize[A]] ← −∞ ∗∗ or any value smaller than all keys in A Heap-Increase-key (A,heapsize[A],key) Topic 5: Heaps Starting with a heap: 214 310 "! "! 48576973 "! "! "! "! Topic 5: Heaps Max-heap-Insert (A, 15): 214 310 "! "! 48576973 "! "! "! "! 8 2 9 4 10 -∞ "!"!&% Topic 5: Heaps Heap-Increase-Key (A, heapsize[A], 15) is called: # 214 310 "! "! 48576973 "! "! "! "! 8 2 9 4 10 15 "!"!"! Topic 5: Heaps Bubbling up key 15: 214 310 "! "! 4 8 5 15 6 9 7 3 "! "! "! "! 8 2 9 4 10 7 "!"!"! Topic 5: Heaps Bubbling up key 15: 215 310 "! "! 4 8 5 14 6 9 7 3 "! "! "! "! 8 2 9 4 10 7 "!"!"! Topic 5: Heaps Priority Queue: 􏰀 Initialize(A) — Build-Max-Heap. Takes Θ(n) time. 􏰀 Maximum(A) — Return A[1]. Takes Θ(1) time. 􏰀 Extract-Maximum(A) — Like deleting from an array: put A[n] as the new first element before returning the max. The difference: we Max-Heapify(A, 1) to make this array into a heap. Θ(lg n) time. 􏰀 Increase-Key(A, i, new key) — The inverse of Max-Heapify: Increase the priority value for A[i] and bubble up to till max-heap property is restored. Θ(lg n) time. 􏰀 Insert(A, new key) — Add a new key with lowest priority, increase its priority to new key. Θ(lg n) time. 􏰀 Note that we didn’t mention Decrease-key(A, i, new key). Why? 􏰀 Because we already know how to deal with it. Once i’s key is set to a new smaller value, then the subheap rooted at i becomes an almost-heap. Run Max-Heapify(A, i). Topic 5: Heaps Sorting on the Fly 􏰀 So far — we have considered the notion of a static problem: someone gives you an array of n items and we have to sort them. 􏰀 However, the problem can be studied also in the dynamic setting: the set of items changes, keys are added and removed (inserted and deleted), and every now and then, we wish to sort them (or find a value x among them). 􏰀 Option 1: use a data-structure that does insertion and deletion fast (array, list, hash-table), and upon a sorting request - run a sorting algorithm. 􏰀 Option 2: use a data-structure that keeps the elements sorted. (a binary search tree) 􏰀 Which is the better option: depends on the sequence of calls. If a find()/sort() request comes once in a long while, after many insertion/deletions, then use option 1. If there are many find()/sort() requests, or the they appear after the insertion/deletion of only a few elements — use option 2. Topic 5: Heaps 程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts