A newbie’s information to constructing a heap in C++
In laptop science, a heap is a sort of tree-shaped information construction that has the particular property of being an almost-completely binary construction satisfying the heap property. This property corresponds to max heaps and min heaps. A max heap is an information construction the place every baby node is lower than or equal to its mother or father node. A min heap is an analogous sort of knowledge construction the place every baby node is larger than or equal to its mother or father node. When these constraints are positioned on tree information buildings, we find yourself with bushes of comparatively brief size. This makes the method of trying to find values throughout the tree a lot quicker. Let’s contemplate the next max heap:
On the prime of the tree we’ve the foundation node with a worth of 90. The property of the max heap is that the foundation node has the utmost values. Additional, the worth of every node is lower than or equal to its mother or father node. We see that 90 is the biggest worth within the tree. Additional, on the second stage we see the values 79 and 72, that are lower than 90, after which 30 and 65 that are lower than 79, and so forth.
Conversely, check out the instance of the min heap beneath:
If we take a look at the worth on the root in comparison with the values at every node beneath the foundation, we see that 12 is the smallest worth within the tree. On the stage beneath, we’ve 20 and 29 that are each larger than 12, and so forth.
The duty of heapifying a tree is the method of reordering the weather of a tree such that it has the properties of a min or max heap. Particularly, max-heapify is the method of taking an array that’s represented as a binary tree and recording the values at every node such that the kid nodes are both lower than or equal to the mother or father, satisfying a max heap:
Min-heapify is the method of recording the values at every node such that the kid is larger than or equal to the mother or father node, satisfying a min heap:
Heapifying is beneficial due to the favorable properties of the heap information construction. Making a tree fulfill the heap properties can pace up many algorithmic duties which might be crucial in software program engineering. For instance, heap information buildings can be utilized for locating order statistics. An order statistic corresponds to the Kth smallest (or largest) worth in a group of things. This has functions in duties akin to shortly discovering the median in an array.
Heap information buildings may also be used for locating and retaining monitor of the minimal/most worth in an array. This may be helpful for scheduling duties in a precedence queue for purchasers, the place clients with points that take the shortest period of time are prioritized. This could result in a decrease common ready time for all clients. Heaps are additionally utilized in graph algorithms akin to Djiktra’s algorithm which is used to seek out the shortest path. This can be utilized for infrastructure planning duties akin to establishing a street community, electrical energy line or oil pipeline.
Understanding how you can implement a heap information construction is a crucial ability set for each information scientist. Additional, understanding the fundamental functions of a heap information construction could make it a strong instrument for a lot of algorithmic duties throughout a wide range of software program engineering functions.
Heapify a Binary tree
Heapifying is the method of changing a binary tree right into a heap information construction. To see how that is completed, let’s contemplate the next array:
array_in = [3, 5, 8, 10, 17, 11, 13, 19, 22, 24, 29]
This array has the corresponding full binary tree:
We will outline a heapify operate that takes the array as enter and converts it right into a max or min-heap. Let’s contemplate changing this binary tree right into a max heap. The very first thing we have to do is use the final node that isn’t a leaf. A leaf is a node that doesn’t have any kids. We see that 11, 13, 19, 22, 24, and 29 are all leaves since they don’t level to any kids:
Additional, studying the nodes in every tree stage from left to proper we see that the final non-leaf node is 17. That is additionally the mother or father of the final node:
We will discover the index of the final non-leaf node by taking the ground of half the variety of nodes -1:
index of final non-leaf node = flooring of (variety of nodes)/2–1.
In our instance there are 11 nodes so the index of the final non-leaf node is:
index of final non-leaf node = flooring of (11)/2–1 = 5.5 -1 = flooring of 4.5 = 4.0.
So the index of the final non-leaf node is 4, which has the worth of 17 (bear in mind we begin with an index worth of 0).
We need to construct a max-heap from our binary tree. We will do that by heapifying the nodes as much as the final non-leaf node [3,5,8,10,17] entering into reverse order. We apply the heapify operation in reverse stage order that means ranging from proper to left at every stage we examine every baby node to its mother or father. For max-heapify, if the kid node is larger than its mother or father, swap the values. For instance, we begin the heapify operation by swapping 17 with the worth of its furthest proper baby, 29, for the reason that baby is larger than the mother or father:
We then transfer to the following node, going from left to proper, and examine 24 with 29. This satisfies the max-heap property so we then transfer on to 22, which we examine to 10. Since 10 is at a mother or father node and is lower than 22, it doesn’t fulfill the heap property so we swap:
We then transfer to the following node. Since 19 is lower than 22, it satisfies the max- heap so we transfer on to the following stage. We begin at 13 and examine it to its mother or father. It doesn’t fulfill the heap property so we swap 8 and 13:
The subsequent node values to swap are 5 and 29, then 5 and 24:
Then we swap 3 and 29, 3 and 24, after which 3 and 17:
Let’s write some c++ code that implements this heapify logic. Let’s create a .cpp file known as heapify_code.cpp. In terminal sort:
vi heapify_code.cpp
Let’s begin by together with <iostream> which permits us to write down to the usual enter/output streams.
#embody <iostream>
Let’s additionally outline a operate known as heapify that returns void:
void heapify(){}
The operate will take an integer array enter. Let’s name the integer array array_in. It should additionally take an integer, subtree_root_index, for the index of subtree root . It should additionally take an integer, array_size, for the scale of the array:
void heapify(int array_in[], int index, int array_size){}
Subsequent, we have to outline a number of variables throughout the scope of our operate. Let’s initialize a variable known as largest_value. Let’s additionally initialize variables for the left and proper kids. For the left baby, the index is 2*subtree_root_index +1 and the suitable baby is 2*subtree_root_index +2.
void heapify(int array_in[], int array_size, int subtree_root_index){int largest_value = subtree_root_index;int left = 2*subtree_root_index + 1;int proper = 2*subtree_root_index + 2;}
Subsequent let’s add logic that checks if the left baby is bigger than the foundation. If the left baby is larger than the foundation, we redefine the largest_value because the left baby. Inside this logic we additionally must guarantee that the index of the left baby is lower than the scale of the array:
void heapify(int array_in[], int array_size, int subtree_root_index){
…//code truncated for readabilityif (left < array_size && array_in[left] > array_in[largest_value])
{
largest_value = left;
}}
Subsequent we have to =add logic that checks if the suitable baby is bigger than the foundation. Just like the earlier examine, if the suitable baby is larger than the foundation, we redefine the largest_value as the suitable baby. We additionally must guarantee that the index of the suitable baby is lower than array_size:
void heapify(int array_in[], int array_size, int subtree_root_index){
…//code truncated for readabilityif (left < array_size && array_in[left] > array_in[largest_value])
{
largest_value = left;
}if (proper < array_size && array_in[right] > array_in[largest_value]){
largest_value = proper;
}}
Lastly, we have to examine if the biggest worth is the same as the worth on the root. If it’s not we swap the values on the root with the biggest worth:
void heapify(int array_in[], int array_size, int subtree_root_index){
…//code truncated for readabilityif (largest_value != subtree_root_index )
{
swap(array_in[subtree_root_index], array_in[largest_value];
}}
And at last we recursively name the heap operate on the subtree underneath the situation largest_value just isn’t equal subtree_root_index:
void heapify(int array_in[], int array_size, int subtree_root_index){…//code truncated for readabilityif (largest_value != subtree_root_index )
{
swap(array_in[subtree_root_index], array_in[largest_value]
heapify(array_in, array_size, subtree_root_index);
}}
The complete operate is as follows:
void heapify(int array_in[], int array_size, int subtree_root_index){
int largest_value = subtree_root_index;
int left = 2*subtree_root_index + 1;
int proper = 2*subtree_root_index + 2;if (left < array_size && array_in[left] > array_in[largest_value])
{
largest_value = left;
}if (proper < array_size && array_in[right] > array_in[largest_value]){
largest_value = proper;
}if (largest_value != subtree_root_index )
{
swap(array_in[subtree_root_index], array_in[largest_value]
heapify(array_in, array_size, largest_value);
}}
Construct Heap
Now that we’re completed writing our heapify operate, we are able to write one other operate that enables us to assemble a heap given an enter array. This operate will take an array and its measurement as inputs, and inside a for loop name the heapify operate on the array ranging from the last-node leaf node. We’ll name the operate constructHeap:
void construct_heap(int array_in[], int array_size){}
Let’s outline a variable known as last_non_leaf_node which is the array_size/2 -1:
void construct_heap(int array_in[], int array_size)
{
int last_non_leaf_node = (array_size/2) -1;
}
Subsequent we are able to loop in reverse order ranging from the final leaf node, iteratively lowering the index by 1, and name the heapify operate with every worth for the index:
void construct_heap(int array_in[], int array_size){int last_non_leaf_node = (array_size/2) -1;for (int subtree_root_index = last_non_leaf_node; subtree_root_index >=0; subtree_root_index-=1)
{
heapify(array_in, array_size, subtree_root_index);
}}
Subsequent let’s outline a print operate that may enable use to print out the values in our heap:
void print_heap(int array_in[], int array_size){cout << "Printing values at every node in heap" << endl;for (int index = 0; index < array_size; index+=1)
{
cout<< array_in[index] << endl;
}}
Now we are able to outline our important operate which can function the driving force code for executing our heapify, construct_heap and print_heap features. Let’s outline the array we work working with earlier, array_in = [3, 5, 8, 10, 17, 11, 13, 19, 22, 24, 29], which has the corresponding tree illustration:
int important(){int array_in[] = { 3, 5, 8, 10, 17, 11, 13, 19, 22, 24, 29};
int array_size = sizeof(array_in) / sizeof(array_in[0]);
construct_heap(array_in, array_size);
print_heap(array_in, array_size);}
Let’s compile our script:
g++ heapify_code.cpp
And run our compiled script:
./a.out
And we must always get the next output:
This has the array illustration heap = [29, 24, 13, 22, 17, 11, 8, 19, 10, 5, 3] and the next transformation we carried out is as follows:
The code used on this submit is offered on GitHub.
Conclusions
Heapifying a tree is essential because it permits us to profit from the favorable properties of the heap information construction. A heap is a vital information construction that has functions akin to min/max looking out, order statistics and discovering the shortest paths. Heap information buildings can considerably pace up these algorithmic duties. It’s usually helpful any time it’s essential repeatedly choose largest or smallest values from a group of things which is the case with precedence queues and order statistics.
This submit was initially revealed on the BuiltIn weblog. The unique piece may be discovered right here.
