Shulou(Shulou.com)06/03 Report--

Web development of binary heap need to pay attention to what things, I believe that many inexperienced people do not know what to do, so this paper summarizes the causes of the problem and solutions, through this article I hope you can solve this problem.

1. What is a binary heap?

Needless to say, the trees introduced in this chapter are all binary trees. So what is "heap"?

In our daily life, we usually say "pile things" or "pile things". The "pile" here usually refers to a lot of things placed on top of each other.

A bunch of stuff.

When we pile things, we must have an experience, that is, in order to make this pile more stable, we will put heavier and large things at the bottom and lighter and small things on top.

This experience is also applicable in the data structure, the binary tree. It's just that "heavy" and "big" are judged by the value of the node, and are compared between the parent node and the child node.

For example, a node with a large value is used as a child node, and a node with a small value is used as a parent node.

As an example, let's take a look at the following ordinary binary tree, which is also a complete binary tree:

Take a look at the following binary pile:

Minimum heap

The characteristics of this binary reactor are:

It is a complete binary tree. In fact, the binary heap is transformed from the complete binary tree in the figure above.

The value of any parent node is less than or equal to that of the left child and the right child.

Each branch is sorted in ascending order from the root node (for example, branch 1-2-3-4).

Such a binary heap is called the minimum heap, and its top, the root node A, is the minimum of the whole tree.

Corresponding to the smallest heap is the maximum heap:

The largest heap is a complete binary tree.

The value of any parent node is greater than or equal to the value of the left child and the right child.

Each branch is sorted in descending order from the root node.

The top of the largest heap is the maximum value of the whole tree.

We convert the ordinary binary tree in the above image to the maximum heap, as shown in the following figure:

Maximum heap

two。 Operation of binary heap 2.1. Construct binary reactor

If I give you a complete binary tree, how to adjust the nodes to construct a binary heap? Here is a completely disordered binary tree:

Now we want to construct a minimum heap, first find all the non-leaf nodes (green marks) in this complete binary tree:

What we need to do is to make the smallest pile of "sinking" adjustment for each non-leaf node.

What is the "sinking" adjustment of the smallest pile?

For a non-leaf node, if the node is larger than the smallest of its child nodes, the positions of the two nodes are exchanged, otherwise there is no need to exchange. On the graph, it shows a level of "sinking" of non-leaf nodes (that is, large-value nodes). The motion is relative, and the "sinking" of the large node is equivalent to the "floating" of the small node.

It is important to note that sometimes it is not enough to sink once, we need to sink several times to make sure that the node sinks to the end (that is, it is no longer larger than its child).

All non-leaf nodes, starting from the last one, make multiple sinking adjustments of the minimum heap from right to left and from bottom to top to form a minimum heap.

For example, for a non-leaf node with a value of 4, after sinking to level 3, it is still larger than its child, which does not count as "sinking to the end" and needs to continue to sink to level 4. At this point, on the branch 2-4-3-1, the "large value" node 4 is considered to have sunk to the bottom.

The following is a step-by-step explanation:

1. For non-leaf node 7, it is less than its child node 10 and does not need to "sink"

two。 For the non-leaf node 3, it is larger than the larger node 1 of its child node, and node 3 should "sink" and exchange with node 1. Obviously, Node 3 sank to the bottom.

3. For non-leaf node 6, it is larger than the smaller node 5 of its child node, and node 6 should "sink" and exchange positions with node 5. Obviously, node 6 sank to the bottom.

4. For the non-leaf node 4, it is larger than the smallest node 1 of its child node, and node 4 should "sink" and exchange positions with node 1. Obviously, node 4 did not sink to the end.

5. It is still for node 4, which is larger than the smallest node 3 of its child nodes. Node 4 should "sink" and exchange positions with node 3. At this point, node 4 is considered to be at the bottom.

6. For the non-leaf node 2, it is larger than the smallest node 1 of its child node, and node 2 should "sink" and exchange positions with node 1. Obviously, Node 2 has sunk to the bottom.

At this point, we have transformed an unordered complete binary tree into a minimum binary heap, and you can check that all nodes in the smallest heap satisfy that the parent's value is less than the child's value. Moreover, the five branches are all orderly.

The steps for constructing the maximum heap are similar, but the sinking adjustment of the maximum heap is: if a node is smaller than the largest of its child nodes, the positions of the two are exchanged, which is shown as a level of "sinking" of non-leaf nodes (that is, small nodes) on the graph. Through several sinking adjustments, the node is no longer smaller than its child.

