Introducing the Binomial Heap data structure 2 – Arrays, collections and data structures

Implementing findMin()

Finding the minimum key of a Binomial Heap requires us to loop the root list (which is a linked list) and find the smallest key. This can be optimized from O(log n) to O(1) if we decide to maintain a pointer to the minimum root. However, the O(log n) approach is listed here:

public int findMin() {
  if (head == null) {
    return Integer.MIN_VALUE;
  } else {
    Node min = head;
    Node nextNode = min.sibling;
    while (nextNode != null) {
      if (nextNode.key < min.key) {
        min = nextNode;
      }
      nextNode = nextNode.sibling;
    }
    return min.key;
  }
}

Since our Binomial Heap holds primitive integers, we use Integer.MIN_VALUE as an equivalent to no value. If you adjust the implementation to use Integer or generic T then you can replace Integer.MIN_VALUE with null.

Implementing extractMin()

Before extracting the minimum key we have to find it. Afterward, we delete it. Finally, we have to union the resulting sub-trees as follows:

public int extractMin() {
  if (head == null) {
    return Integer.MIN_VALUE;
  }
  Node min = head;
  Node minPrev = null;
  Node nextNode = min.sibling;
  Node nextNodePrev = min;
  while (nextNode != null) {
    if (nextNode.key < min.key) {
      min = nextNode;
      minPrev = nextNodePrev;
    }
    nextNodePrev = nextNode;
    nextNode = nextNode.sibling;
  }
  deleteTreeRoot(min, minPrev);
  return min.key;
}

The deleteTreeRoot() is a helper method useful for deleting the given root and union the remaining sub-trees:

private void deleteTreeRoot(Node root, Node previousNode) {
  if (root == head) {
    head = root.sibling;
  } else {
    previousNode.sibling = root.sibling;
  }
  Node unionHeap = null;
  Node child = root.child;
  while (child != null) {
    Node nextNode = child.sibling;
    child.sibling = unionHeap;
    child.parent = null;
    unionHeap = child;
    child = nextNode;
  }
      
  BinomialHeap toUnionHeap = new BinomialHeap(unionHeap);
  head = unionHeap(toUnionHeap);
}

The union operation is depicted as the last operation of this section.

Implementing decreaseKey(int key, int newKey)

Decreasing a key value means replacing an existing key with a smaller one. When this operation happens, the new key may be smaller than the key of its parent, which means that the min-heap property is violated. This scenario requires us to swap the current node with its parent, its parent with its grandparent, and so on until we reestablish the min-heap property. The implementation starts as follows:

public void decreaseKey(int key, int newKey) {
      
  Node found  = findByKey(key);
  if (found != null) {
    decreaseKey(found, newKey);
  }
}
private void decreaseKey(Node node, int newKey) {
  node.key = newKey;
  goUp(node, false);
}

The goUp() method is a helper method used to reestablish the min-heap property:

private Node goUp(Node node, boolean goToRoot) {
  Node parent = node.parent;
  while (parent != null && (goToRoot
      || node.key < parent.key)) {
    int t = node.key;
    node.key = parent.key;
    parent.key = t;
    node = parent;
    parent = parent.parent;
  }
  return node;
}

As you will see next, this helper is useful for deleting a node as well.

Implementing delete(int key)

Deleting a key starts by finding the corresponding Node and decreasing it to the minimum (Integer.MIN_VALUE). Next, we delete the minimum from the heap and connect the remaining sub-trees. The implementation relies on the goUp() and deleteTreeRoot() helpers listed in the previous sections.

public void delete(int key) {
  Node found = findByKey(key);
  if (found != null) {
    delete(found);
  }
}
private void delete(Node node) {
  node = goUp(node, true);
  if (head == node) {
    deleteTreeRoot(node, null);
  } else {
    Node previousNode = head;
    while (previousNode.sibling.key != node.key) {
      previousNode = previousNode.sibling;
    }
    deleteTreeRoot(node, previousNode);
  }
}

Finally, let’s talk about union heaps.