looking over my test for data structures i noticed something when going over it, can someone please help and answer, what is the average time cost (big O) of a search for a max key in min heap (priority queue), would it be O(log N) or is it O(N)?
Asked
Active
Viewed 920 times
-1
-
Helpful page: http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o – hexparrot May 16 '13 at 22:59
1 Answers
1
Searching for the maximal element in a min heap is O(N).
You'd have to go to the lowest level in the tree (which is up to half the children) and check each of them since they are in no particular order in relation to each other.
That would require checking about N/2 nodes which (assuming you use the standard algorithm for finding a maximum) is O(N).
If you are interested in finding the maximal element in a heap you can use a max heap instead. If memory is not a big concern you can use both a max heap and a min heap which would allow you O(1) for getting both the maximal and minimal elements.
Benjamin Gruenbaum
- 270,886
- 87
- 504
- 504