can anyone help me understand this code part ?
this is about binary minimum heap , ie root has the lowest key..
the part of the code im trying to understand checks whether the subtree ( of a certain minHeap pq[1..N] ), rooted at k is also a min heap or not

    private boolean isMinHeap(int k) {
        if (k > N)
            return true;
        int left = 2 * k, right = 2 * k + 1;
        if (left <= N && greater(k, left))
            return false;
        if (right <= N && greater(k, right))
            return false;
        return isMinHeap(left) && isMinHeap(right);
    }

in the 2nd line , i dont understand the if statement... as the array which is used to implement the minheap is [1..N] , shouldnt k>N return false? as a value > N means its out of the array?

this is the full version from where i got the above part.

Recommended Answers

All 2 Replies

According to that method a tree is a min heap if there is no node that has a value greater than one of its children. When the index is off the end of the array then it has no nodes at all, so it can't have any node with a value greater than one of its children.

When writing a recursive algorithm like this you have to decide what value you want to give to an empty tree even though it's not obvious whether an empty tree is a min heap. In this case true was chosen because it is convenient that way; it means that when you have a min heap you can recurse all the way down to the leaves without ever encountering a false.

thank you :) i get it now.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.