Thursday, February 2, 2023
Learning Code
  • Home
  • JavaScript
  • Java
  • Python
  • Swift
  • C++
  • C#
No Result
View All Result
  • Home
  • JavaScript
  • Java
  • Python
  • Swift
  • C++
  • C#
No Result
View All Result
Learning Code
No Result
View All Result
Home C++

How to Heapify a Heap Tree in C++: A Tutorial With Examples

learningcode_x1mckf by learningcode_x1mckf
September 4, 2022
in C++
0
How to Heapify a Heap Tree in C++: A Tutorial With Examples
74
SHARES
1.2k
VIEWS
Share on FacebookShare on Twitter


You might also like

C can be memory-safe – Security Boulevard

C++ Lambda Expressions Explained | Built In

C++ creator Bjarne Stroustrup defends its safety

In pc science, a heap is a sort of tree-shaped knowledge construction that has the particular property of being an almost-completely binary construction satisfying the heap property. A heap could be both a min heap or a max heap. A max heap is a knowledge construction by which every youngster node is lower than or equal to its dad or mum node. A min heap is an analogous sort of knowledge construction the place every youngster node is bigger than or equal to its dad or mum node. Thus, heapifying a heap tree means reordering the kid nodes in order that they conform to both min heap or max heap guidelines.

When min heap or max heap constraints are positioned on tree knowledge buildings, we find yourself with timber of comparatively brief size. As a result of heaps are shorter, traversing from the minimal to the utmost worth takes much less time, which makes the method of looking for values throughout the tree a lot sooner.

Learn how to Heapify a Heap Tree in C++

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.

 

What Are Min Heaps and Max Heaps?

Let’s contemplate the next max heap.

An image of a heap data structure, which is hierarchical and branching, like a tree, and is also called a dendrogram. This one is a max heap.
Picture: Sadrach Pierre / Constructed In

The property of the max heap is that the foundation node has the utmost worth. Additional, the worth of every node is lower than or equal to its dad or mum node. On the prime of the tree we have now the foundation node with a price of 90, which is the most important 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 under.

An image of a heap data structure, which is hierarchical and branching, like a tree, and is also called a dendrogram. This one is a min heap.
Picture: Sadrach Pierre / Constructed In

If we take a look at the worth on the root in comparison with the values at every node under the foundation, we see that 12 is the smallest worth within the tree. On the stage under, we have now 20 and 29 that are each higher than 12, and so forth.

 

Learn how to Heapify a Heap Tree in C++

The duty of heapifying a heap tree is the method of reordering the weather of a tree such that it has the properties of a min or max heap.

 

Max Heapify

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 dad or mum, satisfying a max heap:

An unsorted heap tree is on the left of this diagram, and an arrow points to the right side, which has been heap sorted to max heap.
Picture: Sadrach Pierre / Constructed In

 

Min Heapify

Min heapify is the method of recording the values at every node such that the kid is bigger than or equal to the dad or mum node, satisfying a min heap:

An unsorted heap tree is on the left side of this image, and an arrow points to a min heap sorted heap tree on the right.
Picture: Sadrach Pierre / Constructed In

Heap knowledge buildings may also be used for locating and retaining observe 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 will result in a decrease common ready time for all clients. Heaps are additionally utilized in graph algorithms corresponding to Djiktra’s algorithm, which is used to seek out the shortest path between two nodes in an array. This can be utilized for infrastructure planning duties corresponding to establishing a street community, electrical energy line, or oil pipeline. 

Video: Tech Dose / YouTube | Heapify Algorithm, Max Heapify, Min Heapify

 

Defining a Heapify Perform

To elucidate how greatest to heapify your knowledge, 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, that means that every dad or mum node has exactly two youngster nodes:

A binary heap tree, which is also a min heap.

We will outline a heapify perform 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 locate the final node that isn’t a leaf. A leaf is a node that doesn’t have any youngsters. We see that 11, 13, 19, 22, 24, and 29 are all leaves since they don’t level to any youngsters:

The same binary min heap, but with two circles identifying the leaf nodes, the nodes that don’t point to any children.
Picture: Sadrach Pierre / Constructed In

Additional, studying the nodes in every tree stage (that’s, a stage above the leaf nodes) from left to proper we see that the final non-leaf node is 17. That is additionally the dad or mum of the final node:

The same min heap tree again, this time the last non-leaf node is circled. It has the value of 17.
Picture: Sadrach Pierre / Constructed In

