程序代写代做代考 data structure algorithm COMP251: Heaps & Heapsort

COMP251: Heaps & Heapsort
Jérôme Waldispühl School of Computer Science
McGill University
From (Cormen et al., 2002) Based on slides from D. Plaisted (UNC)

Heap data structure
• Tree-based data structure (here, binary tree, but we can also use k-ary trees)
• Max-Heap
– Largest element is stored at the root.
– for all nodes i, excluding the root, A[PARENT(i)] ≥ A[i].
• Min-Heap
– Smallest element is stored at the root.
– for all nodes i, excluding the root, excluding the root, A[PARENT(i)] ≤ A[i].
• Tree is filled top-down from left to right.

Heaps – Example
Max-heap as a binary tree.
26
24
18 17 19 13
20
12
14 11
Last row filled from left to right.

Heaps as arrays
26
24
20
18
17
19
13
12
14
11
array. 1 2 3 4 5 6 7 8 9 10
Max-heap as an
1
2 26 3 24 20
18
89
12
Map from array elements to tree nodes:
• Root : A[1]
• Left[i] : A[2i]
• Right[i] : A[2i+1]
• Parent[i] : A[ëi/2û]
456
7 17 19 13
10 14 11

Height
• Height of a node in a tree: the number of edges on the longest simple path down from the node to a leaf.
• Height of a heap = height of the root = Q(lg n).
• Most Basic operations on a heap run in O(lg n) time
• Shape of a heap

Sorting with Heaps
• Usemax-heapsforsorting.
• Thearrayrepresentationofmax-heapisnotsorted.
• Stepsinsorting
1. Convert the given array of size n to a max-heap (BuildMaxHeap)
2. Swap the first and last elements of the array.
• Now, the largest element is in the last position – where it belongs.
• That leaves n – 1 elements to be placed in their appropriate locations.
• However, the array of first n – 1 elements is no longer a max-heap.
• Float the element at the root down one of its subtrees so that the
array remains a max-heap (MaxHeapify)
• Repeat step 2 until the array is sorted.

Heapsort
• Combines the better attributes of merge sort and insertion sort.
– Like merge sort, worst-case running time is O(n lg n). – Like insertion sort, sorts in place.
• Introduces an algorithm design technique
– Create data structure (heap) to manage information
during the execution of an algorithm.
• The heap has other applications beside sorting.
– Priority Queues (recall COMP250)

Maintaining the heap property
• Supposetwosub-treesaremax-heaps, but the root violates the max-heap property.
• Fixtheoffendingnodebyexchangingthevalueatthe node with the larger of the values at its children.
– The resulting tree may have a sub-tree that is not a heap.
• Recursivelyfixthechildrenuntilallofthemsatisfythe max-heap property.

MaxHeapify – Example
1
26
23 14 20
Node n=2
456
7
24 17 19 13
8 9 10
12
18 11
MaxHeapify(A, 2)

MaxHeapify – Example
1
26
23 24 20
7
14 17 19 13
456
8 9 10
12
18 11
MaxHeapify(A, 2)

MaxHeapify – Example
1
26
23 24 20
7
14 17 19 13
456
8 9 10
12
18 11
MaxHeapify(A, 2) MaxHeapify(A, 4)

MaxHeapify – Example
1
26
23 24 20
7
14 17 19 13
456
8 9 10
12
18 11
MaxHeapify(A, 2) MaxHeapify(A, 4) MaxHeapify(A, 9)

Procedure MaxHeapify
Assumption: Left(i) and Right(i) are max-heaps. n is the size of the heap.
MaxHeapify(A, i)
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
l ¬ leftNode(i)
r ¬ rightNode(i)
n ¬ HeapSize(i)
if l £ n and A[l]>A[i]
then largest ¬ l
else largest ¬ i
if r £ n and A[r]>A[largest]
then largest ¬ r if largest ≠ i
then exchange A[i] « A[largest] MaxHeapify(A, largest)
Time to determine if there is a conflict and find the largest children is Q(1)
Time to fix the subtree rooted at one of i’s children is O(size of subtree)

Worst case running time of MaxHeapify(A, n)
• Size of a tree = number of nodes in this tree
• T(n): time used for an input of size n
• T(n) = T(size of the largest subtree) + Q(1)
• Size of the largest subtree £ 2n/3 (worst case occurs when the last row of tree is exactly half full)
Þ T(n) £ T(2n/3) + Q(1) Þ T(n) = O(lg n)
Alternately, MaxHeapify takes O(h) where h is the height of the node where MaxHeapify is applied

Height vs. Depth
https://stackoverflow.com/questions/29326512/what-is-the-difference-between-the-height-of-a-tree-and-depth-of-a-tree

Max # nodes / level 20
21 22
23
26
Maximum capacity of a heap
24
18 17 19 13
12 14 11 9 3 42 23 12
20
Maximum capacity of a binary tree of height h = 2h+1 – 1
Heap of height h+1 has at least (2h+1 – 1) + 1 nodes
⟹𝑛! ≥2! ⟹log”𝑛! ≥h⟹h=Ο(log𝑛)

Worst case running time of MaxHeapify
Note: Valid iff h ≥ 1
1
h-1 1
2h – 1 2*2h-1 =2h
2h – 1
Total in heap (n): 𝑛 = 3 % 2! − 1 (
Totalleftsubtree𝑛”#$% ≤2!&’−1=(%2%(2!−))=(%(3%2!−))≤(%𝑛
‘ )
( )

