Register

max heap with binary search

1,427 views

1 Answer

1 votes
1 votes

https://gateoverflow.in/1245/gate2007-47

you can refer above question and it is clear that comparison require  loglog n time.

but that does not mean you can insert element in loglog n time.

we have to shift the element and it require log n time in worst case  same as that of heap.

one more thing not related to heap but about binary search and insertion sort  

there also you find the position of element in sorted part of array in log n time but you can not improve the worst case time.

it will be O(n^2) only, cause you have to shift the element to its correct position.

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

Related questions

3 votes
3 votes
1 answer
1
Hardik Vagadia asked Sep 13, 2016
1,164 views
Binary Max Heap
In a binary max heap containing n numbers, the smallest element can be found in time?
In a binary max heap containing n numbers, the smallest element can be found in time?
User Avatar
0 votes
0 votes
3 answers
2
anurag_am asked Jun 18, 2015
914 views
why do we not apply Binary search for insertion in the heap ?
however number of comparisions in binary search=O(loglogn) and in linear search it is O(logn), time complexity in case of binary search- O(logn) and in case of linear it is also O(logn)
however number of comparisions in binary search=O(loglogn) and in linear search it is O(logn),time complexity in case of binary search- O(logn) and in case of linear it i...
User Avatar
2 votes
2 votes
3 answers
3
Sankaranarayanan P.N asked Jun 4, 2015
751 views
a binary search tree with n elements are constructed by randomly taking the elements one by one. What is the expected height of the tree
a binary search tree with n elements are constructed by randomly taking the elements one by one. What is the expected height of the tree
User Avatar
2 votes
2 votes
1 answer
4
Thor-o-s asked Sep 1, 2022
423 views
Algorithm which uses Max heap to find i smallest elements
Can anyone please explain how to find “ i “ smallest elements from an array whose elements are distinct Please use max heap to explain the working input : n distinct elements output : i smallest elements
Can anyone please explain how to find “ i “ smallest elements from an array whose elements are distinctPlease use max heap to explain the working input : n distinct e...
User Avatar
Link Copied!