Skip to main content

Problem Solving with Algorithms and Data Structures using C++: The PreTeXt Interactive Edition

Section 8.10 Binary Heap Implementation

Subsection 8.10.1 The Structure Property

In order to make our heap work efficiently, we will take advantage of the logarithmic nature of the binary tree to represent our heap. In order to guarantee logarithmic performance, we must keep our tree balanced. A balanced binary tree has roughly the same number of nodes in the left and right subtrees of the root. In our heap implementation we keep the tree balanced by creating a complete binary tree. A complete binary tree is a tree in which each level has all of its nodes. The exception to this is the bottom level of the tree, which we fill in from left to right. Figure 8.10.1 shows an example of a complete binary tree.
described in detail following the image
Diagram of a complete binary tree. The top node, or the root, is labeled ’5’. This root node has two child nodes: ’9’ to the left and ’11’ to the right. Each of these child nodes further branches out into two more nodes. The left child ’9’ has nodes ’14’ and ’18’ as children. ’14’ has a single left child labeled ’33’, while ’18’ has two children labeled ’17’ and ’27’. On the right side, the child ’11’ has two children labeled ’19’ and ’21’. The tree is balanced and each level is fully filled except for the last level, which is filled from the left. The image is labeled ’Figure 1: A Complete Binary Tree’.
Figure 8.10.1. A Complete Binary Tree.
Another interesting property of a complete tree is that we can represent it using a single vector. We do not need to use nodes and references or even vectors of vectors. Because the tree is complete, the left child of a parent (at position \(p\)) is the node that is found in position \(2p\) in the vector. Similarly, the right child of the parent is at position \(2p + 1\) in the vector. To find the parent of any node in the tree, we can simply use integer division. Given that a node is at position \(n\) in the vector, the parent is at position \(n/2\text{.}\) Figure 8.10.2 shows a complete binary tree and also gives the vector representation of the tree. Note the \(2p\) and \(2p+1\) relationship between parent and children. The vector representation of the tree, along with the full structure property, allows us to efficiently traverse a complete binary tree using only a few simple mathematical operations. We will see that this also leads to an efficient implementation of our binary heap.

Subsection 8.10.2 The Heap Order Property

The method that we will use to store items in a binary heap relies on maintaining the heap order property. The heap order property is as follows: In a binary heap, for every node \(x\) with parent \(p\text{,}\) the key in \(p\) is smaller than or equal to the key in \(x\text{.}\) Figure 8.10.2 also illustrates a complete binary tree that has the heap order property.
described in detail following the image
The image depicts a complete binary tree at the top and its corresponding vector representation at the bottom. The binary tree has a root node labeled ’5’, which branches out to two nodes labeled ’9’ on the left and ’11’ on the right. The ’9’ node further branches into ’14’ and ’18’, which in turn have children ’33’ and ’17’, and ’27’, respectively. The ’11’ node branches into ’19’ and ’21’. Below the binary tree, there is a vector representation with indexed positions from 0 to 11. The values in the vector are arranged as ’5’, ’9’, ’11’, ’14’, ’18’, ’19’, ’21’, ’33’, ’17’, ’27’, respecting the binary tree’s structure. The image is labeled ’Figure 2: A Complete Binary Tree, along with its Vector Representation’.
Figure 8.10.2. A Complete Binary Tree, along with its Vector Representation.

Subsection 8.10.3 Heap Operations

We will begin our implementation of a binary heap with the constructor. Since the entire binary heap can be represented by a single vector, all the constructor will do is initialize the vector and an attribute currentSize to keep track of the current size of the heap. Listing 8.10.3 shows the C++ code for the constructor. You will notice that an empty binary heap has a single zero as the first element of heapList and that this zero is not used, but is there so that simple integer division can be used in later methods.
class BinHeap{
    private:
        vector<int> heapvector;
        int currentSize;

