Book Image

Hands-On Data Structures and Algorithms with Python - Third Edition

By : Dr. Basant Agarwal
Book Image

Hands-On Data Structures and Algorithms with Python - Third Edition

By: Dr. Basant Agarwal

Overview of this book

Choosing the right data structure is pivotal to optimizing the performance and scalability of applications. This new edition of Hands-On Data Structures and Algorithms with Python will expand your understanding of key structures, including stacks, queues, and lists, and also show you how to apply priority queues and heaps in applications. You’ll learn how to analyze and compare Python algorithms, and understand which algorithms should be used for a problem based on running time and computational complexity. You will also become confident organizing your code in a manageable, consistent, and scalable way, which will boost your productivity as a Python developer. By the end of this Python book, you’ll be able to manipulate the most important data structures and algorithms to more efficiently store, organize, and access data in your applications.
Table of Contents (17 chapters)
14
Other Books You May Enjoy
15
Index

Chapter 7: Heaps and Priority Queues

Question 1

What will be the time complexity for deleting an arbitrary element from the min-heap?

Solution

To delete any element from the heap, we first have to search the element that is to be deleted, and then we delete the element.

Total time complexity = Time for searching the element + Deleting the element

= O(n) + O(log n)

= O(n)

Question 2

What will be the time complexity for finding the kth smallest element from the min-heap?

Solution

The kth element can be found out from the min-heap by performing delete operations k times. For each delete operation, the time complexity is O(logn). So, the total time complexity for finding out the kth smallest element will be O(klogn).

Question 3

What will be the time complexity to make a max-heap that combines two max-heap each of size n?

Solution

O(n).

Since the time complexity of creating a heap from n elements is O(n), creating a heap of 2n...