About

I am too Lazy to update about me.

Role

Alma Mater:

Not updated.

Experience:

Not updated.
Babytud
Answer
1 year 5 months ago

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. 

moreless
Babytud
Answer
1 year 5 months ago

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

moreless
Babytud
Answer
2 years 1 month ago
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.
moreless
Babytud
Answer
2 years 1 month ago

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. 

moreless

<div class="tex2jax">Oops....!! Find someone to follow. You are not following anyone yet.</div>

Rajeev
914
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.
more less

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. 

more less

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

more less

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. 

more less