40. TopK 问题（用Java PriorityQueue实现最大最小堆）

caipengbo commented 5 years ago

PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); //小顶堆，默认容量为11
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11,new Comparator<Integer>(){ //大顶堆，容量11
    @Override
    public int compare(Integer o1,Integer o2){
        return o2.compareTo(o1); // return i2-i1; 
    }
});

caipengbo commented 5 years ago

// 使用堆（类似于一个容器），适合大数据，不用讲全部数据读入内存
    public ArrayList<Integer> GetLeastNumbers_Solution2(int [] array, int k) {
        int len = array.length;
        ArrayList<Integer> result = new ArrayList<>();
        if (k <= 0 || len < k) return result;

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        for (int value : array) {
            if (maxHeap.size() < k) {
                maxHeap.add(value);
            } else if (maxHeap.peek() > value) {
                maxHeap.poll();
                maxHeap.add(value);
            }
        }

        result.addAll(maxHeap);
        return result;
    }

caipengbo commented 5 years ago

当需要在某数据容器内频繁查找以及替换最大值的时候，二叉树是一个合适的选择，堆和红黑树就是这样的特殊数据结构

caipengbo / Coding-Interviews

40. TopK 问题（用Java PriorityQueue实现最大最小堆） #27