PriorityQueue is called priority queue. The bottom layer is implemented by the heap structure. The default is small root heap. The elements added through the offer method will be sorted in the heap, and the smallest elements will be placed on the top of the heap. The heap top (minimum) element can be obtained by peek method. Through the poll method, you can delete the heap top elements and get the heap top elements at the same time. After deletion, the smallest of the remaining elements is still at the heap top.

1, Application scenario

A certain e-commerce platform has entered a large number of businesses. Businesses can sell goods on the platform, and users can buy goods from the businesses on the platform. If the user is not satisfied with the purchased goods after payment, he can make a complaint to the platform. The user's complaint record on a certain product of a certain merchant will be stored in a table with the following structure:

Now the demand is: to find the top three businesses with the most complaint records, in order to reduce the power of their stores when searching.

2, Thinking analysis

1. Create a small root heap (PriorityQueue is the small root heap by default)
2. Add elements directly to the collection when the number of elements in the small root heap is less than 3
3. When the number of elements in the heap is equal to 3, the peek method is used to take out the top element of the heap (the smallest one) and compare it with the currently traversed element
4. If the currently traversed element is larger than the heap top element, remove the original heap top element and add the current element to the heap
5. This makes the removed elements smaller than those in the heap
6. So the last remaining N elements in the heap are the largest

3, Code implementation

import java.util.*;

// Complaint log entity class
class ComplainLog {
    // Merchant id
    public Integer storeId;
    // Commodity id
    public Integer productId;
    // Complaint record
    public String remark;
    ComplainLog(Integer storeId, Integer productId, String remark) {
        this.storeId = storeId;
        this.productId = productId;
        this.remark = remark;
    }
}

// Number of complaints by merchants entity class
class ComplainCount {
    // Merchant id
    public Integer storeId;
    // Number of complaints
    public Integer complainCount;
    ComplainCount(Integer storeId, Integer complainCount) {
        this.storeId = storeId;
        this.complainCount = complainCount;
    }
}

public class PriorityQueueTest {
    public static void main(String[] args) {
        // Simulate 10 complaint records
        ComplainLog log1 = new ComplainLog(101, 8650, "Quality is not good.");
        ComplainLog log2 = new ComplainLog(101, 8651, "The cover of the book is rotten. Garbage Logistics");
        ComplainLog log3 = new ComplainLog(101, 7921, "Beef is not fresh, suspected to be fake");
        ComplainLog log4 = new ComplainLog(101, 7963, "Sell fake goods and seal his shop!!!");
        ComplainLog log5 = new ComplainLog(102, 6217, "The store's attitude is not good. Give him the right");
        ComplainLog log6 = new ComplainLog(102, 6245, "The clothes are torn...");
        ComplainLog log7 = new ComplainLog(102, 5214, "Just want to complain");
        ComplainLog log8 = new ComplainLog(103, 5215, ". . . ");
        ComplainLog log9 = new ComplainLog(104, 4632, "2333333");
        ComplainLog log10 = new ComplainLog(104, 4632, "Is anybody there");
        ComplainLog log11 = new ComplainLog(104, 4632, "Is anybody there,aaaaaa");

        List<ComplainLog> complainLogList = new ArrayList<ComplainLog>();
        complainLogList.add(log1);
        complainLogList.add(log2);
        complainLogList.add(log3);
        complainLogList.add(log4);
        complainLogList.add(log5);
        complainLogList.add(log6);
        complainLogList.add(log7);
        complainLogList.add(log8);
        complainLogList.add(log9);
        complainLogList.add(log10);
        complainLogList.add(log11);

        // Count the number of complaints per store
        HashMap<Integer, Integer> complainCountMap = new HashMap<Integer, Integer>();
        for (ComplainLog complainLog : complainLogList) {
            if (complainCountMap.get(complainLog.storeId) == null) {
                complainCountMap.put(complainLog.storeId, 1);
            } else {
                complainCountMap.put(complainLog.storeId, complainCountMap.get(complainLog.storeId) + 1);
            }
        }
        List<ComplainCount> complainCountList = new ArrayList<ComplainCount>();
        for (Map.Entry<Integer, Integer> entry : complainCountMap.entrySet()) {
            ComplainCount complainCount = new ComplainCount(entry.getKey(), entry.getValue());
            complainCountList.add(complainCount);
        }

        // Find the top 3 businesses with the most complaint records through PriorityQueue
        PriorityQueue<ComplainCount> queue = new PriorityQueue<ComplainCount>(new Comparator<ComplainCount>() {
            @Override
            public int compare(ComplainCount o1, ComplainCount o2) {
                return o1.complainCount.compareTo(o2.complainCount);
            }
        });

        // Create a small root heap (PriorityQueue is the small root heap by default)
        // Add elements directly to the collection when the number of elements in the small root heap is less than 3
        // When the number of elements in the heap is equal to 3, the peek method is used to take out the top element of the heap (the smallest one) and compare it with the currently traversed element
        // If the currently traversed element is larger than the heap top element, remove the original heap top element and add the current element to the heap
        // All removed elements are smaller than those in the heap
        // So the last remaining N elements in the heap are the largest
        int topN = 3;
        for (ComplainCount complainCount : complainCountList) {
            if (queue.size() < topN) {
                queue.offer(complainCount);
            } else {
                if (queue.peek().complainCount < complainCount.complainCount) {
                    queue.poll();
                    queue.offer(complainCount);
                }
            }
        }

        for (ComplainCount complainCount : queue) {
            System.out.println(complainCount.storeId + ":" + complainCount.complainCount);
        }

    }
}

4, Operation results

It can be seen that the final result is that 101102104 stores have the largest number of complaints, which is in line with expectations.

Five, summary

PriorityQueue is mainly used in the scenario of large data volume TopN. A small amount of data can be sorted directly.