i) Give the fastest algorithm to find the two smallest distinct integer values in a MIN heap of n integers, in which values may be duplicated, and there are at least 2 distinct values. Clearly list the sequence of steps in the algorithm. You can only manipulate the heap using its insert and delete the methods (you do not have access to the internal heap array), and you can use additional storage structure to temporarily hold deleted items. The heap must still hold all n values when your algorithm is done. What is the worst case big 0 running time of your algorithm? Ignore the time it takes to allocate space for additional structures, if any. ii) A max heap has 128 items. The max item is deleted, and the heap order is restored. What would be the worst case number of comparisons made between the heap items in this process?

Actually, algorithm is an step by step process.

Answered: ) Give the fastest algorithm to find…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

100%

i) Give the fastest algorithm to find the two smallest distinct integer values in a MIN heap of n integers, in which values may be duplicated, and there are at least 2 distinct values. Clearly list the sequence of steps in the algorithm. You can only manipulate the heap using its insert and delete the methods (you do not have access to the internal heap array), and you can use additional storage structure to temporarily hold deleted items. The heap must still hold all n values when your algorithm is done.

What is the worst case big 0 running time of your algorithm? Ignore the time it takes to allocate space for additional structures, if any.

ii) A max heap has 128 items. The max item is deleted, and the heap order is restored. What would be the worst case number of comparisons made between the heap items in this process?

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

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