The following figure adjusts an unordered complete binary tree to the maximum heap:

2.2. Insert node

The binary heap is a complete binary tree. To insert a node into it, insert it into the next position of the last node of the complete binary tree.

For example, insert node 11 into the largest heap below, to the next location of the last node 4. When a new node is inserted into the maximum heap at 11:00, it is no longer the largest heap because node 11 destroys the structure of the original heap. Therefore, we should think of it as a new complete binary tree, and then adjust the new complete binary tree to construct the maximum heap again. (see above for the adjustment process)

Insertion process

2.3. Delete a node

The delete operation, in contrast to the insert operation, deletes the element in the first position, that is, the top of the heap.

Let's take the deletion of the top 11 of the largest heap in the image above as an example.

When the stack top 11 is deleted, the original structure of the binary reactor is destroyed, and it is not even a binary tree (turned into two):

In order to maintain the shape of the complete binary tree, we add the last node 7 to the root node to replace the deleted root node 11. In this way, we get a new complete binary tree (not a binary heap), and then we can construct the maximum heap based on the new complete binary tree.

Delete process

3. Storage structure of binary heap

The storage structure of binary heap is sequential storage, because binary heap is a complete binary tree. In the article [Storage of binary Tree], we said that complete binary tree is suitable to be implemented by sequential storage structure.

The following figure is the largest heap, and the red box is the number of nodes, corresponding to the array subscript one by one.

Sequential storage of binary heap

The chain storage structure can clearly and vividly show us the relationship between the parents' nodes and the left and right children in the binary heap. But there is no pointer in the array, only the array subscript, how to express the relationship between parents and children?

In fact, for a complete binary tree, an array subscript is sufficient!

Now suppose that the array index of the parent node in the binary heap is parent_index, the left child's array index is left_child_index, and the right child's array index is right_child_index, then the relationship between them is as follows:

(1) left_child_index = 2 × parent_index + 1

(2) right_child_index = 2 × parent_index + 2

(3) parent_index = (left_child_index-1) / 2

(4) parent_index = (right_child_index-2) / 2

(5) right_child_index = left_child_index + 1

For example, if the subscript of node 3 is 3, the subscript of left child 2 is 2 × 3 + 1 = 7 and the subscript of right child 1 is 2 × 3 + 2 = 8.

The subscript of node 3 is 3, as a left child, the parent subscript is (3-1) / 2 = 1; the subscript of node 7 is 4, and as a right child, the parent subscript is (4-2) / 2 = 1.

Suppose the array subscript of a node is child_index. You don't know whether the node is a left child or a right child. Ask for the subscript of its parents.

(6) parent_index = (child_index-1) / 2

For example, if you do not know whether node 5 (subscript 5) and node 6 (subscript 6) are left or right children, then the parent subscript of node 5 and node 6 is (5-1) / 2 = 2 and (6-1) / 2 = 2, respectively. (note the integer operation in the programming language, so the result is not a decimal)

Here, we use structures to implement the binary heap:

# define MAXSIZE 20 / / the maximum storage space of the array typedef struct {int array [MAXSIZE]; / / Storage array int length; / / current heap length (number of nodes)} BinaryHeap

Before doing the actual operation, you need to initialize the binary heap, that is, assign values to the array and heap length:

/ * * @ description: initialize the first address of binary heap * @ param {BinaryHeap} * heap binary heap * @ param {int} * array array The array is an unordered complete binary tree * @ param {int} arr_length array length * @ return {*} No * / void init_heap (BinaryHeap * heap, int * array, int arr_length) {/ / array copied to heap memcpy (heap- > array, array, arr_length * sizeof (int)) / / set heap length heap- > length = arr_length;} 4. The concrete realization of binary reactor 4.1. Adjustment and construction

Here we take the construction of a minimum heap as an example.

To construct a minimum heap, you have to adjust all non-leaf nodes. The adjustment is based on the comparison of non-leaf nodes and the size of their children.

We agree that parent is a non-leaf node and parent_index is its subscript. Child is the younger of his children, and child_index is the subscript.

Child starts to mark the left child by default, then the right child's subscript is child_index + 1. When the left child is less than or equal to the right child, the child does not need to be changed; when the left child is larger than the right child, you have to update the child_index to make the child identify the right child.

The following example shows how to implement the code with a non-leaf node with a value of 4 in the following figure.

First compare the left and right parent children, the left child is smaller, then child is the left child, there is no need to update the child_index.

Parent and child are in place, and it is found that parent is greater than child, and places can be exchanged. Before swapping, save the value of parent, that is, parent_value = 4:

