Register

Min Heap & Probability

• recategorized by
591 views

1 Answer

Best answer
2 votes
2 votes

Considering h as height of tree, h =0 at root. Total no of elements are (2^(h+1)-1) means it is complete.Largest element wil be in leaf level of MIN HEAP.

At each level we have two choices (i.e paths to take equally likely) to reach bottom we have(2*2*2.....*2) h times,among all choices only one will lead to largest element. SO, probability to reach largest element while traversing tree is 1/2^h.

• selected by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
saurav raghaw asked Dec 22, 2018
686 views
MIN HEAP
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)
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)
User Avatar
1 votes
1 votes
1 answer
2
gmrishikumar asked Dec 1, 2018
2,297 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
4
Shivam Chauhan asked Oct 31, 2017
4,960 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
Link Copied!