程序代写代做代考 data structure algorithm Pop Quiz

Pop Quiz
2. Show that an n-element heap has height (lg n)
• Since the height of an n-element heap must satisfy that 2h £ n £ 2h+1-1 < 2h+1. • Wehave h£lgn A[i] 4 largest = l
5 else largest = i
6 if r ≤ A.heap-size and A[r] > A[largest]
Assumption:
Left(i) and Right(i) are max-heaps.
7
8
9 10
largest = r
if largest 1 i
exchange A[i] « A[largest] Max-Heapify(A, largest)
T (n) £ T ( 2n ) + Q(1) Þ T (n) = O(lg n) 3
Alternatively O(h) (h: height)
L6.5

Max-Heapify(A,2) heap-size[A] = 10
Max-Heapify(A,2)
-> Max-Heapify(A,4)
-> Max-Heapify(A,9)
L6.6

16
4 10
14 7 9 3 281
A=
16
4
10
14
7
9
3
2
8
1
L6.7

16
4 10
14 7 9 3 281
A=
16
4
10
14
7
9
3
2
8
1
L6.8

16
4 10
14 7 9 3 281
A=
16
4
10
14
7
9
3
2
8
1
L6.9

16
14 4793
281
A=
10
16
14
10
4
7
9
3
2
8
1
L6.10

16
14 4793
281
A=
10
16
14
10
4
7
9
3
2
8
1
L6.11

16
14 4793
281
A=
10
16
14
10
4
7
9
3
2
8
1
L6.12

16
14 8793
241
A=
10
16
14
10
8
7
9
3
2
4
1
L6.13

16
14 8793
241
A=
10
16
14
10
8
7
9
3
2
4
1
L6.14

16
14 8793
241
A=
10
16
14
10
8
7
9
3
2
4
1
L6.15

Running Time for Max-Heapify
Max-Heapify(A,i)
1 2 3 4 5 6 7 8 9
l = Left(i)
r = Right(i)
if l ≤ A.heap-size and A[l] > A[i]
largest = l else largest = i
if r ≤ A.heap-size and A[r] > A[largest] largest = r
if largest 1 i
exchange A[i] « A[largest]
10 Max-Heapify(A, largest)
Time to fix node i and its children = Q(1)
PLUS
Time to fix the subtree rooted at one of i’s children = T(size of subree at largest)
L6.16

Max-Heapify
-To make node i max heap
Max-Heapify(A,1)
1
23 4567
8 9 10 11 12 13 14 15
A=
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
L6.17

Max-Heapify(A,1)
1
Largest =3
23 4567
8 9 10 11 12 13 14 15
A=
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
L6.18

Max-Heapify(A,largest) = Max-Heapify(A,3)
3 21 4567
8 9 10 11 12 13 14 15
A=
3
2
1
4
5
6
7
8
9
10
11
12
13
14
15
L6.19

Max-Heapify(A,3)
3 21 4567
Largest =7
8 9 10 11 12 13 14 15
A=
3
2
1
4
5
6
7
8
9
10
11
12
13
14
15
L6.20

Max-Heapify(A,7)
3 27 4561
Largest =7
8 9 10 11 12 13 14 15
A=
3
2
7
4
5
6
1
8
9
10
11
12
13
14
15
L6.21

Max-Heapify(A,7)
3 27 4561
Largest =15 8 9 10 11 12 13 14 15
3
2
7
4
5
6
1
8
9
10
11
12
13
14
15
A=
L6.22

Max-Heapify(A,15)
3 27
4 5 6 15
8 9 10 11 12 13 14 1
A=
3
2
7
4
5
6
15
8
9
10
11
12
13
14
1
L6.23

Running Time for Max-Heapify(A, n)
• Fixing up relationships between i, l, and r takes Q(1)
time
• T(n) = T(largest) + Q(1)
• If the heap at i has n elements, how many elements can the subtrees at l or r have?
§ Draw it
• Answer: 2n/3 (worst case: bottom row 1/2 full)
• largest £ 2n/3 (worst case occurs when the last row of tree is exactly half full)
• So time taken by Max-Heapify() is given by T(n) £ T(2n/3) + Q(1)
L6.25

Why T(2n/3) ?
• The worst case: bottom row 1/2 full
• Number of nodes at –
• level 0 i.e. root is 20
• level 1 is 21
• level 2 is 22
• …
• level h is 2h
• Summation of all nodes from level 0 up to level h,
• S = 20 + 21 + 22 + … + 2h
• From geometric series summation rule we know that
• x0 + x1 + x2 + … + xn = (x n+1 – 1)/(x-1)
• Substituting x = 2, we get
• S = 2h+1 – 1. i.e. 2h+1 = S + 1
• As 2h+1 is the total nodes at level h+1, which means that the total number of leaf nodes (2h+1 ) is one node more than the total number of non-leaf nodes (S).
L6.26

