Topic 5: :
Heaps (CLRS Ch. 6.1-6.5) Max-Heapify
Build-Max-Heap Heapsort
Priority Queues
Copyright By PowCoder代写 加微信 powcoder
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 =nk=nk+k ≤nk+2k/2
Topic 5: Heaps
2k 2k2k2k2k2k k=1 k=1 k=4 k=1 k=4
3lg(n) ∞ =nk+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 21 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