0
\$\begingroup\$

There is a Java program to check if a Heap (Min) is in the correct order. Heap Order means the parent is less than both left child and right child.

package testers;

import heap.Heap;
import java.util.List;

public class HeapTester
{
    public static void main(String[] args)
    {
        Heap<Integer> heap = new Heap <>();
        heap.add(50);
        heap.add(25);
        heap.add(26);
        heap.add(15);
        heap.add(10);
        heap.add(16);
        heap.add(3);
        heap.add(7);
        heap.add(10);
        heap.add(12);
        heap.add(2);
        System.out.println(heap);
        System.out.println(hasHeapOrder(heap.copy()));
    }

    private static <T extends Comparable<T>> boolean hasHeapOrder(List<T> list)
    {
        if(list.size() < 2) return true;

        boolean hasOrder = true;

        int parent = 0;
        int leftChild = 2 * parent + 1;
        int rightChild = 2 * parent + 2;

        while(leftChild < list.size())
        {
            if(list.get(parent).compareTo(list.get(leftChild)) > 0)
            {
                hasOrder = false;
                break;
            }
            if(rightChild < list.size())
            {
            if(list.get(parent).compareTo(list.get(rightChild)) > 0)
                {
                    hasOrder = false;
                    break;
                }
            }

            parent++;
            leftChild = 2 * parent + 1;
            rightChild = 2 * parent + 2;
        }
        return hasOrder;
    }  
}
\$\endgroup\$
1
\$\begingroup\$

Avoid flag variables if you don't need them

The hasOrder flag variable is unnecessary. When you set this variable to false, you could return false instead. If the end of the loop is reached, you can return true.

Avoid unnecessary special handling

The special treatment for the case list.size() < 2 is unnecessary. The rest of the implementation handles that case naturally.

Don't repeat yourself

The computation logic of the left and right child indexes is duplicated twice. You could eliminate that by changing the loop to while (true), and making this computation the first step of the loop instead of last:

while (true) {
  int leftChild = 2 * parent + 1;
  int rightChild = 2 * parent + 2;

  if (leftChild >= list.size()) {
    break;
  }

  // ...

Test using a unit test framework

Testing by printing stuff is not very useful. You have to read the output to verify it's correct, which takes mental effort, and error-prone. It's better to use a proper unit testing framework, where test cases will give you simple yes-no answers per test case; no need to re-interpret passing results.

Test all corner cases

Only one case is "tested". You need more tests to verify that hasHeapOrder correctly returns true or false depending on the input. I suppose you have an implementation of Heap such that heap.copy() returns a correctly heap-ordered list, and so hasHeapOrder returns true. At the minimum, you should verify that hasHeapOrder returns false for lists like 4, 1, 2 and 4, 5, 2.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.