Example analysis of down and up adjustment of heap in Java
This article mainly introduces the Java heap down and up adjustment example analysis, the article is very detailed, has a certain reference value, interested friends must read it!
I. about the heap
The bottom layer of PriortyQueue (priority queue) in JDK1.8 uses the data structure of heap, and the heap actually adjusts some elements based on the complete binary tree.
1. The concept of heap
Heaps can be divided into the largest and the smallest.
The maximum (minimum) heap is a tree in which the elements of each node are not less than (greater than) the elements of its child (if any). Dadu is not only a complete binary tree, but also the largest tree. Xiaodi is not only a complete binary tree, but also the smallest tree.
Note: any subtree in the heap is also a heap, that is, a large pile of subtrees is also a big heap, and so is a small heap.
two。 Properties of heap
The value of a node in the heap is always not greater than or less than the value of its parent node
The heap is always a complete binary tree.
3. Storage mode of heap
From the concept of heap, it is known that heap is a complete binary tree, so the rules of hierarchy can be stored efficiently in a sequential way.
Note: for incomplete binary trees, it is not suitable to use sequential storage, because in order to restore binary trees, empty nodes must be stored in space, which will lead to low space utilization.
Second, the creation of heap 1. Heap downward adjustment
For a given data, how to create it as a heap? For example, the following figure:
After careful observation of the above figure, it is found that the left and right subtrees of the root node have fully satisfied the properties of the heap, so you only need to adjust the root node downward.
Take the small heap as an example:
1. Let parent mark the nodes that need to be adjusted, and child marks the left child of parent (Note: if parent has a child, there must be a left child first)
two。 If the left child of parent exists, that is, child
