数据结构-7.Java对象的比较

时间：2024-11-19 08:50:02
// JDK中PriorityQueue的实现：
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {
//......

// 默认容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// 内部定义的比较器对象，用来接收用户实例化PriorityQueue对象时提供的比较器对象
private final Comparator<? super E> comparator;
// 用户如果没有提供比较器对象，使用默认的内部比较，将comparator置为null
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
// 如果用户提供了比较器，采用用户提供的比较器进行比较
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
// ...
// 向上调整：
// 如果用户没有提供比较器对象，采用Comparable进行比较
// 否则使用用户提供的比较器对象进行比较
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
// 使用Comparable
@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
// 使用用户提供的比较器对象进行比较
@SuppressWarnings("unchecked")
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
}

5. 使用PriorityQueue创建大小堆，解决TOPK问题

top-k 问题：最大或者最小的前 k 个数据。比如：世界前 500 强公司
链接: 
面试题 17.14. 最小K个数 - 力扣（LeetCode）
容易想到的常规做法:
上图两种做法虽然很方便但是 效率不高. 
换种做法: 
题目要求的是前 k 个最小的数组
我们不妨先把原数组前 k 个元素 建大堆, 然后将 大堆的堆顶元素top 与原数组剩余的元素 [ i ] 进行比较, 若是 top较大 则 top出堆 [ i ] 入堆. 否则就只让 i++即可. 这样一来 比较完之后 堆中的 k 个 元素 必然是 前 k 个最小的元素. 
同理, 若是 题目要求前 k 个最大的数组, 则建小堆, top较小 则出堆......
总结成下图: 
下面给出OJ面试的答案, 一定要先自己写, 写不出来了再看答案. 
//由于PriorityQueue默认是小根堆, 所以需要实现比较器, 重写compare方法,来创建大根堆.
class IntCmp implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}
class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr == null || k <= 0) return ret;

        //创建大根堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCmp());
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        for (int j = k; j < arr.length; j++) {
            int top = priorityQueue.peek();
            if(top > arr[j]) {
                //top大, 出堆, 小的元素入堆
                priorityQueue.poll();
                priorityQueue.offer(arr[j]);
            }
        }
        for(int i = 0;i < k;i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }
}

时间复杂度分析: 

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=20fn3gqj5vk00

相关文章