Why T(2n/3) ?
Now let’s calculate the number of nodes in left subtree, right subtree and total ..
• Assume that number of non-leaf nodes in the left subtree of root = k.
• By the above reasoning, number of leaf nodes in the left subtree of root = k + 1. Number of non-leaf nodes in the right subtree of root = k as the tree is said to be exactly half full.
• Total number of nodes in the left subtree of root = k + k + 1 = 2k +1
• Total number of nodes in the tree, n = (2k + 1) + k + 1(root) = 3k + 2.
• Ratio of nodes in the left subtree and total nodes = (2k + 1) / (3k + 2) which is bounded above by 2/3.
• That’s the reason of saying that the children’s subtrees each have size at most 2n/3.
L6.27

Analyzing Heapify(): Formal
• So we have
T(n) £ T(2n/3) + Q(1)
• By case 2 of the Master Theorem, T(n) = O(lg n)
• Thus, Max-Heapify() takes logarithmic time
L6.28

6.3 Building a heap
• Use Max-Heapify to convert an array A into a max-heap.
• How?
• Call Max-Heapify on each element in a bottom-up manner.
Build-Max-Heap(A)
1. A.heap-size = A.length
2. for i = ëA.length / 2û downto 1 3. do Max-Heapify(A, i)
Why ëA.length / 2û ?
— the total number of nodes at leaf level is roughly the same as the total number of nodes without leaf level.
L6.29

Build-Max-Heap(A) heap-size[A] = 10
i=5 Max-Heapify(A, i)
i=4 Max-Heapify(A, i)
L6.30

i=3 i=2 Max-Heapify(A, i) Max-Heapify(A, i)
L6.31

i=1 Max-Heapify(A, i)
L6.32

Build-Max-Heap – Example Input Array:
24
21
23
22
36
29
30
34
28
27
Initial Heap: (not max-heap)
24
21
22 36 29 30
34
23
28 27
L6.33

Build-Max-Heap – Example
MaxHeapify(ë10/2û = 5) MaxHeapify(4) MaxHeapify(3) MaxHeapify(2) MaxHeapify(1)
23282424 2324
232464
32324641
2321617
3203
29
3203
248 271
L6.34

Running Time of Build-Max-Heap
• Loose upper bound:
§ Cost of a Max-Heapify call ́ No. of calls to Max-Heapify § O(lg n) ́ O(n) = O(nlg n)
• Tighter bound:
§ Cost of a call to Max-Heapify at a node depends on the
height, h, of the node – O(h).
§ Height of most nodes smaller than n.
§ Height of nodes h ranges from 0 to ëlg nû.
§ A heap of size, n, has at most no. of nodes with height h ? (6.3-3)
§is én/2h+1ù Why?
§ Answer will be posted on Canvas.
L6.35

lem 1
6.3-3
A heap of size n has at most dn/2h+1e nodes with height h. Key Observation: For
any n > 0, the number of leaves of nearly complete binary tree is dn/2e. Proof by
induction Base case: Show that it’s true for h = 0. This is the direct result from
above observation. Inductive step: Suppose it’s true for h 1. Let Nh be the
number of nodes at height h in the n-node tree T . Consider the tree T0 formed by
removingtheleavesofT. Ithasn0 =ndn/2e=bn/2cnodes. Notethatthe
nodesatheighthinTwouldbeatheighth1intreeT0. LetN0 denotethe h1
numberofnodesatheighth1inT0,wehaveNh =N0 . Byinduction,wehave h1
Nh =N0 =dn0/2he=dbn/2c/2hed(n/2)/2he=dn/2h+1e. h1
Remark: Initially, I give following proof, which is flawed. The mistake is made in the
b
claim “The remaining nodes have height strictly more than h. To connect all subtrees

Running Time of Build-Max-Heap Tighter Bound for T(Build-Max-Heap)
T(Build-Max-Heap)
ëlgnû h å2h
h=0
£å¥h (!å¥kxk=x)
(1-x)2
= 1 / 2 , x = 1 / 2 in (A.8)
h=0 2h
k=0
(1-1/2)2 =2
ëlgnûé n ù åê2h+1 ú O(h)
h=0
ëlgnû
æåhö =Oçn 2h ÷
èh=0 ø
æëlgnûhö æ¥ hö Oçnå2h ÷=Oçnå2h ÷
èh=0 ø èh=0 ø = O(n)
Can build a heap from an unordered array in linear time
L6.37

