Register

MIN HEAP

• recategorized by
695 views
0 votes
0 votes
The time complexity of the most efficient algorithm to determine whether an arbitrary array of size ‘n’, is min-heap or not?

(A) O(log n)

(B) O(n)

(C) O(n logn)

(D) O(1)
• recategorized by
User Avatar

1 Answer

2 votes
2 votes

Time complexity is O(n). We can visualize it using  traversal of Binary Tree.

We just check the root and its immediate descendent (not all the children) and return the result whether the root is smaller then its immediate children or not.

Similarly we proceed to the next levels and perform the same procedure. Check whether the root is smaller than immediate descendent or not. In this way we can check the entire tree in O(n) time. In this way we can say whether tree is mean - heap or not.

NOTE:- Dont check all the children for a root. It would increase the complexity to O(n^2)

User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
gmrishikumar asked Dec 1, 2018
2,311 views
Kth Largest element in Min-Heap
What is the time complexity to find the Kth largest element in a Min-Heap? Or equivalently, What is the time complexity to find Kth smallest element in Max-Heap?
What is the time complexity to find the Kth largest element in a Min-Heap? Or equivalently, What is the time complexity to find Kth smallest element in Max-Heap?
User Avatar
6 votes
6 votes
2 answers
2
Shivam Chauhan asked Oct 31, 2017
5,011 views
Min Heap
In a min-heap, the next largest element of a particular element can be found in ___ time. A) O(1) B) O(log n) C) O(n)
In a min-heap, the next largest element of a particular element can be found in ___ time.A) O(1)B) O(log n)C) O(n)
User Avatar
8 votes
8 votes
3 answers
3
Kapil asked Sep 4, 2016
3,983 views
7th smallest element in a Min-Heap
In a min-heap with n elements 1). The 7th smallest element can be found in time, if duplicates are allowed ? 2). The 7th distinct smallest element can be found in time, If duplicates are allowed ?
In a min-heap with n elements1). The 7th smallest element can be found in time, if duplicates are allowed ?2). The 7th distinct smallest element can be found in time, I...
User Avatar
11 votes
11 votes
5 answers
4
Vikrant Singh asked Dec 28, 2014
3,711 views
What is the complexity of finding 50th smallest element in an already constructed binary min-heap?
What is the complexity of finding $50^{th}$ smallest element in an already constructed binary min-heap? $\Theta(1)$ $\Theta (\log n)$ $\Theta (n)$ $\Theta (n \log n)$
What is the complexity of finding $50^{th}$ smallest element in an already constructed binary min-heap?$\Theta(1)$$\Theta (\log n)$$\Theta (n)$$\Theta (n \log n)$
User Avatar
Link Copied!