Shulou(Shulou.com)05/31 Report--

This article introduces the relevant knowledge of "how to use heap to solve Top-k problems with Java". In the operation of actual cases, many people will encounter such a dilemma. Next, let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

1. What is heap? Reactor structure

A heap is actually a binary tree, but an ordinary binary tree stores data in a chained structure, while a heap stores data sequentially in an array. So what kind of binary tree is suitable for sequential storage?

Assuming that an ordinary binary tree can be stored in an array, we can get the following structure:

We can see that when there is a null value in the middle of the binary tree, the storage space of the array will be wasted, so under what circumstances will the space not be wasted? That's the complete binary tree.

From the above structure, we can not use the chain structure pointer to access the child node or father node, can only be accessed through the corresponding subscript, in fact, it is relatively simple.

For example, the following figure:

It is known that the subscript of 2 nodes is 1, so

His left child's subscript is: 2 * 2 + 1 = 3

His right child's subscript is: 2 * 2 + 2 = 4

On the contrary, it is known that the subscript of node 1 is 3, and the subscript of node 3 is 4, so

The subscript of the parent node of node 1 is: (3-1) / 2 = 1

The subscript of the parent node of the 3 node is: (4-1) / 2 = 1

Big root pile VS small root pile big root pile (maximum pile)

The big root heap ensures that the root node of each binary tree is larger than the left and right child nodes.

Adjust from the root node of the last subtree to the root node of each subtree, so that each subtree is adjusted down to a large root heap, and finally down to make the final adjustment to ensure that the binary tree as a whole is a large root heap (this adjustment is mainly for the following heap sorting).

The specific adjustment process is as follows:

How to implement it in code?

We first adjust from the last subtree, then we need to get the root node parent of the last subtree. We know that the last node subscript of the array is len-1, and this node is the left or right child of the last subtree. According to the child subscript, we can get the root node subscript (parent), and parent-- can adjust each subtree until it comes to the root node, and then adjust downwards for the last time. You can get a big root pile.

/ / turn the array into a large root heap structure public void createHeap (int [] arr) {for (int I = 0; I)

< arr.length; i++) { elem[i] = arr[i];// 放入elem[],假设不需要扩容 usedSize++; } // 得到根节点parent, parent--依次来到每颗子树的根节点， for (int parent = (usedSize-1-1)/2; parent >

= 0; parent--) {/ / search down in turn so that each subtree becomes a large root heap shiftDown (parent,usedSize);}} / / the downward search becomes a large root heap public void shiftDown (int parent,int len) {int child = parent*2+1;// to get the left child while (child)

< len){ // 如果有右孩子,比较左右孩子大小,得到较大的值和父节点比较 if (child+1 < len && (elem[child] < elem[child+1])){ child++; } // 比较较大的孩子和父节点,看是否要交换 int max = elem[parent] >

= elem [child]? Parent: child; if (max = = parent) break;// if it does not need to be adjusted, it means that the current subtree is already a large root heap, and directly break swap (elem,parent,child); parent = child;// continues to detect downward to see if you want to adjust child = parent*2+1;}} public void swap (int [] arr,int iMint j) {int temp = arr [I] Arr [I] = arr [j]; arr [j] = temp;} small root heap (minimum heap)

The small root heap ensures that the root node of each binary tree is smaller than the left and right child nodes.

The adjustment process is the same as above.

Priority queue (PriorityQueue)

In java, heap is provided as a data structure (PriorityQueue), also known as priority queue. When we create such an object, we get a small root heap without adding data. We can add or delete elements to it. Each time we delete or add an element to it, the system will adjust it as a whole and re-adjust it to a small root heap.

/ / by default, you get a small root heap PriorityQueue smallHeap = new PriorityQueue (); smallHeap.offer (23); smallHeap.offer (2); smallHeap.offer (11); System.out.println (smallHeap.poll ()); / / Pop 2, and the remaining smallest element is 11, which will be adjusted to the top of the heap, and System.out.println (smallHeap.poll ()) will pop up next time. / / Pop up 11 / / if you need to get a large root heap, pass a comparator PriorityQueue BigHeap = new PriorityQueue (new Comparator () {@ Override public int compare (Integer o1, Integer o2) {return o2-o1;}}); 2. Top-k problem solving ideas

Ex.: there are a bunch of elements that allow you to find out the first three smallest elements.

Idea 1: sort the array from small to large and get the first three elements of the array. However, it can be found that the time complexity is too high and undesirable.

Idea 2: put all the elements into a heap structure, and then pop up three elements, each pop-up elements are the current heap smallest, then the three pop-up elements are the first three smallest elements.

This idea can be done, but if I have 1000000 elements and only the first three smallest elements pop up, then I will use a heap with a size of 1000000. This is too complex to do, and this method is not recommended.

Idea 3:

We need to get the three smallest elements, so build a heap of size 3, assuming that the current heap structure is just full of three elements, then these three elements are the current smallest three elements. Assuming that the fourth element is one of the elements we want, then at least one of the first three elements needs to pop up if at least one of the first three elements is not what we want, so who does it pop up?

What we want to get is the first three smallest elements, so the largest element in the current heap structure must not be what we want, so here we build a big heap. Pop up the element and place the fourth element until you have traversed the entire array.

In this way, we get a heap with only the first three smallest elements, and we can see that the size of the heap has always been 3, rather than building a heap as big as there is data, and then popping up the elements in turn.

/ / find the first k smallest elements, public static int [] topK (int [] arr,int k) {/ / create a large root heap of size k PriorityQueue maxHeap = new PriorityQueue (new Comparator () {@ Override public int compare (Integer o1, Integer o2) {return o2;}}); for (int I = 0; I)

< arr.length; i++) { if (i < k){ // 放入前 k 个元素 maxHeap.offer(arr[i]); }else{ // 从第 k+1个元素开始进行判断是否要入堆 if (maxHeap.peek() >

Arr [I]) {maxHeap.poll (); maxHeap.offer (arr [I]);} int [] ret = new int [k]; for (int I = 0; I < k; iTunes +) {ret [I] = maxHeap.poll ();} return ret } this is the end of the content of "how to solve the Top-k problem with Java with heap". Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.