(c) Evaluate this sum and then rewrite this as a function of n. You will probably have to [11 pts] look up an unfamiliar sum formula for this. Simplify this as much as possible - it will be very simple! Solution: 4. Suppose we have a perfect binary tree with height h 0 representing a heap, meaning it = has n 2+1 1 keys indexed from 1 to 2+1 1. When we run convertomaxheap we run maxheapify in reverse order on every key with children. Let's examine the worst-case - In the worst-case every single key gets swapped all the way to the leaf level. (a) For each level in the tree there are a certain number of nodes and each of those nodes [10 pts] requires a certain number of swaps. Fill in the appropriate values/expressions in the table: Level Number of Keys Number of Swaps per Key 0 2 .. (b) Write down a sum for the total number of swaps required. This should involve h, not n. [10 pts] Total
(c) Evaluate this sum and then rewrite this as a function of n. You will probably have to [11 pts] look up an unfamiliar sum formula for this. Simplify this as much as possible - it will be very simple! Solution: 4. Suppose we have a perfect binary tree with height h 0 representing a heap, meaning it = has n 2+1 1 keys indexed from 1 to 2+1 1. When we run convertomaxheap we run maxheapify in reverse order on every key with children. Let's examine the worst-case - In the worst-case every single key gets swapped all the way to the leaf level. (a) For each level in the tree there are a certain number of nodes and each of those nodes [10 pts] requires a certain number of swaps. Fill in the appropriate values/expressions in the table: Level Number of Keys Number of Swaps per Key 0 2 .. (b) Write down a sum for the total number of swaps required. This should involve h, not n. [10 pts] Total
C++ Programming: From Problem Analysis to Program Design
8th Edition
ISBN:9781337102087
Author:D. S. Malik
Publisher:D. S. Malik
Chapter18: Stacks And Queues
Section: Chapter Questions
Problem 15SA
Related questions
Question
![(c) Evaluate this sum and then rewrite this as a function of n. You will probably have to [11 pts]
look up an unfamiliar sum formula for this. Simplify this as much as possible - it will be
very simple!
Solution:](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fe0394dda-1230-46f2-92ff-9edb879436e7%2Ff3faf542-4746-4fa6-9ed0-c2ed6154aa33%2Fgboeuph_processed.png&w=3840&q=75)
Transcribed Image Text:(c) Evaluate this sum and then rewrite this as a function of n. You will probably have to [11 pts]
look up an unfamiliar sum formula for this. Simplify this as much as possible - it will be
very simple!
Solution:
![4. Suppose we have a perfect binary tree with height h 0 representing a heap, meaning it
=
has n 2+1 1 keys indexed from 1 to 2+1 1. When we run convertomaxheap we run
maxheapify in reverse order on every key with children.
Let's examine the worst-case - In the worst-case every single key gets swapped all the way to
the leaf level.
(a) For each level in the tree there are a certain number of nodes and each of those nodes [10 pts]
requires a certain number of swaps. Fill in the appropriate values/expressions in the
table:
Level
Number of Keys
Number of Swaps per Key
0
2
..
(b) Write down a sum for the total number of swaps required. This should involve h, not n.
[10 pts]
Total](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fe0394dda-1230-46f2-92ff-9edb879436e7%2Ff3faf542-4746-4fa6-9ed0-c2ed6154aa33%2Fwq5s3zq_processed.png&w=3840&q=75)
Transcribed Image Text:4. Suppose we have a perfect binary tree with height h 0 representing a heap, meaning it
=
has n 2+1 1 keys indexed from 1 to 2+1 1. When we run convertomaxheap we run
maxheapify in reverse order on every key with children.
Let's examine the worst-case - In the worst-case every single key gets swapped all the way to
the leaf level.
(a) For each level in the tree there are a certain number of nodes and each of those nodes [10 pts]
requires a certain number of swaps. Fill in the appropriate values/expressions in the
table:
Level
Number of Keys
Number of Swaps per Key
0
2
..
(b) Write down a sum for the total number of swaps required. This should involve h, not n.
[10 pts]
Total
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps with 3 images
Recommended textbooks for you
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning
Operations Research : Applications and Algorithms
Computer Science
ISBN:
9780534380588
Author:
Wayne L. Winston
Publisher:
Brooks Cole
New Perspectives on HTML5, CSS3, and JavaScript
Computer Science
ISBN:
9781305503922
Author:
Patrick M. Carey
Publisher:
Cengage Learning
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning
Operations Research : Applications and Algorithms
Computer Science
ISBN:
9780534380588
Author:
Wayne L. Winston
Publisher:
Brooks Cole
New Perspectives on HTML5, CSS3, and JavaScript
Computer Science
ISBN:
9781305503922
Author:
Patrick M. Carey
Publisher:
Cengage Learning
Programming Logic & Design Comprehensive
Computer Science
ISBN:
9781337669405
Author:
FARRELL
Publisher:
Cengage
Systems Architecture
Computer Science
ISBN:
9781305080195
Author:
Stephen D. Burd
Publisher:
Cengage Learning
Fundamentals of Information Systems
Computer Science
ISBN:
9781305082168
Author:
Ralph Stair, George Reynolds
Publisher:
Cengage Learning