Binary Heaps (With code in C, C++, and Java)

Introduction

A binary heap is a complete binary tree and possesses an interesting property called a heap property. The heap property states that every node in a binary tree must follow a specific order. There are two types of heaps depending upon how the nodes are ordered in the tree.

max-heap: In max-heap, a parent node is always larger than or equal to its children nodes.
min-heap: In min-heap, a parent node is always smaller than or equal to its children nodes.

Figure 1 shows an example of a max and min heap.

Fig 1: A max-heap (left) and a min-heap (right)

Since binary heap is a complete binary tree, the height of the tree is always O(log n). This is very important because most of the operations we perform in the binary heap scan the tree from top to bottom or bottom to top which leads to complexity of O(log n). This helps us to efficiently implement one sorting algorithm called heap sort and a priority queue.

A binary heap can be efficiently implemented using an array (static or dynamic). To implement a binary heap of height h, we need O(2^h) memory blocks and we insert the items in the array following level-order (breadth first) of a tree. Figure 2 shows the array implementation of a tree shown in Figure 1 (left).

Fig 2: An array implementation of a max-heap given in figure 1

The parent, the left child, and the right of a node at i can be calculated as

Parent = (i - 1) / 2 (Take floor).
Left Child = 2*i + 1
Right Child = 2*i + 2

Operations on a binary heap

The various operations on a binary heap are given in detail below. Please note that I am describing the max-heap here but with a little modification this can be changed to min-heap.

Insertion

The new item is initially inserted at the end of the heap (at the last position of the array). If it satisfies the heap property then we are done. Otherwise, we shift it up in the tree as long as it violates the heap property. The algorithm for inserting is given below.

1. Insert the new item at the end of the heap.
2. Compare the newly inserted item with its parent. 
   If the parent is larger, stop. If the parent is smaller,  swap the item with its parent.
3. Repeat step 2 until the parent is larger or equal to the item.

Figure 3 shows the steps of inserting an item in an example heap.

Fig 3: Steps for inserting an item to the heap

In order to insert a new item, in the worst case, we need to travel all the way to the root item. Therefore, the complexity of the insertion operation is O(log n).

Delete Max

In a max heap, the first item is always the maximum. So to delete the maximum, we delete the first item. After the deletion of the first time, we replace the vacant first position by the last time in the array. We might need to shift this item down in order to keep the heap property intact. The algorithm is given below.

1. Store the first time in the tree in some temporary variable.
2. Replace the first node with the item in the last node.
3. Check the first node with its children nodes. 
   If the left child is larger, we swap it with the left child. 
   If the right node is larger, we swap it with the right node. 
4. Repeat step 3 until the parent node is larger than the left and right child node.
5. Return the maximum value (stored in the temporary variable).

Step 3 and 4 in the above algorithm is called a max heapify (or bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down). This step moves the item down in the tree to its appropriate place. Figure 4 shows an example of this process.

Fig 4: An example of a max-heapify process. The item in the first position is shifted down to the tree to its appropriate position.

As the insertion step, the complexity of delete max operation is O(log n).

Building a heap

We can build the heap from an array of n items using two methods. In the first method, we successively perform the insert operation on the heap. In n insert operations, we can build the heap from the array. Since each insert operation takes O(log n) time and there are n such operations, the complexity of this method is O(nlog n).

Another method does this in linear time. In this method, the internal node of the tree is max-heapified one at a time. If there are n items in the array, we start from the item at n/2 position and heapify it and we move to next item and do the same all the way down to the first item in the array. Consider a tree given in figure 5.

Fig 5: The internal nodes are heapified to move them to their appropriate position

There are 10 nodes in the tree. Since the tree is a complete binary tree there are n/2 (floor) leaf nodes. We ignore all the leaf nodes and heapify the internal nodes. Using this method, we can build the heap in linear time O(n). The algorithm for this method is given below.

build-max-heap(arr) {
    n = length of arr;
    for (i = n/2; i > 0; i--) {
        max-heapify(arr, i);
    }
}

Implementation