    public:
        BinHeap(vector<int> heapvector){
            this->heapvector = heapvector;
            this->currentSize = 0;
        }
}
Listing 8.10.3. BinHeap Class and Constructor
The next method we will implement is insert. The easiest, and most efficient, way to add an item to a vector is to simply append the item to the end of the vector. The good news about appending is that it guarantees that we will maintain the complete tree property. The bad news about appending is that we will very likely violate the heap structure property. However, it is possible to write a method that will allow us to regain the heap structure property by comparing the newly added item with its parent. If the newly added item is less than its parent, then we can swap the item with its parent. Figure 8.10.4 shows the series of swaps needed to percolate the newly added item up to its proper position in the tree.
described in detail following the image
Image showing the process of percolating a newly added node to its proper position in a binary heap. The diagram consists of three stages illustrating how the heap structure property is restored through swaps. In the first stage, a new item labeled "7" is appended as a leaf node under the node "18" in the binary tree, which initially violates the heap structure property. The parent-child relationship is unbalanced because "7" is smaller than its parent "18." In the second stage (swap 1), the new item "7" is swapped with its parent "18," moving up the tree. The new structure partially restores the heap property, but "7" is now a child of node "9," still violating the heap structure. In the third stage (swap 2), "7" is swapped with its new parent "9," percolating up to its proper position. At this point, the heap structure property is fully restored, and the tree satisfies the complete binary heap requirements. Arrows and dashed lines in the diagram highlight the movement of nodes during each swap.
Figure 8.10.4. Percolate the New Node up to Its Proper Position.
Notice that as we percolate an item up the tree, the heap property is restored between the newly added item and the parent. We also preserve the heap property for any siblings. If an item is very small, we will need to swap it up another level. In fact, we may need to keep swapping until we get to the top of the tree. Listing 8.10.5 shows the percUp method, which percolates a new item as far up the tree as it needs to go to maintain the heap property. Here is where the unused element at the beginning of the heapvector is important. By storing the first node at index 1 instead of at index 0, we can compute the parent of any node by using simple integer division because the parent of a node is computed by dividing the index of the current node by 2 (the parent of node 9 is at index 4, the parent of 4 is at index 2, and the parent of 2 is at index 1).
We are now ready to write the insert method (see Listing 8.10.6). Most of the work in the insert method is really done by percUp. Once a new item is appended to the tree, percUp takes over and positions the new item properly.
void percUp(int i){
    while ((i / 2) > 0){
        if (this->heapvector[i] < this->heapvector[i/2]){
            int tmp = this->heapvector[i/2];
            this->heapvector[i/2] = this->heapvector[i];
            this->heapvector[i] = tmp;
        }
        i = i/2;
    }
}
Listing 8.10.5. percUp Method
void insert(int k){
    this->heapvector.push_back(k);
    this->currentSize = this->currentSize + 1;
    this->percUp(this->currentSize);
}
Listing 8.10.6. insert Method
With the insert method properly defined, we can now look at the delMin method. Since the heap property requires that the root of the tree be the smallest item in the tree, finding the minimum item is easy. The hard part of delMin is restoring full compliance with the heap structure and heap order properties after the root has been removed. We can restore our heap in two steps. First, we will restore the root item by taking the last item in the vector and moving it to the root position. Moving the last item maintains our heap structure property. However, we have probably destroyed the heap order property of our binary heap. Second, we will restore the heap order property by pushing the new root node down the tree to its proper position. Figure 8.10.7 shows the series of swaps needed to move the new root node to its proper position in the heap.
described in detail following the image
Image showing the process of percolating the root node down the tree in a binary heap after removing the minimum (root) value. The diagram consists of four stages illustrating how the heap structure property is restored. In the first stage, the root node "5" is removed, leaving an empty root. The last node in the heap, "27," is moved to the root, creating a temporary imbalance in the heap structure. Arrows indicate the initial swap process. In the second stage (swap 1), the new root "27" is swapped with the smaller of its two children, "9," moving "27" down the tree and partially restoring the heap structure. In the third stage (swap 2), "27" is swapped with its smaller child "14," further percolating it down the tree and improving the heap structure. In the fourth stage (swap 3), "27" is swapped with its child "17," reaching its proper position. The heap structure is now fully restored, maintaining the binary heap properties. Each stage is annotated with arrows and labels indicating the swaps, clearly demonstrating the percolation process.
Figure 8.10.7. Percolating the Root Node down the Tree.
In order to maintain the heap order property, all we need to do is swap the root with its smallest child less than the root. After the initial swap, we may repeat the swapping process with a node and its children until the node is swapped into a position on the tree where it is already less than both children. The code for percolating a node down the tree is found in the percDown and minChild methods in Listing 8.10.8.
void percDown(int i){
    while ((i*2) <= this->currentSize){
        int mc = this->minChild(i);
        if (this->heapvector[i] > this->heapvector[mc]){
            int tmp = this->heapvector[i];
            this->heapvector[i] = this->heapvector[mc];
            this->heapvector[mc] = tmp;
        }
        i = mc;
    }
}

