Menu
I'm learning about heaps right now and obviously more attention is given to the min element of the heap, however I'm just wondering how you would find the max element? For the min element you would just have to return the root, not sure how you would approach it for the max?
411
We can check all the nodes in the min-heap to get the maximum element. Note that this approach works on any binary tree and does not makes use of any property of the min-heap. It has a time and space complexity of O(n).
The correct answer is O(n). In each step you need traverse both left and right sub-trees in order to search for the minimum element. In effect, this means that you need to traverse all elements to find the minimum.
In a max-heap, the parent or root node is usually greater than the children nodes. The maximum element can be accessed in constant time since it is at index 1 . Based on the figure above, at every level, the largest number is the parent node.
(e) T F [2 points] We can always find the maximum in a min-heap in O(log n) time. Solution: FALSE. The maximum element in a min-heap can be anywhere in the bottom level of the heap. There are up to n/2 elements in the bottom level, so finding the maximum can take up to O(n) time.
I will assume that the Heap is implemented as an array (that is a very common way to implement a Heap).
You dont need to check the whole tree, "only" half.
So if I index the elements of the array starting from 1, the binary will look like this (where numbers ar ethe indexes in the array):
1
2 3
4 5 6 7
8 9 10 11 12 13
You only need to check floor(length(heapArray)/2) last elements, in the case above 7, so from 7 to 13. The nodes before that have children so they never will be the max. Than means checking n/2 elements so you still have O(n) complexity.
180
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
