Binary Heap

Description

A binary heap is a heap that uses a binary tree.

Heaps are trees which are arranged according to one of two orderings. Heaps can either be a max heap or min heap.

• Max heaps are ordered such that all parent nodes are greater than or equal to their children.
• Min heaps are ordered such that all parent nodes are less than or equal to their children.

A binary heap also adheres to an additional constraint. It must be a complete binary tree. This means that the only the last level of the tree is allowed to be partially filled, and any partially filled levels must be filled in from left to right.

Heaps are commonly used as the data structure for priority queues.

Implementation

Usually, an array or array-based data structure is used to implement a binary heap.

Since a binary heap uses a binary tree, the array indices can be used to connect a parent to its children in the following way:

For any node in the tree that has its value stored at index n, its children's values are located at the following indices:

• left child: 2n + 1
• right child: 2n + 2

The tree's root is located at index 0. The left child of the root is at index 1, and the left and right children of that node are at indices 3 and 4 respectively.

public class BinaryMaxHeap {
    ArrayList<Integer> nodeValueArray = new ArrayList<>();

    void insert(int value) {
        // Insert at the end of the list.
        nodeValueArray.add(value);

        // Compare the inserted value to its parent and on up the
        // tree, swapping values as we go, until the heap
        // property has been restored.

        int childIndex = nodeValueArray.size() - 1;
        int parentIndex = (childIndex - 1) / 2;

        if(childIndex > 0 && parentIndex >= 0) {
            while(true) {
                int childValue = nodeValueArray.get(childIndex);
                int parentValue = nodeValueArray.get(parentIndex);

                if(childValue > parentValue) {
                    // Heap property not adhered to, so swap value with parent
                    nodeValueArray.add(parentIndex, childValue);
                    nodeValueArray.add(childIndex, parentValue);

                    // The tree root has been reached.  Exit.
                    if(parentIndex == 0) {
                        break;
                    }
                    else {
                        // Compare parent with grandparent on next
                        // iteration.
                        childIndex = parentIndex;
                        parentIndex = (childIndex - 1) / 2;
                    }
                }
                else {
                    // Heap property has been restored.  Exit.
                    break;
                }
            }
        }
    }

    int extractMax() {
        // Max value is located at the root (index 0).
        int max = nodeValueArray.get(0);

        if(nodeValueArray.size() ==  1) {
            // Put the last node value at the root
            int lastNodeValue = nodeValueArray.remove(nodeValueArray.size() - 1);
            nodeValueArray.add(0, lastNodeValue);

            int parentIndex = 0;

            // If one of the children is larger than the parent, swap values.
            // Continue to swap until heap property has been restored.
            while(true) {
                int leftChildIndex = 2 * parentIndex + 1;
                int rightChildIndex = 2 * parentIndex + 2;

                int parentValue = nodeValueArray.get(parentIndex);
                int leftChildValue = Integer.MIN_VALUE;
                int rightChildValue = Integer.MIN_VALUE;

                int numNodes = nodeValueArray.size();

                // Ensure child nodes exist
                if(leftChildIndex < numNodes) {
                    leftChildValue = nodeValueArray.get(leftChildIndex);

                    if(rightChildIndex < numNodes) {
                        rightChildValue = nodeValueArray.get(rightChildIndex);
                    }
                }

                // Stop if the parent is larger than both children.
                if(parentValue >= leftChildValue && parentValue >= rightChildValue) {
                    break;
                }
                else {
                    // Find largest child
                    int largestChildIndex =
                        leftChildValue > rightChildValue ? leftChildIndex : rightChildIndex;

                    int largestChildValue = nodeValueArray.get(largestChildIndex);

                    // Swap parent with largest child
                    nodeValueArray.add(largestChildIndex, parentValue);
                    nodeValueArray.add(parentIndex, largestChildValue);

                    // Reset the parent index for the next iteration.
                    parentIndex = largestChildIndex;
                }
            }
        }
        else {
            // This was the last node in the tree, so remove.
            nodeValueArray.remove(0);
        }

        return max;
    }
}

Run time

Insert operation

For the worst case, there are O(ln n) comparisons, where n is the number of nodes. This is equivalent to the height of the binary tree.

Extract min/max operation

Similar to insertion there are O(ln n) comparisons to re-order the nodes so the tree retains the properties of a heap.

References

• Binary heap - Wikipedia
• Heap - Wikipedia