CODEWITHSUNDEEP
algorithmtime-complexity
Sanjay Verma
Sanjay Verma

Reputation: 101

In a min-heap with n elements with the smallest element at the root,

In a min-heap with n elements with the smallest element at the root, the 7th smallest element can be found in time.

  1. Θ(nlogn)
  2. Θ(n)
  3. Θ(logn)
  4. Θ(1)

My understanding: Time to find the smallest element on a min-heap- one retrieve operation - Θ(1) Time to find the second smallest element on a min-heap- requires 22−1 = 3 check operations to find the second smallest element out of 3 elements — Θ(1).

Time to find the 7th smallest element - requires O(27−1) = O(127) check operations to find the seventh smallest element out of 127 possible ones — Θ(1).

In short if the number of required operations is independent of the input size n, then it is always Θ(1). (Here, we are doing a level order traversal of the heap and checking the elements).

Or I can look this way too: If we are not allowed to traverse the heap and allowed only default heap-operations, we will be restricted with doing Extract-min 7 times which would be O(n).

My doubt is about which way is correct what should be the answer.

Upvotes: 1

Views: 1580

Answers (2)

SomeDude
SomeDude

Reputation: 14238

Extracting min in a min heap takes log(n) time and because you are limiting to the 7th position ( a constant ) the time taken is still of the order of log(n).

If you are trying to find 7th smallest element, one way to do it is extract the top element 6 times from the heap and then read ( not extract ) the top of the heap. That is your 7th smallest element. Your running time is still of the order of log(n) because you are removing constant number of times from the heap. Now you may want to insert the 6 elements back into the heap. Each insert has worst time of log(n), this is still log(n) because 6 is constant.

Upvotes: 2

Matt Timmermans
Matt Timmermans

Reputation: 59233

A min-heap is a specific arrangement of nodes, which you can traverse to find the 7th-smallest element in O(1) time, because you must visit at most 127 nodes.

A priority queue is an abstract data type that provides an extract-min operation, but which is not necessarily implemented with a min-heap that you could traverse in this way.

Upvotes: 4

Related Questions