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

Java priority queue is like, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can gain something.

1. Priority queue concept

Priority queue (priority queue) is a special data structure.

Each element in the queue is assigned a priority value, and the queuing order is divided according to the priority value.

There are generally two kinds of queuing order: high priority or low priority.

Priority queue must have at least two basic ADT: in-team, out-of-team (according to high priority or low priority)

Cause: it is also to improve the efficiency of data processing. Just imagine, to achieve the corresponding function of the priority queue, if you use a linked list or array, you can either sort and then insert, or insert first and then find the maximum and minimum elements. In this way, the time complexity of joining and leaving the team is at least O (N).

The time complexity of priority queue queuing and queuing is O (log N).

The priority queue is implemented based on the binary heap.

two。 Binary reactor (Heap)

Heap is a special binary tree with the following properties:

The value of each node is greater than or equal to the value of its left and right child node (large top heap), or the value of each node is Xiao Yu or equal to its left and right child value (small top heap).

The structure of a complete binary tree must be satisfied.

Complete binary tree and full binary tree

Complete binary tree complete binary tree

Leaf nodes can only appear in the last two layers, and the leaf nodes in the last layer are all left-aligned.

A complete binary tree with depth h

Full binary tree full binary tree

A full binary tree with depth h has (2 ^ h)-1 node.

From the definition of binary heap, it can be seen that the heel node must have the largest (or minimum) node value in the binary heap. The larger (or smaller) node is close to the root node

Storage structure of the heap:

In general, the heap is stored in an array, and the subscript of the parent node of the I node is (iMur1) / 2.

If you use the sequence traversal order to put the big top heap and the small top heap into the array

The relationship is shown in the figure:

Important operation of heap

Insert: after inserting an element, the new element is first inserted into the surface layer (that is, the last layer is as left as possible), and then adjusted according to the nature of the heap.

Example: write the result of inserting 10 and 12 at a time into an initially empty binary heap.

Delete: deletion always occurs at the root, and then the last element (that is, the rightmost element of the last layer) is used to fill the gap, and then the structure of the heap is adjusted according to the nature of the heap.

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

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.