使用PriorityQueue實作大小根堆

1.一個基于優先級堆的無界優先級隊列。優先級隊列的元素預設按照其自然順序進行排序（即預設小根堆），大根堆需要通過構造方法重寫Comparator接口的compare方法。

2.初始容量為11，線程不安全，線程安全的實作結構為PriorityBlockingQueue。

3.小根堆的實作

public class findTopK {

    //找出前k個最大數，采用小頂堆實作
    public static int[] findKMax(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(k);//隊列預設自然順序排列，小頂堆，不必重寫compare

        for (int num : nums) {
            if (pq.size() < k) {
                pq.offer(num);
            } else if (pq.peek() < num) {//如果堆頂元素 < 新數，則删除堆頂，加入新數入堆
                pq.poll();
                pq.offer(num);
            }
        }

        int[] result = new int[k];
        for (int i = 0; i < k&&!pq.isEmpty(); i++) {
            result[i] = pq.poll();
        }
        return result;
    }

 public static void main(String[] args) {
        int[]arr=new int[]{1, 6, 2, 3, 5, 4, 8, 7, 9};
        System.out.println(Arrays.toString(findKMax( arr,5)));
    }
}
/**
輸出：[5, 6, 7, 8, 9]
*/
           

大根堆的實作

public class findTopK {

    要找前k個最小數，則建構大頂堆，要重寫compare方法
    public static int[] findKMin(int[] nums, int k) {

        PriorityQueue<Integer> pq =
                new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

        for (int num : nums) {
            if (pq.size() < k) {
                pq.offer(num);
            } else if (pq.peek() > num) {//如果堆頂元素 > 新數，則删除堆頂，加入新數入堆
                pq.poll();
                pq.offer(num);
            }
        }

        int[] result = new int[k];
        for (int i = 0; i < k&&!pq.isEmpty(); i++) {
            result[i] = pq.poll();
        }
        return result;
    }

    public static void main(String[] args) {
        int[]arr=new int[]{1, 6, 2, 3, 5, 4, 8, 7, 9};
        System.out.println(Arrays.toString(findKMin( arr,5)));
    }

}
/**
輸出：[5, 4, 3, 2, 1]
*/