0
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ I have a feeling that this method in itself is fine but perhaps your overall design could be restructured/improved. If you want you can post the rest of your implementation as well so we can look at it? \$\endgroup\$ – Imus Apr 15 '17 at 13:38
  • \$\begingroup\$ @lmus, will post it as another question. \$\endgroup\$ – Sean Francis N. Ballais Apr 15 '17 at 13:55
1
\$\begingroup\$
    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.

\$\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.