Swap position: first assign the value of child to parent to achieve the floating effect of value 1:

Then update parent_index and child_index, both of which go down one level:

Then assign the previously saved value to the current parent to achieve the sinking effect of a value of 4:

The adjustment is complete at once, but it is not over for the value 4, because the value 4 has not sunk to the bottom.

Compare the left and right children of parent at this time, and find that the right child is smaller, then child is the right subtree, and you need to update the child_index to make child identify the right child:

Now you can switch places and assign the value of child to parent to reach the float of value 3:

Then, update the values of parent_index and child_index, which go down one level:

Assign value to parent to reach a sinking value of 4:

At this point, the child_index has exceeded the length of the binary heap, that is, the value of 4 has reached the bottom.

The adjustment code is as follows:

/ * * @ description: adjust the sinking of a non-leaf node to the end * @ param {BinaryHeap} * heap binary heap (disordered) * @ param {int} parent_index a non-leaf node * @ return {*} none * / void adjust_for_min_heap (BinaryHeap * heap, int parent_index) {/ / value saves the value of the non-leaf node int value = heap- > Array [parent _ index] / / child_index marks left child int child_index = parent_index * 2 + 1; / / the subscript of the last node int last_child_index = heap- > length-1 / / the parent node parent has at least one child while (child_index array [child _ index] > heap- > Array [child _ index + 1]) {/ / then child_index marks the right child child_index = child_index + 1 }} / / if the parent's value is greater than the child's value if (value > heap- > Array [child _ index]) {heap- > Array [parent _ index] = heap- > Array [child _ index]; / / small node floats parent_index = child_index; / / updates parent subscript child_index = parent_index * 2 + 1 / / Update child subscript} else {/ / do nothing, jump out of the loop break;} / / sink big node heap- > array [parent _ index] = value;}}

The construction code is as follows:

/ * * @ description: construct the minimum heap * @ param {BinaryHeap} * heap binary heap (disordered) * @ return {*} none * / void create_min_heap (BinaryHeap * heap) {/ / each non-leaf node adjusts for (int I = (heap- > length-2) / 2; I > = 0; I color -) {adjust_for_min_heap (heap, I);}} 4.2. Insert node

Simply insert the new node into the next location of the last node of the binary heap and reconstruct the binary heap.

Take the minimum heap as an example, the code is as follows:

/ * * @ description: insert an element into the minimum heap * @ param {BinaryHeap} * heap minimum heap pointer * @ param {int} elem new element * @ return {*} none * / void insert_into_min_heap (BinaryHeap * heap, int elem) {if (heap- > length = MAXSIZE) {printf ("binary heap is full and cannot be inserted. \ n "); return;} heap- > Array [heap-> length] = elem; / / insert heap- > length++; / / update length create_min_heap (heap); / / Reconstruction} 4.3. Delete a node

Move (assign) the last node to the top of the heap and reconstruct the binary heap.

Take the minimum heap as an example, the code is as follows:

/ * * @ description: delete the top of the minimum heap * @ param {BinaryHeap} * heap minimum heap pointer * @ param {int} * elem save variable pointer * @ return {*} none * / void delete_from_min_heap (BinaryHeap * heap, int * elem) {if (heap- > length = = 0) {printf ("binary heap empty, no elements to delete. \ n "); return;} * elem = heap- > array [0]; heap- > array [0] = heap- > Array [heap-> length- 1]; / / move to the top of the heap heap- > length--; / / update length create_min_heap (heap); / / restructure} 5. Summary

The essence of constructing the largest heap is to float the "big" node of each sub-tree as a parent and the "small" node to sink as a child.

The essence of constructing the smallest heap is to float the "small" node of each subtree as a parent, and the "big" node to sink as a child.

The essence of the insertion node is to insert the new node to the end of the binary heap, destroy the structure of the original binary heap, and then adjust the newly obtained complete binary tree to reconstruct the binary heap.

The essence of deleting a node is to delete the heap top, destroy the structure of the original complete binary tree, and then use the last node to reconstruct the complete binary tree, and then adjust the new complete binary tree to reconstruct the binary heap.

It can be summed up in four words-- break and stand behind.

As for the code implementation, the key lies in the adjustment of the node, figure this out, and the rest is simple.

These are the principles and related operations of the binary reactor.

After reading the above, have you mastered what the binary heap needs to pay attention to in web development? If you want to learn more skills or want to know more about it, you are welcome to follow the industry information channel, thank you for reading!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.