程序代写 COMP250) - PowCoder代写

Algorithms & Data Structures (Winter 2022) Heaps

• Introduction. • Operations. • Application.

Introduction – 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.

Introduction – Heap – example
Max-heap as a binary tree.
18 17 19 13
14 11 Last row filled from left to right.

Introduction – Heap as arrays – example
Max-heap as an
array. 1 2 3 4 5 6 7 8 9 10
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̂]
7 17 19 13

Introduction – Heap – 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 = O(lg n).
• Most Basic operations on a heap run in O(lg n) time • Shape of a heap

Introduction – Heap – Height
Taken from Langer2014

• Introduction. • Operations. • Application.

Operations – Maintaining the heap property
• Suppose two sub-trees are max-heaps, but the root violates the max-heap property.
• Fix the offending node by exchanging the value at the node with the larger of the values at its children.
• The resulting tree may have a sub-tree that is not a heap.
• Recursively fix the children until all of them satisfy
the max-heap property.

MaxHeapify – Example
24 17 19 13
MaxHeapify(A, 2)
Note: The call assumes that the left and right sub-trees of the node i are max-heaps, but that the node i might be smaller than its children (violating the max-heap property)

MaxHeapify – Example
14 17 19 13
456 8 9 10
Note: The call assumes that the left and right sub-trees of the node i are max-heaps, but that the node i might be smaller than its children (violating the max-heap property)
MaxHeapify(A, 2)

MaxHeapify – Example
14 17 19 13
MaxHeapify(A, 2)
MaxHeapify(A, 4) 12

MaxHeapify – Example
14 17 19 13
MaxHeapify(A, 2)
MaxHeapify(A, 4) 13

MaxHeapify – Example
18 17 19 13
MaxHeapify(A, 2)
MaxHeapify(A, 4)
MaxHeapify(A, 9) 14

MaxHeapify – Example
18 17 19 13
MaxHeapify(A, 2)
MaxHeapify(A, 4)
MaxHeapify(A, 9) 15

MaxHeapify – Procedure
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()
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 O(1)
Time to fix the
subtree rooted at
one of i’s children is 16
O(size of subtree)

MaxHeapify – worst case
MaxHeapify(A, i)
• 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) + O(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(lgn)
Alternately, MaxHeapify takes O(h) where h is the height
of the node where MaxHeapify is applied

Introduction – Heap – Height
Taken from Langer2014

MaxHeapify – supplemental material
Taken from Langer2014
(“!”##$)#$ =”!”##” =2& −1 “”
# of nodes in the left subtree

MaxHeapify – supplemental material
Taken from Langer2014
“!”# = 2& ”
# of nodes in an added last row that is exactly half full.

MaxHeapify – worst case
Note: Valid iff h ≥ 1
Totalinheap(n):𝑛=2 2! −1 + 2! +1=3)2! −1
Total left subtree 𝑛
( ) ( ) 21(
≤ 2!&’ − 1 = ( ) 2 ) (2!− ‘) = ) ) (3 ) 2! − () ≤ ) ) 𝑛

MaxHeapify – worst case

Operations – 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̈n/2û downto 1 3. do MaxHeapify(A, i)

Building a heap – Example
Input Array:
Starting tree (not max-heap)

Building a heap – Example
MaxHeapify(ë10/2û = 5)

Building a heap – Example
MaxHeapify(ë10/2û = 5) MaxHeapify(4)

Building a heap – Example
MaxHeapify(ë10/2û = 5) MaxHeapify(4)
MaxHeapify(3)

Building a heap – Example
34 36 29 3203
MaxHeapify(ë10/2û = 5) 28 27 MaxHeapify(4)
MaxHeapify(3)

Building a heap – Example
34 36 29 3203
MaxHeapify(ë10/2û = 5) 28 27 MaxHeapify(4)
MaxHeapify(3) MaxHeapify(2)30

Building a heap – Example
34 21 29 3203
MaxHeapify(ë10/2û = 5) 28 27 MaxHeapify(4)
MaxHeapify(3) MaxHeapify(2)31

Building a heap – Example
34 27 29 3203
MaxHeapify(ë10/2û = 5) 28 21 MaxHeapify(4)
MaxHeapify(3) MaxHeapify(2)32

Building a heap – Example
34 27 29 3203
MaxHeapify(ë10/2û = 5)
MaxHeapify(4) MaxHeapify(3)
MaxHeapify(2)33 MaxHeapify(1)

Building a heap – Example
34 27 29 3203
MaxHeapify(ë10/2û = 5)
MaxHeapify(4) MaxHeapify(3)
MaxHeapify(2)34 MaxHeapify(1)

Building a heap – Example
24 27 29 3203
MaxHeapify(ë10/2û = 5)
MaxHeapify(4) MaxHeapify(3)
MaxHeapify(2)35 MaxHeapify(1)

Building a heap – Example
28 27 29 3203
MaxHeapify(ë10/2û = 5)
MaxHeapify(4) MaxHeapify(3)
MaxHeapify(2)36 MaxHeapify(1)

Building a heap – Correctness
• Loop Invariant property (LI): At the start of each iteration of 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.
• Termination:
• bounded number of calls to MaxHeapify
• At termination, i =0. Then, each node 1,2,…,n is the root of a max-heap. In
particular, node 1 is.

Building a heap – Running Time
• Loose upper bound:
• Cost of a MaxHeapify call ́ # calls to MaxHeapify
• O(lgn) ́O(n)=O(nlgn)
• Tighter bound:
• Cost of MaxHeapify is O(h).
• # of nodes with height h ≤ én/2h+1ù • Height of heap is !”lgn#$
Taken from Langer2014

Building a heap – Running Time
• Tighter bound:
• Cost of MaxHeapify is O(h).
• #nodes with height h ≤ én/2h+1ù • Heightofheapis!”lgn#$
&2! = 1−1⁄2 % =2 !”#
“%lgn$&! n # ( “%lgn$& h + ∑”2h+1$O(h)=O*n∑2h -=O(n)
h=0 ) h=0 ,
Running time of BuildMaxHeap is O(n)

• Introduction. • Operations. • Application.

Application – 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)

Application – 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)
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

Heapsort – Example
• 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)

• Introduction. • Operations. • Application.

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts