Binary Heap Order Fixing in Java

Question

I am implementing a binary heap in Java. I've come to the point where I have to fix the heap ordering whenever a new node is being inserted to the heap. The code below fixes the heap ordering. I have a gut feeling that the code can be improved.

private void fixHeapOrder(Node anomalousNode)
{
    if (this.heapType == 0) {
        // Min-heaps
        while (anomalousNode.getParent().getValue() > anomalousNode.getValue()) {
            // In min-heaps, the parent's value must be less than or equal to the
            // value of its children.

            Node.swapValues(anomalousNode.getParent(), anomalousNode);
            anomalousNode = anomalousNode.getParent();
        }
    } else if (this.heapType == 1) {
        // Max-heaps
        while (anomalousNode.getParent().getValue() < anomalousNode.getValue()) {
            // In max-heaps, the parent's value must be greater than or equal to the
            // value of its children.

            Node.swapValues(anomalousNode.getParent(), anomalousNode);
            anomalousNode = anomalousNode.getParent();
        }
    }
}

How else can I improve the code?

Answer 1

    if (this.heapType == 0) {

and

    } else if (this.heapType == 1) {

Rather than using magic numbers, it is typical to use Enum values for this in Java.

    if (heapType == HeapType.MIN) {

and

    } else if (heapType == HeapType.MAX) {

or in the latter case, just

    } else {

Presumably there are only two types of heap.

You don't have to say this.heapType. It's enough to just say heapType if there is no conflict. You can add the this. if you find it makes things clearer, but it's not functionally necessary. You only need to specify this. if there is another variable with the same name as the object field.

Another way to do this would be with an interface and separate implementations for Max and Min heaps. That may not be better though. It's hard to comment with so little context. It would save the if/else here but might cause problems elsewhere.

In general, I can't comment on how this method works with other methods like the caller or swapValues, as those definitions are not included. Should you work directly with the value rather than the node? Should this be integrated into the caller's logic? I can't really tell.