Binary heap

Earth is home to thousands of species of trees: tall trees, deciduous trees, Christmas trees. Similarly, there is a large variety of trees in computer science as well. In this topic, we are going to learn about an important data structure that plays a vast role in several algorithms — binary heap. This type of tree will be the key to building one of the most efficient sorting algorithms, and we will also use it to implement several other data structures. So, let's get started.

Formal definition

A binary heap is a binary tree with the following properties:

• it is a complete binary tree;

• each node's value is the maximum (minimum) among all values present in its subtrees.

Let's recall that a complete binary tree has the following properties:

• all levels, except possibly the last one, are fully filled;

• if the last level is not complete, the nodes are filled from left to right.

As an attentive reader, you have noticed the word "minimum" in parentheses in the definition above. Let's clarify it. Binary heaps can be of two types: max-heaps and min-heaps. Naturally, a binary heap is a max-heap if each node's value is the maximum among all values present in its subtrees. In the opposite case, we call it a min-heap. The images below show various examples of binary heaps:

Let's call $T$ the last max-heap above. We will perform some interesting operations on it later in the topic.

Just like with some other trees, the elements of a binary heap can be of any data type for which the comparison operator is defined (integers, characters, strings, etc.). There exist numerous operations that we can perform on binary heaps; however, in this topic we will cover only some of them — in particular, those that we will need in the following topics on the subject.

Inserting an element

The features of the operation of inserting an element are dictated by the basic properties of a binary heap that we have listed at the beginning of this topic. Because of the completeness property, the only possible place to insert a new node is after the last node at the last level. If the last level is filled, then we put the node as the first one at the next level. However, this simple action may still break the maximum property. Formally, the steps of insertion are described below:

1. Add the new element at the end of the heap as described above.

2. Compare the added element with its parent: if its value is not greater than the value in the parent node, terminate.

3. Otherwise, swap them and return to step $2$. Note that our element will now have a new parent after the swapping.

The time complexity of this operation is $O(\log n)$, where $n$ is the number of the nodes in our tree. Indeed, the number of swappings performed is not greater than the height of the tree, namely $\log n$: each time we swap elements, we move one level above, and in the worst case we might need to reach the root.

Let's illustrate the steps of this operation with a simple example. The following images demonstrate the process of adding the item $12$ to the tree $T$:

Pseudocode for insert (max-heap):

The data structure for a tree is an array T, where the first element, T[1], is the element at the root, and the descendants of the element T[i] are T[2*i] and T[2*i+1] (but only when numbering elements of an array starting with 1).

function insert(T, k):
    T.append(k)                                                   // adding a new element to the end
    index_now = len(T)                                            // calculating the index of the added element
    index_prev = index_now // 2                                   // calculating the index of the previous node (divide by 2 and round to the smallest)
    while index_now > 1 and T[index_prev] < T[index_now]:         // the loop will continue until the current element is at the root (its index is equal to 1) and until the value in the node is less than the current one
        swap(T[index_prev], T[index_now])                         // swapping the current value and the value in the node
        index_now = index_prev                                    // changing the index of the current element (now it is equal to the node)
        index_prev = index_now // 2                               // recalculating the index of the new previous node

Extracting the maximum with heapify

The largest element in the max-heap is always the root of the tree, which means that to extract the maximum, we basically need to learn to remove the root element. However, deletion might cause trouble with the maximum property. Hence, we need to first define another crucial operation: heapify. It is an operation performed on a single node, moving it down the tree until the order is correct. In formal words, it works in the following way:

1. Compare the given node with its children: if our element is not smaller than the value of each of its children, we finish.

2. Otherwise, choose the child with the largest value. Swap it with our element. Repeat step $1$. Note that now our element is one level below, so its subtree will be smaller.

Now we can easily describe the extract_max operation:

1. Remove the root element. You might want to save its value in a variable or array for further operations.

2. Select the rightmost element from the lowest level (the leaves) and move it to the root.

3. Perform heapify on the new root.

Note that these operations are very similar to insertion. The only difference is that when the maximum property is broken, we move the elements down and not up. However, it is clear that the time taken is the same. Therefore, the time complexity for heapify is $O(\log n)$. extract_max has the same time complexity, as it performs heapify once and a couple of basic operations that take $O(1)$.

Here is how the operation to extract maximum is performed step by step on our heap $T$:

There are other operations that we can perform on binary heaps, such as removal and alteration of any value in the binary heap. Using these operations will require changing the data structure a bit. We will talk about it during practice. In the meantime, you can check some visualizations of the operations mentioned above.

Pseudocode for extract_max:

function extract_max(T):
    result = T[1]    // memorizing the root value
    T[1] = T.pop()   // writing the last value to the root (and deleting the root at the same time)
    heapify(T, 1)    // calling heapify for the root to restore the order of the elements in the heap
    return result    // returning the maximum from the heap

Pseudocode for heapify:

function heapify(T, k):
    index_now = k                                                           // we remember the index of the current element (which may violate the order)
    flag_was_changes = True                                                 // the flag keeps track of whether there have been changes in the heap
    while flag_was_changes:                                                 // the cycle will continue while the changes are taking place
        index_left = index_now * 2                                          // index of the left child element
        index_right = index_now * 2 + 1                                     // index of the right child element
        flag_was_changes = False                                            // we reset the flag value so that the cycle ends if there are no changes
        if index_left <= len(T) and T[index_left] > T[index_now]           // if the left index has not gone beyond the heap boundary and this element is larger than the current one
            or index_right <= len(T) and T[index_right] > T[index_now] then: // or the same for the right index
            flag_was_changes = True                                         // then we swap the elements, which means there will be changes
            if T[index_left] >= T[index_right] then:                        // if the left value is greater than the right one
                swap(T[index_left], T[index_now])                           // then we change the current value from the left 
                index_now = index_left                                      // and also change the index of the current element
            else:                                                           // else (if the right value is greater than the left one)
                swap(T[index_right], T[index_now])                          // we change the current value from the right
                index_now = index_right                                     // and change the index of the current element

Conclusion

Here is a quick recap. By definition, a binary heap is a complete binary tree with the following property: the value of each node is not smaller than the value of its children in the case of max-heaps, and not greater in the case of min-heaps. The most common operations on binary heaps are:

• insert(T, k) — inserting a new element $k$ in $O(\log n)$ time;

• heapify(T, k) — moving the element at index $k$ down the tree until it satisfies the maximum property; it takes $O(\log n)$ time;

• extract_max(T) — extracting the largest element; its time complexity is also $O(\log n)$.

All in all, a binary heap is a useful data structure with several important applications, as we shall soon see in some of the following topics.