6.4 Heapsort algorithm
• Sort by maintaining the as yet unsorted elements as a max-heap.
• Start by building a max-heap on all elements in A. § Maximum element is in the root, A[1].
• Move the maximum element to its correct final position.
§ Exchange A[1] with A[n].
• Discard A[n] – it is now sorted.
§ Decrement heap-size[A].
• Restore the max-heap property on A[1..n–1].
§ Call Max-Heapify(A, 1).
• Repeat until heap-size[A] is reduced to 2.
L6.38

Heapsort algorithm
Heapsort(A)
• Tosortanarrayinplace.
Heapsort(A)
1 Build-Max-Heap(A)
2 for i = A.length down to 2
3
4 5
exchange A[1]«A[i] A.heap-size = A.heap-size -1 Max-Heapify(A,1)
Heapsort Visualization 1
Heap Sort Dancing 2 Heapsort Visualization 3
Heapsort Visualization 4
L6.39

Heapsort(A)
{
} }
Heapsort
Build-Max-Heap(A);
for (i = length(A) downto 2)
{
Swap(A[1], A[i]);
heap_size(A) -= 1;
Max-Heapify(A, 1);
L6.40

Operation of Heapsort
L6.41

Analysis: O(n lg n)
L6.42

Algorithm Analysis
Heapsort(A)
1 Build-Max-Heap(A)
2 for i = A.length down to 2
3
4 5
exchange A[1]«A[i] A.heap-size = A.heap-size -1 Max-Heapify(A,1)
• In-place: no need additional space for sorting.
• Not Stable: do not maintain the relative location/order
of records with equal keys.
• Build-Max-Heap takes O(n) and each of the n-1 calls
to Max-Heapify takes time O(lg n). • Therefore, T(n) = O(n lg n)
L6.44

Heap Procedures for Sorting
• Max-Heapify
• Build-Max-Heap • HeapSort
O(lg n) O(n)
O(n lg n)
L6.45

Analyzing Heapsort
• The call to Build-Max-Heap() takes O(n) time
• Each of the n – 1 calls to Max-heapify() takes
O(lg n) time
• Thus the total time taken by HeapSort()
= O(n) + (n – 1) O(lg n) = O(n) + O(n lg n)
= O(n lg n)
L6.46

6.5 Priority Queues
• Popular & important application of heaps.
• Max and min priority queues.
• Maintains a dynamic set S of elements.
• Each set element has a key – an associated value.
• Goal is to support insertion and extraction efficiently. • Applications:
§ Ready list of processes in operating systems by their priorities – the list is highly dynamic
§ In event-driven simulators to maintain the list of events to be simulated in order of their time of occurrence.
L6.47

Priority Queues
• Heapsort is a nice algorithm, but in practice Quicksort (coming up) usually wins
• But the heap data structure is incredibly useful for implementing priority queues
§ A data structure for maintaining a set S of elements, each with an associated value or key
§ Supports the operations Insert(), Maximum(), and ExtractMax()
§ What might a priority queue be useful for?
L6.48

Priority Queues
• A max-priority queue support the following operations:
Insert(S, x) O(lg n) inserts the element x into the set S.
Maximum(S) O(1) returns the element of S with the largest key.
Extract-Max(S) O(lg n)
removes and returns the element of S with the largest
key.
Increase-Key(S,x,k) O(lg n)
increases the value of element x’s key to the new
value k, where k 3 x’s current key value
L6.49

Heap-Maximum
Heap-Maximum(A) 1 return A[1]
L6.50

Heap_Extract-Max
Heap_Extract-Max(A)
1 if A.heap-size < 1 2 error “heap underflow” 3 max = A[1] 4 A[1]= A[A.heap-size] 5 A.heap-size = A.heap-size - 1 6 Max-Heapify(A, 1) 7 return max Running time : Dominated by the running time of Max-Heapify = O(lg n) L6.51 Heap-Increase-Key Heap-Increase-Key (A, i, key) 1 ifkey 1 and A[Parent(i)] < A[i] 5 exchange A[i] « A[Parent(i)] 6 i = Parent(i) L6.52 Heap-Increase-Key(A,i,15) L6.53 Heap-Increase-Key(A, i, key) Heap-Increase-Key(A, i, key) 1 2 3 4 5 6 If key < A[i] error “new key is smaller than the current key” A[i] = key while i > 1 and A[Parent[i]] < A[i] exchange A[i] « A[Parent[i]] i = Parent[i] Heap-Insert(A, key) 1 A.heap-size = heap-size[A] + 1 2 A[A.heap-size] = –¥ 3 Heap-Increase-Key(A, A.heap-size, key) L6.54 Examples L6.55

Related Posts