#check if array represents a min heap

1 messages · Page 1 of 1 (latest)

foggy oyster
#

`
public class Solution {

public static void main(String[] args) {
    int arr[] = {90, 15, 10, 7, 12, 2, 7, 12}; 
    int n = arr.length-1; 
   
    if (isHeap(arr,0, n)) { 
        System.out.println("Yes"); 
    } else { 
        System.out.println("No"); 
    } 

    

}
static boolean isHeap(int arr[], int i, int n) {
    
    // If (2 * i) + 1 >= n, then leaf node, so return true 
    if (i >= (n-1) / 2) { 
        
        return true; 
    } 

    // If an internal node and 
    // is greater than its 
    // children, and same is 
    // recursively true for the 
    // children 
    if (arr[i] <= arr[2 * i + 1] && arr[i] <= arr[2 * i + 2] && isHeap(arr, 2 * i + 1, n) && isHeap(arr, 2 * i + 2, n)) { 
        //System.out.print(i + " ");
        return true; 
    } 

    return false; 
     

}

}`

my base case (i >= (n-1) / 2) is not correct ,can someone help me figure out where am going wrong

leaden jewelBOT
#

⌛ This post has been reserved for your question.

Hey @foggy oyster! Please use /close or the Close Post button above when your problem is solved. Please remember to follow the help guidelines. This post will be automatically closed after 300 minutes of inactivity.

TIP: Narrow down your issue to simple and precise questions to maximize the chance that others will reply in here.

scenic elm
#

in english what does i >= n say?

foggy oyster
scenic elm
#

is > greater than or less than?

ivory fossil
#

@foggy oyster is this post still active/ is it different from your other post?

foggy oyster
foggy oyster
#

I get ur point but i am concerned with the base case

scenic elm
#

i doubt u get my point
programming is the art of communicating ur ideas to a computer
the fact that something is not working means there is a failure in communicating
us discussing ur code using math symbols will achieve nothing if one of us is confused/mistaken about the meaning of a symbol

foggy oyster
#

I am getting an index out of bounds error

#

if the symbol would have been wrong in my second if loop I would have received wrong output instead of an error

scenic elm
#

I agree that the symbol looks correct it's the -1 that I'm worried about
But we can't discuss it without confirming we r both talking about the same thing

# 
    static boolean isHeap(int arr[], int i, int n) {
        
        // If (2 * i) + 1 >= n, then leaf node, so return true 
        if (i >= (n-1) / 2) {      
            return true; 
        } 

        // If an internal node and 
        // is greater than its 
        // children, and same is 
        // recursively true for the 
        // children 
        if (arr[i] <= arr[2 * i + 1] && arr[i] <= arr[2 * i + 2] && isHeap(arr, 2 * i + 1, n) && isHeap(arr, 2 * i + 2, n)) { 
            //System.out.print(i + " ");
            return true; 
        } 

        return false;
    }
}
scenic elm
#

so lets make the code a bit more legible:

    static boolean isHeap(int arr[], int i, int n) {
        
        // If (2 * i) + 1 >= n, then leaf node, so return true 
        if (i >= (n-1) / 2) {      
            return true; 
        } 

        // If an internal node and 
        // is greater than its 
        // children, and same is 
        // recursively true for the 
        // children
        final int lChild = 2 * i + 1; 
        if (arr[i] <= arr[lChild] && arr[i] <= arr[lChild + 1] && isHeap(arr, lChild, n) && isHeap(arr, lChild + 1, n)) { 
            //System.out.print(i + " ");
            return true; 
        } 

        return false;
    }
#

and lets break up that monster boolean expression:

    static boolean isHeap(int arr[], int i, int n) {
        
        // If (2 * i) + 1 >= n, then leaf node, so return true 
        if (i >= (n-1) / 2) {      
            return true; 
        }

        // If either of the children is smaller then the heap is invalid
        final int lChild = 2 * i + 1;
        if (arr[i] > arr[lChild] || arr[i] > arr[lChild + 1]) {
            return false;
        }

        // Check recursively if the children are valid
        if (isHeap(arr, lChild, n) && isHeap(arr, lChild + 1, n)) { 
            //System.out.print(i + " ");
            return true; 
        } 
        return false;
    }

(edit) actually, the bottom can be massively simplified further

    static boolean isHeap(int arr[], int i, int n) {
        
        // If (2 * i) + 1 >= n, then leaf node, so return true 
        if (i >= (n-1) / 2) {      
            return true; 
        }

        // If either of the children is smaller then the heap is invalid
        final int lChild = 2 * i + 1;
        if (arr[i] > arr[lChild] || arr[i] > arr[lChild + 1]) {
            return false;
        }

        // Check recursively if the children are valid
        return (isHeap(arr, lChild, n) &&
              isHeap(arr, lChild + 1, n));
    }
#

@foggy oyster pls run this code, see if i refactored correctly and the bug still occurs

#

ps, i hate recursion, this is so much easier as a loop

# 
static boolean isHeap(int[] arr) {
  if (arr.length == 0) return false;
  if (arr.length == 1) return true;

  //skip arr[0] because other elements are compared to it
  for (int i=1; i<arr.length; i+=2) {
    final int parent = i/2;
    if (arr[i] < arr[parent] || arr[i+1] < arr[parent]) {
      return false;
    }
  }
  return true;
}

not only can u do an early termination with a loop
its also MUCH easier to read, implement, debug and use

foggy oyster
#

Thx a lot @scenic elm

#

yes the iterative approach is definitely better

scenic elm
#

we should still fix ur code

scenic elm
foggy oyster
#

so the recursive approach wasnt efficient

scenic elm
#

well in the code i posted, i dont handle that edge case either 😛

foggy oyster
scenic elm
#

where the array is an odd length

foggy oyster
#

I really appreciate the fact that u are taking time out of ur schedule to help me with my problems

#

sadly I dont have anything to return the favour