The implementation of heap in C, C++, and Java is given below.

#include 

#define MAX_SIZE 15

// returns the index of the parent node
int parent(int i) {
    return (i - 1) / 2;
}

// return the index of the left child 
int left_child(int i) {
    return 2*i + 1;
}

// return the index of the right child 
int right_child(int i) {
    return 2*i + 2;
}

void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

// insert the item at the appropriate position
void insert(int a[], int data, int *n) {
    if (*n >= MAX_SIZE) {
        printf("%s\n", "The heap is full. Cannot insert");
        return;
    }
    // first insert the time at the last position of the array 
    // and move it up
    a[*n] = data;
    *n = *n + 1;


    // move up until the heap property satisfies
    int i = *n - 1;
    while (i != 0 && a[parent(i)] < a[i]) {
        swap(&a[parent(i)], &a[i]);
        i = parent(i);
    }
}

// moves the item at position i of array a
// into its appropriate position
void max_heapify(int a[], int i, int n){
    // find left child node
    int left = left_child(i);

    // find right child node
    int right = right_child(i);

    // find the largest among 3 nodes
    int largest = i;

    // check if the left node is larger than the current node
    if (left <= n && a[left] > a[largest]) {
        largest = left;
    }

    // check if the right node is larger than the current node
    if (right <= n && a[right] > a[largest]) {
        largest = right;
    }

    // swap the largest node with the current node 
    // and repeat this process until the current node is larger than 
    // the right and the left node
    if (largest != i) {
        int temp = a[i];
        a[i] = a[largest];
        a[largest] = temp;
        max_heapify(a, largest, n);
    }

}

// converts an array into a heap
void build_max_heap(int a[], int n) {
    int i;
    for (i = n/2; i >= 0; i--) {
        max_heapify(a, i, n);
    } 
}

// returns the  maximum item of the heap
int get_max(int a[]) {
    return a[0];
}

// deletes the max item and return
int extract_max(int a[], int *n) {
    int max_item = a[0];

    // replace the first item with the last item
    a[0] = a[*n - 1];
    *n = *n - 1;

    // maintain the heap property by heapifying the 
    // first item
    max_heapify(a, 0, *n);
    return max_item;
}

// prints the heap
void print_heap(int a[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        printf("%d\n", a[i]);
    }
    printf("\n");
}


int main() {
    int n = 10;
    int a[MAX_SIZE];
    a[1] = 10; a[2] = 12; a[3] = 9; a[4] = 78; a[5] = 33; a[6] = 21; a[7] = 35; a[8] = 29; a[9] = 5; a[10] = 66;
    build_max_heap(a, n);
    insert(a, 55, &n);
    insert(a, 56, &n);
    insert(a, 57, &n);
    insert(a, 58, &n);
    insert(a, 100, &n);
    print_heap(a, n);
    return 0;
}

// C++ implementation of a binary heap

#include 
using namespace std;

class BinaryHeap {
private:
    const static int MAX_SIZE = 15;
    int heap[MAX_SIZE];
    int size;

public:
    BinaryHeap() {
        size = 0;
    }

    // returns the index of the parent node
    static int parent(int i) {
        return (i - 1) / 2;
    }

    // return the index of the left child 
    static int leftChild(int i) {
        return 2*i + 1;
    }

    // return the index of the right child 
    static int rightChild(int i) {
        return 2*i + 2;
    }


    static void swap(int *x, int *y) {
        int temp = *x;
        *x = *y;
        *y = temp;
    }

    // insert the item at the appropriate position
    void insert(int data) {
        if (size >= MAX_SIZE) {
            cout<<"The heap is full. Cannot insert"<<endl;
            return;
        }

        // first insert the time at the last position of the array 
        // and move it up
        heap[size] = data;
        size = size + 1;


        // move up until the heap property satisfies
        int i = size - 1;
        while (i != 0 && heap[BinaryHeap::parent(i)] < heap[i]) {
            BinaryHeap::swap(&heap[BinaryHeap::parent(i)], &heap[i]);
            i = BinaryHeap::parent(i);
        }
    }

