Top K算法(问题) 小顶堆指定排序实现及源码解析
程序员文章站
2024-03-22 23:22:46
...
本文基于大家了解了有限队列进行的,如果不了解请点击下方传送门,进入了解,大佬文章里面也对这个队列如何使用有很详细的解答。
传送门:PriorityQueue(优先队列参考)https://blog.csdn.net/u010623927/article/details/87179364
package com.example.tran;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
/**
* @author chengtonghua
* @date 2021-02-09
*/
public class Quene {
public static void main(String[] args) {
//优先队列,可以指定其排序升序或者降序
Queue<Integer> integerPriorityQueue = new PriorityQueue<>(7,sortType);
Random rand = new Random();
for (int i = 0; i < 100; i++) {
integerPriorityQueue.add(Integer.valueOf(rand.nextInt(1000)));
}
for (int i = 0; i < 7; i++) {
Integer in = integerPriorityQueue.poll();
System.out.println("Processing Integer:" + in);
}
}
//匿名Comparator实现
public static Comparator<Integer> sortType = new Comparator<Integer>() {
public int compare(Integer c1, Integer c2) {
return (int) (c2 - c1);
}
};
}
看上面的代码,自定义了排序规则但是在插入的时候只是执行了add方法,这个时候我们并没有看到我们指定的排序规则生效对不对。
这个时候先别急,PriorityQueue插入的时候会执行判断,当前对象是否有指定过排序规则,如果有则执行排序规则,没有的话则执行;
不信的话请看源码
/**
* Inserts the specified element into this priority queue.
*
* @return {@code true} (as specified by {@link Collection#add})
* @throws ClassCastException if the specified element cannot be
* compared with elements currently in this priority queue
* according to the priority queue's ordering
* @throws NullPointerException if the specified element is null
*/
public boolean add(E e) {
return offer(e);
}
/**
* Inserts the specified element into this priority queue.
*
* @return {@code true} (as specified by {@link Queue#offer})
* @throws ClassCastException if the specified element cannot be
* compared with elements currently in this priority queue
* according to the priority queue's ordering
* @throws NullPointerException if the specified element is null
*/
public boolean offer(E e) {
if (e == null)//不允许放入null元素
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);//自动扩容
siftUp(i, e);//执行插入逻辑
size = i + 1;
return true;
}
如果不指定排序方式则按照默认排序方式进行插入的逻辑(默认排序根据代码可以看出是从小到大进行的排序)
private static <T> void siftUpComparable(int k, T x, Object[] es) {
Comparable<? super T> key = (Comparable<? super T>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = es[parent];
if (key.compareTo((T) e) >= 0)
break;
es[k] = e;
k = parent;
}
es[k] = key;
}
指定排序方式之后的插入逻辑(最上面我指定是从大到小)
private static <T> void siftUpUsingComparator(
int k, T x, Object[] es, Comparator<? super T> cmp) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = es[parent];
if (cmp.compare(x, (T) e) >= 0)//执行自定义的比器方法
break;
es[k] = e;
k = parent;
}
es[k] = x;
}
看到了上面的插入逻辑应该明白了,优先队列插入时就已经按照我们指定的排序规则进行了排序,这样不论是获取最大的K个数字或者获取最小的K个数字都可以使用优先队列进行执行。