Please explain a. Midterm Exam Thursday, 22 February 2018 ing heaps as a sorting
ID: 3740435 • Letter: P
Question
Please explain a.
Midterm Exam Thursday, 22 February 2018 ing heaps as a sorting approach, the algorithm BuILD-MAX-HEAP (shown) makes use of the procedure MAx-HEAPIFy to take an array and make it into a heap by imposing the heap BUILD-MAX-HEA (A) 1 A.heap-size A.length 3 Max-HEAPIFY(A, ) MAx-HEAPI(A, i) property on each interior node in turn. Since MAX-HEAPIFY runs in ?(lg n) time, and since it is called n times, BUILD-MAX-HEAP runs in ?(n lg n) time to make a heap out of an unsorted input wntol. Ignl array Once the heap is built, we considered using it as a data structure to keep dynamic data in order for easy retrieval. To 3ìf / SA.heap-size and A[f] > ?? 5 else largesr- i 6 ifrSA heap-size and A[r]>A[largest] that end, the algorithms HEAP-MAXIMUM, HEAP-EXTRACT-MAx, HEAP-INCREASE-KEY (shown) and MAx-HEAP-INSERT (shown) were introduced. In fact, at the cost of some additional storage | 7 largesrr 8 ?flargest 9 exchange Al/I with A[largest] 10 MAx-HEAPIFYA, largest) space, we could initially construct the heap by taking the input data array and inserting each element, one at a time, into a heap structure using Max-HEAP-INSERT. A proposed algorithm would be: MAx-HEAP-INSERT A, key) 1 A heap-size A.heap-size + I 2 AIA heap-size)-- 3 HEAr-INCREASE-KEY(A, A heap-size, key) BUILD-INSERT-MAX-HEAP (A) I heap-size[A]4-1 2 fori2 to length[4] 3 dlo MAX-HEAP-INSERT(A,A[i]) HEAP-INCREASE-KEY(A, i, key) 1 if key A 2 error "new key is smaller than current key 4 while i > 1 and A[PARENT(i)] A[i] 5 exchange Alf] with A[PARENT(i)] 6 PARENT) (10 points) Show that in the worst case, BUILD-INSERT-MAX-HEAP requires ?(n lg n) time to build an n-element heap a. b. (12 points) Do procedures BUILD-INSERT-Max-HEAP and BUILD-MAx-HEAP (shown) always create identical heap structures when given the same data? Either prove that they do, or give an example to show that they don't. (Hint: consider a concrete example, e.g.. use both algorithms on an input array such as - but recall that although one counterexample is sufficient to disprove something, a single positive example does not make a proof.) Total points: 100 End of exam . CS303 Algorithms and Data Structures 5 of 5Explanation / Answer
Heap sort is a special case of balanced binary tree data structure. There are two types of heap, parent node is greater than child node(MAX HEAP) and parent node smaller than child node (MIN HEAP). Heap should be always balanced. Each level in the heap should be full (complete) except the bottom one. So element is always first inserted at bottom level.
In best case if number to be inserted is smaller than the parent, heap property is not violated and element is inserted easily in O(1) time at bottom level. So best case time is O(1).
Worst case is the one when the number to be inserted is the larger than all the elements present in the heap. Ideally that element should be at the top. So its needed to be swapped. When an element is swapped upto the next level in heap, the number of nodes at that level is cut down to half roughly. So O(log n) swaps are required for an element at bottom to reach the top root node.
As can be seen in the given code, HEAP-INSERT-KEY is performing this swapping thing and deciding the right position of the new element in the MAX heap. So time required will be O(log n).
BUILD-INSERT-MAX-HEAP calls MAX-HEAP-INSERT which in turn calls HEAP-INSERT-KEY , for each element n, that is n times. So total time required will ne O( n log n)