CODEWITHSUNDEEP
javaalgorithm
user2980566
user2980566

Reputation: 299

Finding max element in a min-heap?

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?

Upvotes: 7

Views: 22447

Answers (2)

Piyush
Piyush

Reputation: 1568

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.

Upvotes: -3

Raul Guiu
Raul Guiu

Reputation: 2404

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.

Upvotes: 10

Related Questions