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

In this article, the editor introduces in detail the "priority queue instance Analysis of Java data structure" with detailed content, clear steps and proper handling of details. I hope that this "priority queue instance Analysis of Java data structure" article can help you solve your doubts.

I. the concept of heap

Definition of heap: the sequence of n elements {K1, K2, … , kn} is called a heap if and only if the following conditions are met:

(1) ki > = k2i and ki > = k (2i+1)-- large root heap

(2) ki 0) {if (Elm [child] > elem [parent]) {int tmp = elem [child]; elem [child] = elem [parent]; elem [parent] = tmp; child = parent; parent = (child-1) / 2;} else {break } public void offer (int val) {if (isFull ()) {/ / expand elem = Arrays.copyOf (elem,2*elem.length);} elem [usedSize++] = val; / / Note that usedSize-1 shiftUp (usedSize-1) is passed in here;} 4. Return to the first element of the queue

Return directly to the top element of the heap

Public int peek () {if (isEmpty ()) {throw new RuntimeException ("priority team is empty!") ;} return elem [0];} public boolean isEmpty () {return usedSize = = 0;}

The overall code:

Public class TestHeap {public int [] elem; public int usedSize; public TestHeap () {this.elem = new int [10];} / * implementation of downward adjustment function * @ param parent root node of each tree * @ param len end position of adjustment of each tree 10 * / public void shiftDown (int parent,int len) {int child = 2*parent+1 / / 1. At least there is a left child, at least 1 child while (child)

< len) { if(child+1 < len && elem[child] < elem[child+1]) { child++;//保证当前左右孩子最大值的下标 } if(elem[child] >

Elem [parent]) {int tmp = elem [child]; elem [child] = elem [parent]; elem [parent] = tmp; parent = child; child = 2roomparentroom1;} else {break } public void createHeap (int [] array) {for (int I = 0; I

< array.length; i++) { elem[i] = array[i]; usedSize++; } //根据代码 显示的时间复杂度 看起来 应该是O(n*logn) 但是 实际上是O(n) for (int parent = (usedSize-1-1)/2; parent >

= 0; parent--) {/ / adjust shiftDown (parent,usedSize);}} private void shiftUp (int child) {int parent = (child-1) / 2; while (child > 0) {if (Elm [child] > elem [parent]) {int tmp = elem [child]; elem [child] = elem [parent] Elem [parent] = tmp; child = parent; parent = (child-1) / 2;} else {break } public void offer (int val) {if (isFull ()) {/ / expand elem = Arrays.copyOf (elem,2*elem.length);} elem [usedSize++] = val; / / Note that usedSize-1 shiftUp (usedSize-1) is passed in here. } public boolean isFull () {return usedSize = = elem.length;} public int poll () {if (isEmpty ()) {throw new RuntimeException ("priority team is empty!") ;} int tmp = elem [0]; elem [0] = Elm [usedSize-1]; Elm [usedSize-1] = tmp; usedSize--; shiftDown; return tmp;} public int peek () {if (isEmpty ()) {throw new RuntimeException ("priority team is empty!") ;} return elem [0];} public boolean isEmpty () {return usedSize = = 0;} public void heapSort () {int end = this.usedSize-1; while (end > 0) {int tmp = elem [0]; elem [0] = elem [end]; elem [end] = tmp; shiftDown (0end) End--;} 5. Other TopK problems of heap

What is the TopK problem?

From the n numbers of arr [1, n], find out the largest k number, which is the classical TopK problem.

To solve this kind of problem, we often have the following ideas:

Sort the whole and output the top 10 largest elements.

Use the heap just mentioned above.

Also use heap, but this is more ingenious than the second way of thinking.

Let's go straight to train of thought three:

First use the first k elements to generate a small top heap, which is used to store the current largest k elements.

Then, start with the k + 1 element, and compare it with the top of the heap (the smallest element in the heap). If the element being scanned is larger than the top of the heap, replace the element on the top of the heap and adjust the heap to ensure that the k elements in the heap are always the largest k elements at present.

Until all the nmurk elements are scanned, and finally the k elements in the heap are the required TopK.

Find the first three largest elements in this array {12pr 15, 21, 41, 30} as an example.

So if we sort a group from small to large, should we use a large root heap or a small root heap?

The answer is: big root pile!

The steps are as follows:

Adjust this set of data to a large root heap.

0 subscript can be exchanged with the last unsorted element

Repeat 1 and 2 until the end.

Summary:

If you want the top K elements, you need to build a small root pile. If you want to find the smallest elements, you need to build a big heap. The largest element in K. Build a small heap, and the element at the top of the pile is the largest element. The K-smallest element. Build a big pile, and the element at the top of the pile is the smallest element.

Public void heapSort () {int end = this.usedSize-1; while (end > 0) {int tmp = elem [0]; elem [0] = elem [end]; elem [end] = tmp; shiftDown (0verse end); end--;}} public void shiftDown (int parent,int len) {int child = 2*parent+1 / / 1. At least there is a left child, at least 1 child while (child)

< len) { if(child+1 < len && elem[child] < elem[child+1]) { child++;//保证当前左右孩子最大值的下标 } if(elem[child] >

Elem [parent]) {int tmp = elem [child]; elem [child] = elem [parent]; elem [parent] = tmp; parent = child; child = 2roomparentroom1;} else {break } here, the article "priority queue instance Analysis of Java data structures" has been introduced. If you want to master the knowledge points of this article, you still need to practice and use it yourself. If you want to know more about related articles, please follow the industry information channel.

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.