1/ To grasp some concepts:

<1> Full binary tree: a full binary tree is a tree with two children for every node at every level except the last one, which has no children. The maximum number of nodes in a tree is 2 to the power of h -1, and h is the depth of the tree. If the number of nodes in a tree is 2 to the power of h -1, then it is a full binary tree. You can understand a full binary tree, you can't add any more nodes to it, it's already full. <2> Complete binary trees Complete binary trees are derived from full binary trees. If the depth of a tree is H and the number of nodes reaches the maximum except for the last layer, then such a tree is a complete binary tree, which can be interpreted as: the saturation of a complete binary tree is not as high as that of a full binary tree. A complete binary tree allows the last layer to be unsaturated, but the other layers must be saturated. <3> As long as the maximum number of child nodes of any node is <=2, the requirement is very low and any layer is allowed to be unsaturated. <5> Differences between full and complete binary trees Full binary trees are saturated, but complete binary trees allow the last layer to be unsaturated. A full binary tree is always a complete binary tree, but a complete binary tree is not always a full binary treeCopy the code

2/ What is a heap

A heap is a data structure. The heap is a complete binary tree because each layer must be filled before the next layer can be filled. There are two types of heaps, big top heaps and small top heaps in the big top heaps, where the value of the parent node is larger than the value of each child node. In the small top heap, the value of the parent node is smaller than the value of each child node. This is known as a "heap property" and is true for every node in the heap.Copy the code

On the left side of the figure is a large top heap, where each parent node has a larger value than its children. 9 is bigger than either 6 or 8. 6 is bigger than 5 and 3. According to this property, the large top heap always stores its maximum value at the root of the tree. For a small top heap, the element in the root node is always the smallest in the tree. The heap attribute is useful because the heap is often used as a priority queue because the "most important" elements can be accessed quickly. Note: We can know whether the root node is the largest or smallest element based on the large or small top heap, but the order of the other nodes is unknown. For example, in a large top heap, the largest element is always at index0, but the smallest element is not necessarily the last. The only guarantee is that the smallest element must be a leaf node, but we don't know which one. In a heap, the next layer is not allowed to be filled until all nodes of the current layer are filled, so the heap always has this shape, which echoes the above: the heap is treated as a full binary tree.Copy the code

3/ heap insertion

Place the new node at the end of the array and begin to adjust the node position graduallyCopy the code

Remove the root node replace the first element with the last element of the array, and then begin to adjust the nodes graduallyCopy the code

4/ How to construct the heap??

[3,6,8,5,7] [3,6,8,5,7] [3,6,8,5,7] [3,6,8,5,7] [3,6,8,5,7] [3,6,8,5,7] If the number of inserts is larger than that of the parent, the data will be swapped with the parent; otherwise, the data will be swapped up until it is less than or equal to the parent, or it reaches the top.)Copy the code