int minChild(int i){
    if (((i*2)+1) > this->currentSize){
        return i * 2;
    }
    else{
        if (this->heapList[i*2] < this->heapList[(i*2)+1]){
            return i * 2;
        }
        else{
            return (i * 2) + 1;
        }
    }
}
Listing 8.10.8. percDown and minChild Methods
The code for the delMin operation is in Listing 8.10.9. Note that once again the hard work is handled by a helper function, in this case percDown.
int delMin(){
    if (this->currentSize > 1){
        int retval = this->heapvector[1];
        this->heapvector[1] = this->heapvector[this->currentSize];
        this->currentSize = this->currentSize - 1;
        this->heapvector.pop_back();
        this->percDown(1);
        return retval;
    }
    else{
        int retval = this->heapvector[0];
        this->heapvector[1] = this->heapvector[this->currentSize];
        this->currentSize = this->currentSize - 1;
        this->heapvector.pop_back();
        this->percDown(1);
        return retval;
    }
}
Listing 8.10.9. delMin Implementation
To finish our discussion of binary heaps, we will look at a method to build an entire heap from a vector of keys. The first method you might think of may be like the following. Given a vector of keys, you could easily build a heap by inserting each key one at a time. Since you are starting with a vector of one item, the vector is sorted and you could use binary search to find the right position to insert the next key at a cost of approximately \(O(\log{n})\) operations. However, remember that inserting an item in the middle of the vector may require \(O(n)\) operations to shift the rest of the vector over to make room for the new key. Therefore, to insert \(n\) keys into the heap would require a total of \(O(n \log{n})\) operations. However, if we start with an entire vector then we can build the whole heap in \(O(n)\) operations. Listing 8.10.10 shows the code to build the entire heap.
void buildheap(vector<int> avector){
    int i = avector.size() / 2;
    this->currentSize = avector.size();
    this->heapvector = avector;
    while (i > 0){
        this->percDown(i);
        i = i - 1;
    }
}
Listing 8.10.10. buildHeap Implementation
described in detail following the image
Image showing the process of building a binary heap from the vector [9, 6, 5, 2, 3] using the `buildHeap` algorithm. The diagram consists of four stages that represent the percolation process as elements are rearranged to satisfy the heap properties. In the first stage, the initial heap is shown as an unstructured tree with the vector elements arranged in their input order. In the second stage (i = 2), the element at index 2, "5," is percolated down as needed to maintain the heap property, though no swaps are required at this step. In the third stage (i = 1), the element at index 1, "6," is percolated down and swapped with its smaller child, "2," to restore the heap property. In the fourth stage (i = 0), the element at the root, "9," is percolated down through successive swaps with its smaller children ("2" and "3") to reach its proper position in the heap. Each stage is annotated with arrows and labels, illustrating the transformations at each step of the heap-building process.
Figure 8.10.11. Building a Heap from the vector [9, 6, 5, 2, 3].
Figure 8.10.11 shows the swaps that the buildHeap method makes as it moves the nodes in an initial tree of [9, 6, 5, 2, 3] into their proper positions. Although we start out in the middle of the tree and work our way back toward the root, the percDown method ensures that the largest child is always moved down the tree. Because the heap is a complete binary tree, any nodes past the halfway point will be leaves and therefore have no children. Notice that when i=1, we are percolating down from the root of the tree, so this may require multiple swaps. As you can see in the rightmost two trees of Figure 8.10.11, first the 9 is moved out of the root position, but after 9 is moved down one level in the tree, percDown ensures that we check the next set of children farther down in the tree to ensure that it is pushed as low as it can go. In this case it results in a second swap with 3. Now that 9 has been moved to the lowest level of the tree, no further swapping can be done. It is useful to compare the vector representation of this series of swaps as shown in Figure 8.10.11 with the tree representation.
i = 2  [0, 9, 5, 6, 2, 3]
i = 1  [0, 9, 2, 6, 5, 3]
i = 0  [0, 2, 3, 6, 5, 9]
The complete binary heap implementation can be seen in Task 8.10.1.a.

Exploration 8.10.1. Complete Heap Implementation.

(a) C++ Implementation.
(b) Python Implementation.
The assertion that we can build the heap in \(O(n)\) may seem a bit mysterious at first, and a proof is beyond the scope of this book. However, the key to understanding that you can build the heap in \(O(n)\) is to remember that the \(\log{n}\) factor is derived from the height of the tree. For most of the work in buildHeap, the tree is shorter than \(\log{n}\text{.}\)
Using the fact that you can build a heap from a vector in \(O(n)\) time, you will construct a sorting algorithm that uses a heap and sorts a vector in \(O(n\log{n}))\) as an exercise at the end of this chapter.

Reading Questions Reading Question

1.
What is the vector used in the binary tree in the first image of Figure 8.10.7? Exclude any whitespace.
You have attempted of activities on this page.
PrevTopNext