If we wish 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] moving 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 youngster node to its dad or mum. For max-heapify, if the kid node is bigger than its dad or mum, swap the values. For instance, we begin the heapify operation by swapping 17 with the worth of its furthest proper youngster, 29, because the youngster is bigger than the dad or mum:

Showing the first step of the heapify, or the heap sort, starting with the lowest-level child nodes and moving from right to left, swapping the higher-value nodes into higher positions on the tree.
Picture: Sadrach Pierre / Constructed In

We then transfer to the following node, going from proper to left, 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 dad or mum node and is lower than 22, it doesn’t fulfill the heap property, so we swap:

The heapify process is repeated on the heap tree, node by node, moving the larger numbers higher up the tree.
Picture: Sadrach Pierre / Constructed In

We then transfer to the following node. Since 19 is lower than 22, it satisfies the max heap precept so we transfer on to the following stage. We begin at 13 and examine it to its dad or mum. It doesn’t fulfill the heap property so we swap 8 and 13:

The heapify process is repeated on the heap tree, node by node, moving the larger numbers higher up the tree.
Picture: Sadrach Pierre / Constructed In

The following node values to swap are 5 with 29, then 5 with 24:

The heapify process is repeated on the heap tree, node by node, moving the larger numbers higher up the tree.
Picture: Sadrach Pierre / Constructed In

Then we swap 3 and 29, 3 and 24, after which 3 and 17, in order that 3 works its manner down the tree to develop into a leaf node and 29 is the foundation:

The heapify process is repeated on the heap tree, node by node, moving the larger numbers higher up the tree.
Picture: Sadrach Pierre / Constructed In

Hug Extra Tree (-Formed Knowledge Constructions) on Constructed In’s Knowledgeable Contributors CommunityHow to Get Started With Regression Trees

 

Indexing a Heap

Earlier than we will transfer on to write down code to heapify our array in C++, we have to rapidly determine the index.

We will discover the index, which is just the place within the tree, of the final non-leaf node by taking the ground of half the variety of nodes minus one, the place the ground is the best integer lower than or equal to the enter. For instance, the ground of two.2 is 2.0. Let’s calculate the index of the final non-leaf node:

index of final non-leaf node = flooring of (variety of nodes)/2 – 1.

In our earlier 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, which might be 5.5 -1 = 4.5. The ground of 4.5 = 4.0.

So the index of the final non-leaf node is 4, which has the worth of 17. As a reminder, we begin indexing nodes with 0. For instance, the primary factor has an index of 0, the second has an index of 1, the fifth factor has an index of 4, and so forth.  

 

Writing Code for Heapifying in C++

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 perform known as heapify that returns void:

void heapify()



The perform 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 perform. Let’s initialize a variable known as largest_value. Let’s additionally initialize variables for the left and proper youngsters. For the left youngster, the index is 2*subtree_root_index +1 and the proper youngster 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 youngster is bigger than the foundation. If the left youngster is bigger than the foundation, we redefine the largest_value because the left youngster. Inside this logic we additionally have to be sure that the index of the left youngster is lower than the scale of the array:

void heapify(int array_in[], int array_size, int subtree_root_index)



    ...//code truncated for readability


    if (left < array_size && array_in[left] > array_in[largest_value])

    largest_value = left; 




Subsequent we have to add logic that checks if the proper youngster is bigger than the foundation. Just like the earlier test, if the proper youngster is bigger than the foundation, we redefine the largest_value as the proper youngster. We additionally have to be sure that the index of the proper youngster is lower than array_size:

void heapify(int array_in[], int array_size, int subtree_root_index)



    ...//code truncated for readability


    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; 




Lastly, we have to test if the most important worth is the same as the worth on the root. If it’s not  we swap the values on the root with the most important worth:

void heapify(int array_in[], int array_size, int subtree_root_index)



    ...//code truncated for readability

    if (largest_value != subtree_root_index )



    swap(array_in[subtree_root_index], array_in[largest_value];



And at last we recursively name the heap perform on the subtree below the situation largest_value just isn’t equal to subtree_root_index:

void heapify(int array_in[], int array_size, int subtree_root_index)



    ...//code truncated for readability

    if (largest_value != subtree_root_index )



    swap(array_in[subtree_root_index], array_in[largest_value]

    heapify(array_in, array_size, subtree_root_index);



The total perform 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);




 

Utilizing Our Heapify Perform to Outline a Heap Constructor

Now that we’re accomplished writing our heapify perform, we will write one other perform that enables us to assemble a heap given an enter array. This perform will take an array and its measurement as inputs, and inside a for loop name the heapify perform on the array ranging from the last-node leaf node. We are going to name the perform assemble Heap:

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 will loop in reverse order ranging from the final leaf node, iteratively decreasing the index by 1, and name on the heapify perform 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 perform 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 will outline our fundamental perform which is able to function the motive force code for executing our heapify, construct_heap and print_heap features. Let’s outline the array we have been working with earlier, array_in = [3, 5, 8, 10, 17, 11, 13, 19, 22, 24, 29], which has the corresponding tree illustration:

An earlier image is repeated, referring back to the min heap tree before it was put through the max heapify process.
Picture: Constructed In
int fundamental()

  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 should always get the next output:

Printing values at every node in heap
29
24
13
22
17
11
9
19
10
5
3

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 final product of the heapify process, with the original heap on the right (including the array index on top of the tree) and the max heap on the right (also with the array on top of the tree).
Picture: Sadrach Pierre / Constructed In

The code used on this put up is out there on GitHub. 

 

Why and When Heapifying Is a Good Concept

In abstract, heapifying a tree is essential because it permits us to learn from the favorable properties of the heap knowledge construction. Heap knowledge buildings can considerably velocity up these algorithmic duties. Heaps even have functions corresponding to min/max looking out, order statististics, and discovering the shortest paths. An order statistic corresponds to the Kth smallest (or largest) worth in a set of things. This has functions in duties corresponding to rapidly discovering the median in an array. It’s usually helpful any time it’s essential repeatedly choose largest or smallest values from a set of things which is the case with precedence queues and order statistics. 

Be taught Extra C++ on Constructed In’s Knowledgeable Contributors CommunityHow to Write Clean Exception Handling Code in C++



Source link

Share30Tweet19
learningcode_x1mckf

learningcode_x1mckf

Recommended For You

C can be memory-safe – Security Boulevard

by learningcode_x1mckf
February 1, 2023
0
C can be memory-safe – Security Boulevard

The concept of memory-safe languages is within the information currently. C/C++ is known for being the world’s system language (that runs most issues) but in addition notorious for being...

Read more

C++ Lambda Expressions Explained | Built In

by learningcode_x1mckf
February 1, 2023
0
C++ Lambda Expressions Explained | Built In

One of many new options launched in trendy C++ ranging from C++ 11 is the lambda expression.It's a handy solution to outline an nameless operate object or functor....

Read more

C++ creator Bjarne Stroustrup defends its safety

by learningcode_x1mckf
January 31, 2023
0
C++ creator Bjarne Stroustrup defends its safety

The creator of C++, Bjarne Stroustrup, is defending the venerable programming language after the US Nationwide Safety Company (NSA) just lately really helpful towards utilizing it. NSA advises...

Read more

Solid Sands and Rapita target hard to do C++ code analysis … – eeNews Europe

by learningcode_x1mckf
January 30, 2023
0
Solid Sands and Rapita target hard to do C++ code analysis … – eeNews Europe

Solid Sands and Rapita target hard to do C++ code analysis ...  eeNews Europe Source link

Read more

Bjarne Stroustrup Defends C++ As Safe

by learningcode_x1mckf
January 29, 2023
0

It is not stunning to search out the creator of a language defending the language they created and so it's with the newest paper from Bjarne Stroustrup. Is...

Read more
Next Post
How to use inner shadows to simulate depth with SwiftUI and Core Motion – Hacking with Swift

How to use inner shadows to simulate depth with SwiftUI and Core Motion – Hacking with Swift

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Related News

Building a URL Shortener With FastAPI and Python – Real Python

Building a URL Shortener With FastAPI and Python – Real Python

September 4, 2022
Verifiy all versions of the C standard library specification

Verifiy all versions of the C standard library specification

December 2, 2022
Memory layout in Swift – The.Swift.Dev.

Memory layout in Swift – The.Swift.Dev.

September 16, 2022

Browse by Category

  • C#
  • C++
  • Java
  • JavaScript
  • Python
  • Swift

RECENT POSTS

  • Java :Full Stack Developer – Western Cape saon_careerjunctionza_state
  • Pay What You Want for this Learn to Code JavaScript Certification Bundle
  • UPB Java Jam brings coffeehouse vibes to Taylor Down Under | Culture

CATEGORIES

  • C#
  • C++
  • Java
  • JavaScript
  • Python
  • Swift

© 2022 Copyright Learning Code

No Result
View All Result
  • Home
  • JavaScript
  • Java
  • Python
  • Swift
  • C++
  • C#

© 2022 Copyright Learning Code

Are you sure want to unlock this post?
Unlock left : 0
Are you sure want to cancel subscription?