Worst case running time of MaxHeapify
Ο(log(n))
≥ 𝑛3
≤ 2⋅n 3

Building a heap
• Use MaxHeapify to convert an array A into a max-heap.
• Call MaxHeapify on each element in a bottom-up manner.
BuildMaxHeap(A)
1. n ¬ length[A]
2. for i ¬ ëlength[A]/2û downto 1 3. do MaxHeapify(A, i, n)

BuildMaxHeap – Example Input Array:
24
21
23
22
36
29
30
34
28
27
Starting tree (not max-heap)
24
21
22 36 29 30
23
34
28 27

BuildMaxHeap – Example 24
21
23
22 36 29 3203
MaxHeapify(ë10/2û = 5)
3224
28 27

BuildMaxHeap – Example 24
21
22 36 29 3203
MaxHeapify(ë10/2û = 5) 28 27 MaxHeapify(4)
23
2324

BuildMaxHeap – Example 24
21
28 36 29 3203
MaxHeapify(ë10/2û = 5) 22 27 MaxHeapify(4)
23
2324

BuildMaxHeap – Example 24
21
28 36 29 3203
23
2324
22 27
MaxHeapify(ë10/2û = 5) MaxHeapify(4) MaxHeapify(3)

BuildMaxHeap – Example 24
21
28 36 23 3203
29
2324
22 27
MaxHeapify(ë10/2û = 5) MaxHeapify(4) MaxHeapify(3)

BuildMaxHeap – Example 24
21
28 36 23 3203
29
2324
22 27
MaxHeapify(ë10/2û = 5) MaxHeapify(4) MaxHeapify(3) MaxHeapify(2)

BuildMaxHeap – Example 24
36
28 21 23 3203
29
2324
22 27
MaxHeapify(ë10/2û = 5) MaxHeapify(4) MaxHeapify(3) MaxHeapify(2)

BuildMaxHeap – Example 24
36
28 27 23 3203
29
2324
22 21
MaxHeapify(ë10/2û = 5) MaxHeapify(4) MaxHeapify(3) MaxHeapify(2)

BuildMaxHeap – Example 24
36
28 27 23 3203
29
3242
22 21
MaxHeapify(ë10/2û = 5) MaxHeapify(4) MaxHeapify(3) MaxHeapify(2) MaxHeapify(1)

BuildMaxHeap – Example 36
24
28 27 23 3203
29
3242
22 21
MaxHeapify(ë10/2û = 5) MaxHeapify(4) MaxHeapify(3) MaxHeapify(2) MaxHeapify(1)

BuildMaxHeap – Example 36
28
24 27 23 3203
29
3242
22 21
MaxHeapify(ë10/2û = 5) MaxHeapify(4) MaxHeapify(3) MaxHeapify(2) MaxHeapify(1)

Correctness of BuildMaxHeap
• LoopInvariantproperty(LI):Atthestartofeachiterationof
the for loop, each node i+1, i+2, …, n is the root of a max-heap. • Initialization:
– Before first iteration i = ën/2û
– Nodes ën/2û+1, ën/2û+2, …, n are leaves, thus max-heaps.
• Maintenance:
– By LI, subtrees at children of node i are max heaps.
– Hence, MaxHeapify(i) renders node i a max heap root (while preserving the max heap root property of higher-numbered nodes).
– Decrementing i reestablishes the loop invariant for the next iteration.
• Stop:boundednumberofcallstoMaxHeapify

Running Time of BuildMaxHeap
• Looseupperbound:
– Cost of a MaxHeapify call ́ # calls to MaxHeapify – O(lgn) ́O(n)=O(nlgn)
• Tighterbound:
– Cost of MaxHeapify is O(h).
– ≤én/2h+1ùnodeswithheighth. – Height of heap is !”lgn#$
“%lgn$&! n # ( “%lgn$& h +
$ h 1⁄2
(2! = 1−1⁄2 % =2 !”#
∑”2h+1$O(h)=O*n∑2h -=O(n) h=0 ) h=0 ,
Running time of BuildMaxHeap is O(n)

Heapsort
1. Builds a max-heap from the array.
2. Put the maximum element (i.e. the root) at the correct place in the array by swapping it with the element in the last position in the array.
3. “Discard” this last node (knowing that it is in its correct place) by decreasing the heap size, and call MAX-HEAPIFY on the new root.
4. Repeat this process (goto 2) until only one node remains.

Heapsort(A)
HeapSort(A)
1. Build-Max-Heap(A)
2. for i ¬ length[A] downto 2 3. do exchange A[1] « A[i] 4. MaxHeapify(A, 1, i-1)

Heapsort – Example
7
4
3
1
2
1
7 43
2

Heapsort – Example
2
4
3
1
7
4
2
3
1
7
Heapify
24 4323
11
7

Heapsort – Example
1
2
3
4
7
3
2
1
4
7
Heapify
13 2321
74

Heapsort – Example
1
2
3
4
7
2
1
3
4
7
Heapify
12 21
743

Heapsort – Example
1
2
3
4
7
1
2
3
4
7
1
7432

Heap Procedures for Sorting
• BuildMaxHeap O(n)
• for loop n-1 times (i.e. O(n))
– exchange elements O(1) – MaxHeapify O(lg n)
=> HeapSort O(n lg n)

Related Posts