Finding max element in a min-heap?

6
votes

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?

2
javaalgorithm
Do you have an idea of Min-heap and Max-heap? – jfly
assuming you don't want to store it off separately, you could just use a depth first search to find the max element in the min heap. – Matthew Madson
A min-heap let's you find the minimum in O(1) (because it's at the root). In a binary heap, the maximum could be in any of the leafs, of which you have O(n), so you can't find it faster than that (unless you have some additional structure in place). For example you can just have a max-binary-heap, in which you can find the max in O(1) but not the min. You might also have a look at min-max heaps for an example of a structure that lets you find both min and max in O(1) – Niklas B.
Check this [stackoverflow.com/questions/1876255/… might help you understanding [1]: stackoverflow.com/questions/1876255/… – Braza
possible duplicate of Time complexity to get min elements from MAX heap – Bernhard Barker

2 Answers

8
votes

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.

-3
votes

Define variable max and initialize it to 0.

HeapNode[] h;
int last;
int max=0;

If heap is not empty, start from 0 level and 0 position(root) and check for max value and iterate to left and right child.

public int getMax() throws Exception {
    if (isEmpty()) {
        Exception EmptyHeapException = new EmptyHeapException();
        throw EmptyHeapException;
    } else {
        //findMax(0, 0);    //If you want to use Iteration
        for(int i=0;i<=last;i++)
            max = Math.max(h[i].key, max);//Updated Thanks Raul Guiu
        return max;
    }
}

Iteration at every node until Node is last.

private void findMax(int i, int level) {
    if (i > last) return;
    if(max<h[i].key)
        max=h[i].key;
    findMax(2*i+1, level+1);//left node
    findMax(2*i+2, level+1);//right node
}

public boolean isEmpty() {
    return (last < 0);
}

You get maximum value from heap.