Introduction to Algorithms
Introduction to Algorithms
3rd Edition
ISBN: 9780262033848
Author: Thomas H. Cormen, Ronald L. Rivest, Charles E. Leiserson, Clifford Stein
Publisher: MIT Press
bartleby

Concept explainers

Question
Book Icon
Chapter 6, Problem 1P

(a)

Program Plan Intro

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)

Expert Solution
Check Mark

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 algorithm is used, A.heapsize =6 and i =6/2=3.

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:

Introduction to Algorithms, Chapter 6, Problem 1P , additional homework tip  1

At the end of the iteration:

Introduction to Algorithms, Chapter 6, Problem 1P , additional homework tip  2

At i=2 , A [2]=2 and after executing the algorithm, the following tree is evolved:

Introduction to Algorithms, Chapter 6, Problem 1P , additional homework tip  3

At i=1 , A [1]=1 and after executing the algorithm, the following tree is evolved:

Introduction to Algorithms, Chapter 6, Problem 1P , additional homework tip  4

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-

Introduction to Algorithms, Chapter 6, Problem 1P , additional homework tip  5

Look at the algorithm of BUILD-MAX-HEAP' . It is using MAX-HEAP-INSERT. So, it becomes-

Introduction to Algorithms, Chapter 6, Problem 1P , additional homework tip  6

At i=3 , A [3]=3 and after using MAX-HEAP-INSERT

Introduction to Algorithms, Chapter 6, Problem 1P , additional homework tip  7

At i=4 , A [4]=4 and after using MAX-HEAP-INSERT

Introduction to Algorithms, Chapter 6, Problem 1P , additional homework tip  8

At i=5 , A [5]=5 and after using MAX-HEAP-INSERT

Introduction to Algorithms, Chapter 6, Problem 1P , additional homework tip  9

Finally at i=6,A [6]=6 and after using MAX-HEAP-INSERT

Introduction to Algorithms, Chapter 6, Problem 1P , additional homework tip  10

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)

Program Plan Intro

To determine the worst case scenario for BUILD-MAX-HEAP' while entering n-elements.

(b)

Expert Solution
Check Mark

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?

Subscribe now to access step-by-step solutions to millions of textbook problems written by subject matter experts!
Students have asked these similar questions
Construct a Binary Heap using the following sequence of numbers as input. It is up to you to decide to construct a Max heap or Min heap. 28 12 17 5 7 22 13 12 4 11 16 Do all of the following.  Write a Max_heapify or Min_heapify function, depending on your construction decision Write a Build_heap function using the given series of numbers. Write a Delete_root function to delete a root node from the heap. Write a print function to display the heap. (print all nodes which have the same level in one line)
Construct a dynamic max heap by inserting one integer at a time to the evolving max heap. Show all steps. Array: 7 30 33 10 44 38 3 1
We can build a heap by top-down (iterated insertion), or by bottom-up. Given the numbers 10, 9, 12, 13, 14, 8 a. run the bottom-up algorithm to create a heap and show the resulting heap and ALLsteps  b. run the top-down algorithm to create heap and show the resulting heap and ALLsteps
Knowledge Booster
Background pattern image
Computer Science
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
SEE MORE QUESTIONS
Recommended textbooks for you
Text book image
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Text book image
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Text book image
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
Text book image
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Text book image
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Text book image
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education