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

This article introduces the relevant knowledge of "what is a binary heap". In the operation of actual cases, many people will encounter such a dilemma. Then let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Before officially starting the learning heap, be sure to review in your brain what a complete binary tree is, because it is closely related to the heap!

If the degree of each node in a binary tree except the leaf node is 2, then the binary tree is called a full binary tree.

If the last layer of nodes in the binary tree is a full binary tree, and the nodes of the last layer are distributed from left to right in turn, then the binary tree is called a complete binary tree.

So a full binary tree must be a complete binary tree. If you don't know about a complete binary tree, you can read this article about the past life and this life of Tree.

For any complete binary tree, if the nodes are labeled from left to right (as shown in the figure above), for any node I, the complete binary tree (binary heap) satisfies the following conclusions:

When I > 1, the father node is the node. For example, the label of node 45 is 4, the number of parent node 15 is 2, and the number of 2, 4, and 2 is 2.

If 2Xi > n (the number of total nodes), then there must be no left child (the leaf node); otherwise the left child is the node 2Xi. For example, the label of node 15 is 2, and the left child node is 4.

If 2X+1 > n, there must be no right child in node I; otherwise, the right child is node 2Xi+1.

Heap is a kind of special data structure based on complete binary tree. Heaps are usually divided into two types:

Big top heap (Max Heap): in a big top heap, the value of the root node must be greater than that of its child node, and this property should be satisfied recursively for all subtrees in the binary tree.

Small top heap (Min Heap): in a small top heap, the value of the root node must be less than that of its child node, and all subtrees of the binary tree recursively satisfy the same property.

Not all people are computer-trained buddies, so I'm nagging about the concept.

The small top heap takes any node as the root, and its left and right children must be greater than or equal to the value of that node, so the root node of the whole tree must be the node with the lowest median value, while the big top heap has the opposite characteristic.

Binary reactor

A binary heap is a binary tree that satisfies the following attributes:

The binary heap must be a complete binary tree. This property of binary heaps also determines that they are suitable for storage in arrays.

The binary pile is either a small top pile or a large top pile. The value of the root node in the small top binary heap is the minimum in the whole tree, and all the vertices and their subtrees in the binary tree satisfy this characteristic. The big top heap is similar to the small top heap, the root node of the big top heap is the maximum value in the whole tree, and the values of all nodes in the binary tree are greater than or equal to their sub-tree nodes.

Because the small top pile and the big top pile are not consistent in the size of the vertices, both of them are a complete binary tree. All the following explanations take the small top pile as an example, knowing the small top pile and the big top pile you can write it yourself.

These are two typical small top piles.

Storage structure of binary heap

A binary heap is a complete binary tree, usually represented by an array. The root element is represented by arr [0], while the other nodes (the storage location of the I node) meet the characteristics in the following table:

Array representation

Array denotes the parent node of the I node of arr [(imur1) / 2] the left child node of the I node arr [2 * I + 1] the right child node of the I node arr [2 * I + 2]

This representation and property of binary heap essentially corresponds to the characteristics of a complete binary tree itself.

Common operation of small top binary reactor

The time complexity of getting the root element getMin () of the small top binary heap is; according to the above storage structure, the root node is arr [0], and you can return it.

Int getMin () {return arr [0];}

The time complexity of removing the smallest element removeMin () of the small top binary heap is because after removing the smallest element of the small top binary heap (that is, the top element of the heap), the heap needs to be adjusted so that the heap still maintains its attributes, which is generally called heapify.

Int removeMin () {if (heap_size 45, swap the two, and then continue to stack the subtree of the vertex (I = 3) with a value of 50:

Step 3: calculate the left and right children of node 50 (I = 1) to be stacked, and find that it does not exist, so node 50 has reached the leaf node, and the stacking of the whole tree is completed (in fact, the process of stacking is quite simple. We will also use stacking later, we delete and so on, we do not understand here, it does not affect the following!).

Update the given target value updateKey (int ijinint new_val), which is assumed to be new_val

Val, then the updated nodes are stacked, so they are not processed separately. I also want to deal with both. Add an If...else.... That's fine.

Void updateKey (int I, int new_val) {harr [I] = new_val; while (I! = 0 & & Har [parent (I)] > harr [I]) {swap (& Har [I], & Har [parent (I)]); I = parent (I);}}

In contrast to the stacking operation, we start backtracking from the updated node until the value of the node is greater than that of the parent node.

We update the value of node 50 with subscript 4 to 8:

The first step: judge the size relationship of the parent node of node 8 (I = 4), 8 < 15, swap 8 and 15, and then node 8 (I = 1) continues to judge:

Step 2: judge the size relationship between node 8 (I = 1) and its parent node, 8 < 10, swap 8 and 10:

Step 3: judge node 8 (I = 0) and find that it is already a root node and has no parent node, and the update ends.

The time complexity of updating the node value is also the tree height.

Insert node insert (): the time complexity of inserting a new node is also. Insert a new node at the end of the tree, and if the value of the new node is greater than the value of its parent, the insertion is done directly; otherwise, similar to the updateKey () operation, backtrack the correction heap up.

Void insert (int k) {if (heap_size = = capacity) {cout harr [I]) {swap (& Har [I], & Har [parent (I)]); I = parent (I);}}

For example, we insert node 30 (I = 5), because its value is greater than the value of the parent node 20, and does not violate the properties of the heap, the direct insertion is completed.

Based on the insertion of node 30, we insert node 9 (I = 6):

The value of the newly inserted node 9 (I = 6) is less than that of the parent node 20 (I = 2), so switch nodes 9 and 20, and then continue to determine that the value is 9 (I = 2):

Judge the value of node 9 (I = 2) and node 10 (I = 0), 9 < 10, exchange 9 and 10, and then continue to judge value 9 (I = 2):

It is found that the value 9 (I = 2) is already the root node, and the insertion is complete.

Delete node delete (): the time complexity of deleting a node is also the same. The node to be deleted is replaced with infinitesimal INT_MIN, which calls updateKey (I, INT_MIN), and then removes the heap top element INT_MIN, calling removeMin ().

Void delete (int I) {updateKey (I, INT_MIN); removeMin ();}

For example, if we delete node 15 (I = 1), the first step is to call update (1, INT_MIN) to replace the value of the node with INT_MIN:

Step 2: call the removeMin () function to remove the INT_MIN.

Finally, let's take a look at the implementation code of the stacking operation mentioned in the removeMin () function (combined with the stacked image and text from the previous introduction to the removeMin () function):

Void Heapify (int I) {int l = left (I); / / left child subscript 2i + 1 int r = right (I) of node I; / / right child subscript 2i + 2 int samllest = I of node I; if (l < heap_size & arr [l] < arr [I]) {smallest = l } if (r < heap_size & & arr [r] < arr [smallest]) {smallest = r;} if (smallist! = I) {swap (& arr [I], & arr [smallest]); Heapify (smallest);}}

The basic operation of binary heap is introduced, because binary heap is the most common in exams and interviews, so it is recommended to understand it!

Application of reactor

Heap sorting (Heap Sort): heap sorting can use binary heap to sort arrays in time, which is why we will talk about binary heap first today.

Second, priority queue (Priority Queue): using binary heap, we can achieve an efficient priority queue, because the time complexity of all kinds of operations of binary heap is. (I don't seem to have mentioned the priority queue. I will update it if I have a chance in the future.)

3. Graph algorithm (Graph Algorithms): priority queues are widely used in graph algorithms such as Dijstra algorithm and Prim algorithm.

This is the end of what is a binary heap. Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.