A few days ago, I met such a question in the interview:
Find the 100 largest numbers in 100 million.
The question stuck in my face. Later I looked it up and said to use HASH functions and the idea of divide and conquer to solve it. The 100 million numbers are HASH removed and stored separately in 1000 partitions according to the HASH value. Then each partition uses a minimum heap of 100 capacity to get the maximum 100 numbers for each partition. Finally, the minimum heap obtained in 1000 partitions can be merged.
This is primarily the problem of the smallest heap. Blame my poor foundation, after the interview and make up the minimum heap of knowledge. Refer to the Internet, wrote a minimum heap Demo to consolidate knowledge.
A couple of things to know about minimum heaps are arrays. If a child node is subscript x, its parent is (x-1)/2. If a child node is subscript Y, its right node is (x+1)<<1, and its left node is (x+1)<<1. Note: (array length)/2-1 represents the location of the parent node with the largest subscript that has children. Because the last node position is (array length -1), and then the parent node position is (array length -2)/2, which is (array length)/2-1
Private int[] data; // MinHeap{private int[] data; public MinHeap(int[] data){ this.data = data; buildHeap(); } private void buildHeap(){for(int I =(data.length)/2-1; i>=0; i--){ heapify(i); } } private void heapify(int i){ int left = left(i); int right = right(i); int small = i; if(left<data.length&&data[left]<data[small]){ small = left; } if(right<data.length&&data[right]<data[small]){ small = right; } if(i == small){ return; } swap(i,small); heapify(small); } private void swap(int i, int j){ int temp = data[i]; data[i] = data[j]; data[j] =temp; } private int left(int i){ return ((i+1)<<1)-1; } private int right(int i){ return (i+1)<<1; } public int getRoot(){ return data[0]; } public void setRoot(int root){ data[0] = root; heapify(0); }} public class Main {public static void Main (String[] args) {int[] number = new int[]{4,5,1,9,9,1,2,3,12}; int[] top7 = topK(number,7); for(int i=0; i<top7.length; i++){ System.out.print(top7[i]+" "); } } private static int[] topK(int[] number,int k) { int[] top7 = new int[k]; for (int i = 0; i < k; i++) { top7[i] = number[i]; } MinHeap minHeap = new MinHeap(top7); for(int i = k; i<number.length; i++){ int root = minHeap.getRoot(); if(number[i]<=root){ break; }else{ minHeap.setRoot(number[i]); } } return top7; }}Copy the code