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

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

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.