can we apply binary search on the heap because heap doesn't contain sorted elements?

Consider the process of inserting an element into a max heap.If we perform a binary search on the path from new leaf to root to find the position of newly inserted element ,the number of comparisons performed are? 

16Comments
Ranita Biswas ranita 25 May 2015 02:05 pm

As far as I understand, you cannot do a binary search to find the position of the newly inserted element in a max-heap, because max-heap is not a binary search tree. Whenever inserting a new element in a max-heap, you insert it in the last leaf, and then heapify it to make it max-heap again. If you wanted to ask something else, please clarify.

Habib Mohammad Khan habibkhan 25 May 2015 03:53 pm

In binary heap tree there is no association between left child and right child so no concept of binary search....

 

Leen Sharma leensharma 26 May 2015 09:16 am

Max-heap is always balanced.
So, distance from leaf to root = log n
So, we need to search within (log n) elements.
Since all the elements in a path from root to a node is always sorted in a max-heap, we can perform binary search.
# of comparisons by binary search on X sorted elements = O(log X)

So, # of comparisons = O(log log n)
 

Parimal Andhalkar parimal_andhalkar 3 Nov 2015 11:14 pm

Max heap is balanced but it is not BST

in BST left child less than ROOT < Right child ..  this condtion cannot be apply to heap  

and if u apply binary search on  path from root to each leaf node .. then there will be n/2 elements in at leaf position .

therfore total time complexity becomes n/2 * log2n = nlogn  .... its worst than normal search = O(n)

 

lucky luckysunda 18 Nov 2015 05:49 am

But we are not applying binary search on each leaf node, we are applying on new leaf to root, in which only sorted elements will occur, and their number will be logn. So, time complexity should be o(loglogn)

Debajyoti Ghosh djg1981 15 Feb 2017 12:13 am

Binary Heap data structure is not well suit for searching as it require O(n) time in the worst case, along with the overhead of heap implementation. 

Rajeev gateaspirant 4 Jun 2016 05:17 pm

I did not get it sir, why heap data structure can't/should't be userd for searching?

Debajyoti Ghosh djg1981 29 May 2018 12:40 pm
Consider the question Given a min/max-heap of N elements, is it possible to find an element efficiently?
Problem with min/max heap is that they are not sorted in any order like BST. Searching in a path from leaf node to root is a partial searching problem, no guarantee that search element will belong to that path. One optimization is possible, though (assume a max heap here). If you have reached a node with a lower value than the element you are searching for, you don't need to search further from that node. However, even with this optimization, search is still O(loglogn).
Each path from leaf to root is sorted, but the subtrees are not
sorted relative to each other. Searching within the entire heap is not recommended, even BST is better than binary heap in this case. To search in heap first you have to insert elements in heap & build heap is O(n), then you need to search through every element in the heap in order to determine if an element is present or not, which is O(n).
Why do you want/interested to search in a heap? heap is meant for what? why don't you delete min in AVL trees? See the set of allowable operations in heap in wikipedia page. Similarly heap is usually not for find-element. A heap is a useful data structure when you need to remove the element with the highest (or lowest) priority, useful in several efficient graph algorithms like as Dijkstra's algorithm.
Ranita Biswas ranita 15 Feb 2017 02:01 pm

I am not exactly sure if it is a sarcasm here. Students are in learning phase, so they can always ask some doubt which is not that relevant. Doubts are called 'doubts' because the asker is not sure about the concept. A teacher's duty is to clarify it in a proper way, sarcasm does not solve problems.

In case of this very problem, it is a little misleading because it does not specify the internal structure of the heap. If the elements of the heap are stored in an array, we can always do a binary search among the elements in a particular path from leaf node to root. Even though heap itself does not support binary searching, but elements of a single path of a heap are always sorted and we can easily get parent and children of nodes from array indices, and so we can do binary search on those elements. The answer given by Leen Sharma (the asker herself) is correct which calculates the complexity as O(log log n).

PS: The comment on which I replied is below (as it was deleted by the user later and now my reply sounds kind of crazy).

Uddalak Bhaduri uddalakbhaduri 15 Feb 2017 12:39 pm

@ranita if a heap contains n elements, then at any single path from leaf node to root, the number of elements are logn. And since binary search takes O(logn) time so overall in a single path it would take O(loglogn) to search for an element. But this solution is not guaranteed as we can't just assume that our search element will always be in that single path only.

Debajyoti Ghosh djg1981 15 Feb 2017 12:10 pm

okay your answer, but is it not O(loglogn) ?

Ranita Biswas ranita 15 Feb 2017 01:10 pm

@uddalakbhaduri That's a genuine doubt. However, if you revise the concept of insertion in a max-heap (you can refer to this link: https://en.wikipedia.org/wiki/Binary_heap#Insert or any standard book), you will see that the 'newly inserted element' always can be found on the path from 'new leaf' to root. It happens because how we insert the new element using up-heap operations only. That's why the solution of O(log log n) works.

@djg1981 That was a typo, just corrected. Thanks.

Debajyoti Ghosh djg1981 15 Feb 2017 01:27 pm

U are exact Uddalok. 

Ranita Biswas ranita 15 Feb 2017 10:04 pm

Unfortunately, he is not. The point both of you are missing is that we are trying to find the position of the newly inserted element (not just any random search element). The position of the newly inserted element is always on the path from new leaf to root. Please go through the question again to understand what it is asking for.

Debajyoti Ghosh djg1981 15 Feb 2017 02:02 pm

We are addressing whether we can search within heap. In that sense Uddalok is right. Not addressing what happen with the newly inserted element as per the question posted. 

Ranita Biswas ranita 15 Feb 2017 02:07 pm

Then kindly create a separate thread for your discussion. As you are addressing 'your issue' on the comment thread of a posted question, it will confuse the students.