    // moves the item at position i of array a
    // into its appropriate position
    void maxHeapify(int i){
        // find left child node
        int left = BinaryHeap::leftChild(i);

        // find right child node
        int right = BinaryHeap::rightChild(i);

        // find the largest among 3 nodes
        int largest = i;

        // check if the left node is larger than the current node
        if (left <= size && heap[left] > heap[largest]) {
            largest = left;
        }

        // check if the right node is larger than the current node 
        // and left node
        if (right <= size && heap[right] > heap[largest]) {
            largest = right;
        }

        // swap the largest node with the current node 
        // and repeat this process until the current node is larger than 
        // the right and the left node
        if (largest != i) {
            int temp = heap[i];
            heap[i] = heap[largest];
            heap[largest] = temp;
            maxHeapify(largest);
        }

    }

    // returns the  maximum item of the heap
    int getMax() {
        return heap[0];
    }

    // deletes the max item and return
    int extractMax() {
        int maxItem = heap[0];

        // replace the first item with the last item
        heap[0] = heap[size - 1];
        size = size - 1;

        // maintain the heap property by heapifying the 
        // first item
        maxHeapify(0);
        return maxItem;
    }

    // prints the heap
    void printHeap() {
        for (int i = 0; i < size; i++) {
            cout<endl;
        }
        cout<<endl;
    }
};

int main() {
    BinaryHeap heap;
    return 0;
}

// Java implementation of a binary heap

class BinaryHeap {
    private static final int MAX_SIZE = 15;
    private int [] heap;
    private int size;

    public BinaryHeap() {
        heap = new int[MAX_SIZE];
        size = 0;
    }

    // returns the index of the parent node
    public static int parent(int i) {
        return (i - 1) / 2;
    }

    // return the index of the left child 
    public static int leftChild(int i) {
        return 2*i + 1;
    }

    // return the index of the right child 
    public static int rightChild(int i) {
        return 2*i + 2;
    }

    // insert the item at the appropriate position
    public void insert(int data) {
        if (size >= MAX_SIZE) {
            System.out.println("The heap is full. Cannot insert");
            return;
        }

        // first insert the time at the last position of the array 
        // and move it up
        heap[size] = data;
        size = size + 1;


        // move up until the heap property satisfies
        int i = size - 1;
        while (i != 0 && heap[BinaryHeap.parent(i)] < heap[i]) {
            int temp = heap[i];
            heap[i] = heap[parent(i)];
            heap[parent(i)] = temp;
            i = BinaryHeap.parent(i);
        }
    }

    // moves the item at position i of array a
    // into its appropriate position
    public void maxHeapify(int i){
        // find left child node
        int left = BinaryHeap.leftChild(i);

        // find right child node
        int right = BinaryHeap.rightChild(i);

        // find the largest among 3 nodes
        int largest = i;

        // check if the left node is larger than the current node
        if (left <= size && heap[left] > heap[largest]) {
            largest = left;
        }

        // check if the right node is larger than the current node 
        // and left node
        if (right <= size && heap[right] > heap[largest]) {
            largest = right;
        }

        // swap the largest node with the current node 
        // and repeat this process until the current node is larger than 
        // the right and the left node
        if (largest != i) {
            int temp = heap[i];
            heap[i] = heap[largest];
            heap[largest] = temp;
            maxHeapify(largest);
        }

    }

    // returns the  maximum item of the heap
    public int getMax() {
        return heap[0];
    }

    // deletes the max item and return
    public int extractMax() {
        int maxItem = heap[0];

        // replace the first item with the last item
        heap[0] = heap[size - 1];
        size = size - 1;

        // maintain the heap property by heapifying the 
        // first item
        maxHeapify(0);
        return maxItem;
    }

    // prints the heap
    public void printHeap() {
        for (int i = 0; i < size; i++) {
            System.out.print(heap[i] + " ");
        }
        System.out.println();
    }

    public static void main(String [] args) {
        BinaryHeap heap = new BinaryHeap();
    }
}