Related applications of priority queue

One 、topK problem

Problem description ： from N Before the number is found K A big number

such as {1,2,3,4,5} Middle front 2 The big one is 4 and 5

Here is how to use priority queues , The idea is ：

• Use the first in the array K The first element builds a small root heap
• Then traverse the array values , If this value is greater than the heap top element, the heap top element will be ejected
• Then put this value into a small root heap

Because the smallest value in the heap is ejected every time , So the last thing left K The value must be the largest .

   

In this way , It's not hard for us to get ：

• Seek before K The biggest , Build small root pile
• Seek before K Minimum , Build a big pile
• Please K Big , Is the top element of the adjusted small root heap （ The top element must be this K The smallest of the three ）
• Please K Small , Is the adjusted top element of the large root heap

Here we use code to write a pre K It's the smallest value  

    // Before array K Small value 
    public static int[] topK(int[] array, int k){
        // Create a large root heap 
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 0; i < array.length; i++){
            // hold K Data into the heap 
            if (priorityQueue.size() < k){
                priorityQueue.offer(array[i]);
            }else {
                // Start comparing 
                int top = priorityQueue.peek();
                // Array elements are put in when they are small 
                if (top > array[i]){
                    priorityQueue.poll();
                    priorityQueue.offer(array[i]);
                }
            }
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++){
            ans[i] = priorityQueue.poll();
        }
        return ans;
    }

Time complexity ：O(N*logK)

An exercise ：373. Look for the smallest K Pairs of numbers

  

Two 、 Heap sort

Problem description ： hold N Sort the number from small to large

From small to large , Adopt large root pile , step ：

• 1、 Build the entire array into a large root heap
• 2、 Swap the top and tail elements of the heap , And then from 0 Start adjusting the large root heap
• 3、 Use one end Remember tail elements , Again --, Make sure the largest element is at the bottom

    public void heapSort(){
        int end = usedSize - 1;
        while (end > 0){
            int tmp = elem[end];
            elem[end] = elem[0];
            elem[0] = tmp;
            shiftDown(0, end);
            end--;
        }
    }

   

Thank you for seeing this