Concept explainers
(a)
To show the difference between the output of the array when it is passed as an array for BUILD-MAX-HEAP and BUILD-MAX-HEAP'.
(a)
Explanation of Solution
Given Information: A heap that has n-elements.
Explanation:
Pseudo code for BUILD-MAX-HEAP is given below:
| BUILD-MAX-HEAP( A ) |
| A.heapsize = A.length |
| for i = A.length/2 downto 1 |
| MAX-HEAPIFY( A,i ) |
Consider an array A= {1, 2, 3, 4, 5, 6}. If the above
The for-loop will iterate from 3 to 1.
At i=3 , MAX-HEAPIFY will be called with arguments as array A and i=3 . The following pseudo code for MAX-HEAPIFY is as follows:
| MAX-HEAPIFY( A,i ) |
| l = LEFT( i ) |
| r = RIGHT( i ) |
| ifl <= A.heapsize and A[l]> A[i] |
| largest = l |
| Else |
| largest = i |
| ifr <= A.heapsize and A[r]> A[largest] |
| largest=r |
| iflargest != i |
| exchange A [ i ] with A [ largest ] |
| MAX-HEAPIFY( A,largest ) |
Currently at i=3 , A [3]=3 and have the following tree:
At the end of the iteration:
At i=2 , A [2]=2 and after executing the algorithm, the following tree is evolved:
At i=1 , A [1]=1 and after executing the algorithm, the following tree is evolved:
Resultant array after BUILD-MAX-HEAP is A= {6, 5, 3, 4, 2, 1}
However, according to the question, the algorithm for BUILD-MAX-HEAP ', there is an alteration in A.heapsize, which is by default 1. Moreover, the value of i starts from 2 and goes on till A.length that is 6.
At i=2 , A [2]=2. The tree is given below-
Look at the algorithm of BUILD-MAX-HEAP' . It is using MAX-HEAP-INSERT. So, it becomes-
At i=3 , A [3]=3 and after using MAX-HEAP-INSERT
At i=4 , A [4]=4 and after using MAX-HEAP-INSERT
At i=5 , A [5]=5 and after using MAX-HEAP-INSERT
Finally at i=6,A [6]=6 and after using MAX-HEAP-INSERT
Resultant array after BUILD-MAX-HEAP' is A= {6, 4, 5, 1, 3, 2}
Hence, the resultant array after BUILD-MAX-HEAP and BUILD-MAX-HEAP' is not the same.
(b)
To determine the worst case scenario for BUILD-MAX-HEAP' while entering n-elements.
(b)
Explanation of Solution
The BUILD-MAX-HEAP' has MAX-HEAP-INSERT in it, which has worst case of Θ(log n). The call to this function is done for n-1 times, since it is not considering the parent node here.
The worst case for MAX-HEAP-INSERT happens when an array is sorted in ascending order.
Each insert step takes maximum Θ(log n ) steps, and since it is done for n times, it takes a worst case of Θ(nlog n ). Each iteration in the new block is actually taking more time as the older version as it has more iteration in it. The new block will work in even work in even worse case as it has the usage of other algorithm as well.
Want to see more full solutions like this?
Chapter 6 Solutions
Introduction to Algorithms
- (where a letter means insert and an asterisk means remove the maximum). Suppose these operation are performed on an initially empty max-oriented heap (max-heap). Draw the sequence of heaps that results from these operations. 1. P 2. R |-> R 3. R 4. R |-> P I O I 6. R |-> R 7. P |-> P I. 8. |-> 5.arrow_forwardConstruct a max heap using the BUILD-MAX-HEAP procedure from the input array H = {1, 3, 5, 7, 15, 11, 13, 9). After building the max heap, answer the following questions. Numeric answers must be encoded as Arabic numbers. For example, if the answer is 5 you should encode the number 5 (not the word "five"). If the answer is none, write none. 1. What is the root node of the resulting max heap? 2. What is the left child of node 7? 3. What is the right child of node 9? 4. What is the left child of node 13? 5. What is the parent of node 1?arrow_forward**In JAVA please** Construct a Binary HEAP for 5000 random ints numbers which are between 0 and 50000. These numbers need to be generated by a random function. Construct Binary HEAP by inserting(using Insert()) the input elements one at a time, into an initially empty binary heap using insert operation. (This should be a different method from the "linear-time algorithm" to build a heap)arrow_forward
- 4. Given an array, arr[] = {90, 15, 10, 7, 12, 2), does this array represents a Max-Heap? if it does, draw this max-heap.arrow_forwardA min-heap is useful when we are interested in the minimum value of aset of numbers. Now, instead of the min, we are interested in the K-th smallest value. a.) Please design a data structure to allow the following two operations: push (insert a newnumber) and find_Kmin (return the value of the K-th smallest number without removing it). Bothoperations should be done in O(log K) time. b.) In addition to push and find_Kmin, now we also want to support the pop operation toreturn and remove the K-th smallest element. Please design a data structure to support these threeoperations, and each operation should take O(log n) time with n being the size of the current set.arrow_forwardPart A - Heapsort We have included code in Java for a Binary Heap implementation.The first task is to use the heap to sort three separate arrays. The sorted arrays do not have to be ”in place” Use the implementation of the Binary Heap to:(a) Sort a list of floats from high to low.(b) Sort a list of strings alphabetically.(c) Sort integers by their second digit only (low to high). Here is the rest of code: import java.util.ArrayList; public class TestHeap { public static void main(String[] args) { ArrayList<Integer> list = new ArrayList<Integer>(); list.add(8); list.add(5); list.add(12); list.add(12); list.add(15); list.add(20); list.add(8); list.add(5); list.add(18); list.add(5); BinaryHeap<Integer> heap = new BinaryHeap<Integer>(new MaxIntegerComparorator()); heap.buildHeap(list); heap.display(); } } import…arrow_forward
- Problem 11: Max heap Build the Max heap with the values: 10, 47, 40, 100, 52, 72. Show the heap after each insertion.arrow_forwardpython This question is on heapsort. (a) We aim to construct a max heap based on an array A. When we call heapify(A,i) for i > size(A)/2, what will happen? (b) Assuming the elements in the array A are in a decreasing order, what is the running time of heapsort on A (using a max heap when constructing the heap)?arrow_forwardA) Draw the binary min heap that results from inserting 3, 4, 7, 8, 2, 6, 9, 5,1 in that order into an initially empty binary min heap. B) Draw the result of one deletemin call on your heap drawn in (A).arrow_forward
- Question 1.arrow_forward4. Draw a new heap that is created by inserting 52 into the following heap: 100 71 67 68 50 44 51 60 49 25 30arrow_forwardAssume that you are implementing a heap using a fixed size array. 1- Illustrate how the following heap would be constructed (show the content of the array, show in detail only what happens when nodes DOB and 17 are added): The nodes are inserted in the following order (key, value): (9, -4), (3, -6), (11, -4), (13, -7), (14, -2), (12, -8), (33-5), (17, -7), (6,-3). 2- Illustrate what happens to the heap when invoking remove (show the details). 3- Assume that you have an array of integers, write a code that would allow you to sort the array in ascending order (smallest to largest), using only a heap.arrow_forward
Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill Education
Starting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSON
Digital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSON
Database Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage Learning
Programmable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education