(a) Consider a heap stored in an array a = = [25, 17, 23, 14, 8, 21, 12,7]. Write the updatedarray when we apply extractMax operation.(b) Consider the same heap a = [25, 17, 23, 14, 8, 21, 12, 7]. Write the updated array whenwe apply the operation insert (24).(c) Specify the best-case running time of extract Max() in a heap formed by n distinctitems. If your answer is (f(n)), you must provide an example, with large n, for whichextract Max() takes (f(n)).

Heap data structures play a significant role in computer science, especially in priority queues and…

Answered: (a) Consider a heap stored in an array…

Similar questions

You are given a Heap represented by an array A[1, ..., n].One of the values in the Heap needs to be changed to a different value.Say, the k’th element, 1 <= k <= n, is to be updated to a new value ‘X’.Write pseudocode to perform fixing the Heap when you update this value.Hint: Consider three cases, A[k] == X, A[k] > X, A[k] < X.
Show the result after a deleteMin on this binary heap. (Show each step). 3 10 15 8. 19 21 20 25 9 11
Suppose we have p max heaps, with q elements in each. We wish to combine these into a single heap. Each of the following sub-parts describes one approach merging the heaps, and you are asked to derive the big O running time. MUST show derivation We create a new, empty heap H. From each of the input heaps, P, until P is empty we repeatedly remove the highest priority element using the heap delete method, and insert it into H using the heap insert method. What is the worst-case big O running time? Show derivation. We create a new, empty linked list L. For each of the input heaps, P, we iterate over its internal array and insert each element at the front of L. We then transfer the elements of L into an array, and heapify the array using repeated sift downs. What is the worst-case running time? Show derivation. We divide the p input heaps into p/2 pairs, and apply the algorithm from part (b) on each pair, resulting in p/2 heaps. We then repeat this process until we are left with a…
2.a. Add a node with value 3 to the following min heap. Show the upheap swap process needed to restore the heap-order property. You will need at least three diagrams. Thanks to https://www.cs.cmu.edu/~adamchik/15-121/lectures/Binary%20Heaps/heaps.html You are welcome to use Microsoft Paint (type "mspaint" in the start menu search box) to create several diagrams. Alternatively, use pen and paper, or a whiteboard, and take a picture with your cell phone. 2.b. Remove the root node from the following heap. You will need to downheap swap to restore the heap-order property. Use diagrams to show the state of the heap at each step. You will need at least three diagrams. Thanks to http://www.studytonight.com/data-structures/heap-sort
Problem 4: Binomial heaps. Let H1 and H2 be two binomial heaps. We would like tomerge H1 and H2 to obtain the binomial heap H and also to find the minimum key in H.A standard approach would be to perform the following sequence of operationsH = Merge(H1, H2);m = Min(H).Alternatively, we may perform the following sequence of operationsm1 = Min(H1);m2 = Min(H2);m = min{m1, m2};H = Merge(H1, H2).(i) Give an example of heaps H1 and H2 in which the time complexity of all operations together in the standard approach is better than in the alternative approach.Note that the time complexity of finding the minimum element in the binomial heapdepends on the number of binomial trees in the heap. Justify your answer.(ii) Does there exist an example of heaps H1 and H2 in which the time complexity ofall operations together in the alternative approach is better than in the standardapproach. Again note that the time complexity of finding the minimum element inthe binomial heap depends on the number of…
The largest item in a heap must appear in position 1, and the second largest mustbe in position 2 or position 3. Give the list of positions in a heap of size 31 where thekth largest (i) can appear, and (ii) cannot appear, for k=2, 3, 4 (assuming the values tobe distinct).
please draw the graph after each operation
Problem 3. In this problem we focus on the BUILD-MAX-HEAP operation. 1. Illustrate the operation of BUILD-MAX-HEAP on the array A = [6,3,12,9,25,17,4,22,8,5]. 2. Prove that the running time of the BUILD-MAX-HEAP operation is O(n lg n). Note, this is not a tight bound.
use figure 6.5 to answer the question