Java实现优先队列及堆
在阅读本文之前，建议读者优先阅读专栏内前面的文章。
目录
前言
本文主要介绍Java中与优先队列和堆相关的知识。
一、基本概念：
前面介绍过队列，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适，比如在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；班主任排座位时可能会让成绩好的同学先挑座位。在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。
如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足Ki <= K2i+1且Ki<= K2i+2(Ki >= K2i+1 且 Ki >= K2i+2)，i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫最小堆或小根堆。对于堆来说，堆中某个节点的值总是不大于或不小于其父节点的值；堆总是一棵完全二叉树。
由于堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储。对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。
二、对于堆和优先队列的模拟实现：
要想实现优先队列，就必须先实现堆。假设我们目前有个数组{27,15,19,18,28,34,65,49,25,37}，我们该如何将其创建为堆呢？
根据我们上面分析的过程，我们可以先把堆基础的结构和简单的方法列出：
public class TestHeap {
public int[] elem;
public int usedSize;
public TestHeap(){
this.elem=new int[10];
}
public void initElem(int[] array){
for(int i = 0; i < array.length; i++){
this.elem[i] = array[i];
}
}
}我们接下来思考下如何建堆？仔细观察上图后发现根节点的左右子树已经完全满足堆的性质，因此只需将根节点向下调整好即可。向下过程(以小堆为例)就是先让parent标记需要调整的节点，child标记parent的左孩子(注意parent如果有孩子一定先是有左孩子)。如果parent的左孩子存在，即child < size， 进行以下操作，直到parent的左孩子不存在：parent右孩子是否存在，存在找到左右孩子中最小的孩子，让child进行标；将parent与较小的孩子child比较，如果parent小于较小的孩子child，调整结束，否则交换parent与较小的孩子child。交换完成之后，parent中大的元素向下移动，可能导致子树不满足对的性质，因此需要继续向下调整，即parent = child；child = parent*2+1; 然后继续重复上面过程。
当然，我们也可以向上去建堆，我们在下面会进行讲解。那么根据我们上面的分析过程，读者可以思考一下如何实现建堆，我这里给出我的代码：
public class Main {
public static void main(String[] args) {
int[] array = {27,15,19,18,28,34,65,49,25,37};
TestHeap testHeap = new TestHeap();
testHeap.initElem(array);
testHeap.createHeap();
}
}public class TestHeap {
public int[] elem;
public int usedSize;
public TestHeap(){
this.elem=new int[10];
}
public void initElem(int[] array){
for(int i = 0; i < array.length; i++){
this.elem[i] = array[i];
this.usedSize++;
}
}
public void createHeap(){
for(int parent = (this.usedSize - 1 - 1) / 2; parent >= 0; parent--){
siftdown(parent, this.usedSize);
}
}
/**
*
* @param parent 每棵子树调整时候的起始位置
* @param usedSize 判断每棵子树何时调整结束
*/
private void siftdown(int parent, int usedSize) {
int child = 2 * parent + 1;
while(child < usedSize){
if(child + 1 < usedSize&& elem[child] < elem[child + 1]){
child++;
}
if(elem[child] > elem[parent]){
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
parent = child;
child = 2 * parent + 1;
}else{
break;
}
}
}
}
可以看到最终结果如下，我们确实成功得到了一个大根堆。
需要注意的是，在调整以parent为根的二叉树时，必须要满足parent的左子树和右子树已经是堆了才可以向下调整。分析时间复杂度的话，最坏的情况即图示的情况，从根一路比较到叶子，比较的次数为完全二叉树的高度，即时间复杂度为O(logN)。那对于普通的序列{1,5,3,8,7,6}，即根节点的左右子树不满足堆的特性，又该如何调整呢？
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
因此我们建堆的时间复杂度就是O(N)。
那么如果现在我们想在堆中插入或者删除元素的话，我们该如何去操作呢？我们首先来看一下插入操作。其实堆的插入总共需要两个步骤，先将元素放入到底层空间中(注意空间不够时需要扩容)；将最后新插入的节点向上调整，直到满足堆的性质。
基于我们上面已完成的代码，读者可以自行实现，我这里给出我的代码：
public void push(int val){
if(isFull()){
elem = Arrays.copyOf(elem, elem.length * 2);
}
elem[usedSize] = val;
siftUp(usedSize);
usedSize++;
}
private void siftUp(int child) {
int parent = (child - 1) / 2;
while(parent >= 0){
if(elem[child] > elem[parent]){
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
child = parent;
parent = (child - 1) / 2;
}else{
break;
}
}
}
public boolean isFull(){
return usedSize == elem.length;
}public class Main {
public static void main(String[] args) {
int[] array = {27,15,19,18,28,34,65,49,25,37};
TestHeap testHeap = new TestHeap();
testHeap.initElem(array);
testHeap.createHeap();
testHeap.push(80);
}
}可以看到此时我们成功插入了：
需要注意的是，堆的删除一定删除的是堆顶元素。具体操作如下，将堆顶元素对堆中最后一个元素交换；将堆中有效数据个数减少一个；对堆顶元素进行向下调整。
这个时候我们来实现这个方法的话相对来说就会容易一些了：
public int poll(){
if(isEmpty()){
return -1;
}
int tmp = elem[0];
elem[0] = elem[usedSize-1];
elem[usedSize-1] = tmp;
siftdown(0, usedSize - 1);
usedSize--;
return tmp;
}
public boolean isEmpty(){
return usedSize == 0;
}public class Main {
public static void main(String[] args) {
int[] array = {27,15,19,18,28,34,65,49,25,37};
TestHeap testHeap = new TestHeap();
testHeap.initElem(array);
testHeap.createHeap();
testHeap.push(80);
System.out.println(testHeap.poll());
System.out.println(testHeap.poll());
}
}其运行结果如下：
那么对于模拟队列的实现就大致如下了：
public class MyPriorityQueue {
// 演示作用，不再考虑扩容部分的代码
private int[] array = new int[100];
private int size = 0;
public void offer(int e) {
array[size++] = e;
shiftUp(size - 1);
}
public int poll() {
int oldValue = array[0];
array[0] = array[--size];
shiftDown(0);
return oldValue;
}
public int peek() {
return array[0];
}
}三、常用接口介绍：
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，本文主要介绍PriorityQueue。
我们可以键入如下的代码：
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(10);
pq.offer(20);
pq.offer(30);
System.out.println(pq.peek());
}
}其运行结果如下：
这个结果就为我们证明了这个优先队列是小根堆。对于优先队列来说，它有如下需要注意的点：首先使用时必须导入其所在的包； 其次PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常；然后不能插入null对象，否则会抛出NullPointerException；并且优先队列没有容量限制，可以插入任意多个元素，其内部可以自动扩容；插入和删除元素的时间复杂度为O(logN)。
对于优先队列来说，它有如下的常用构造方式，其他的读者们可以参考帮助文档。
我们进入优先队列的源码来仔细看一下它的成员变量和相关方法实现：
private static final int DEFAULT_INITIAL_CAPACITY = 11;
/**
* Priority queue represented as a balanced binary heap: the two
* children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The
* priority queue is ordered by comparator, or by the elements'
* natural ordering, if comparator is null: For each node n in the
* heap and each descendant d of n, n <= d. The element with the
* lowest value is in queue[0], assuming the queue is nonempty.
*/
transient Object[] queue; // non-private to simplify nested class access
/**
* The number of elements in the priority queue.
*/
int size;
/**
* The comparator, or null if priority queue uses elements'
* natural ordering.
*/
@SuppressWarnings("serial") // Conditionally serializable
private final Comparator<? super E> comparator;这里第一行代码描述的是默认的优先队列的容量，如果没有指定初始容量，那么底层数组默认会以11作为初始长度。需要注意的是，11并不是优先队列最多只能存放11个元素，而只是初始容量。当元素数量超过当前数组容量时，PriorityQueue会自动进行扩容。
第二行代码则是整个优先级队列的核心实现代码，它是真正用来存储元素的底层数组。虽然变量名叫queue，但它并不是按照普通队列的方式存储元素，而是使用数组来表示一棵完全二叉堆。
第三行代码中的变量表示当前优先队列中实际存储的元素个数。我们需要区分两个概念，queue.length表示底层数组的容量，size表示当前队列中实际元素的数量。
最后一行这个变量表示优先队列使用的比较器，它决定了元素之间的优先级规则。如果创建优先队列时没有传入比较器，那么comparator为null，此时优先队列会使用元素本身的自然顺序进行比较。对于Integer类型来说，自然顺序就是从小到大，因此默认情况下PriorityQueue<Integer>是小根堆。但是如果如果我们手动传入比较器：
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);此时优先队列会按照自定义规则进行排序。上面的写法表示较大的元素优先级更高，因此可以把默认的小顶堆改造成大顶堆。
另外，queue变量前面有一个关键字transient。transient表示这个字段不会按照Java默认序列化机制直接序列化。原因是PriorityQueue内部数组中可能包含未使用的位置，而且它的堆结构也有自己的序列化处理逻辑，所以源码中将底层数组标记为transient，避免直接把内部数组原样序列化出去。
接下来我们可以重点看下我们刚刚提到的一系列构造方法：
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
/**
* Creates a {@code PriorityQueue} with the specified initial
* capacity that orders its elements according to their
* {@linkplain Comparable natural ordering}.
*
* @param initialCapacity the initial capacity for this priority queue
* @throws IllegalArgumentException if {@code initialCapacity} is less
* than 1
*/
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
/**
* Creates a {@code PriorityQueue} with the default initial capacity and
* whose elements are ordered according to the specified comparator.
*
* @param comparator the comparator that will be used to order this
* priority queue. If {@code null}, the {@linkplain Comparable
* natural ordering} of the elements will be used.
* @since 1.8
*/
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
/**
* Creates a {@code PriorityQueue} with the specified initial capacity
* that orders its elements according to the specified comparator.
*
* @param initialCapacity the initial capacity for this priority queue
* @param comparator the comparator that will be used to order this
* priority queue. If {@code null}, the {@linkplain Comparable
* natural ordering} of the elements will be used.
* @throws IllegalArgumentException if {@code initialCapacity} is
* less than 1
*/
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;
}
可以看到前三个构造方法不管是谁最后都必须去调用最后一种构造方法。
所以接下来我们重点要看的其实就是这最后一种构造方法。这个构造方法接收两个参数：
int initialCapacity
Comparator<? super E> comparator这两个参数分别表示优先队列底层数组的初始容量和优先队列中元素的比较规则，也就是决定谁的优先级更高。我们首先看方法签名：
public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)这说明我们可以在创建优先队列时，同时指定初始容量和比较器。例如下面这个代码：
PriorityQueue<Integer> queue = new PriorityQueue<>(20, (a, b) -> b - a);这行代码表示创建一个初始容量为20的优先队列，并且使用自定义比较器(a, b) -> b - a。默认情况下，PriorityQueue<Integer>是小顶堆，而这个比较器会让较大的元素优先级更高，因此可以把它变成大顶堆。接着看参数检查：
if (initialCapacity < 1)
throw new IllegalArgumentException();这段代码的意思是如果传入的初始容量小于 1，就直接抛出IllegalArgumentException异常。也就是说，下面这种写法是不允许的：
PriorityQueue<Integer> queue = new PriorityQueue<>(0, null);因为 initialCapacity 至少要为1。同时在源码注释中提到：
//This restriction of at least one is not actually needed,but continues for 1.5 compatibility意思是从实现角度来说，初始容量必须大于等于1这个限制并不是绝对必要的。理论上，优先队列也可以先创建一个容量为0的数组，等真正添加元素时再扩容。但是为了兼容Java 1.5以来的旧版本行为，源码仍然保留了这个限制。然后看这行代码：
this.queue = new Object[initialCapacity];这里创建了一个新的Object数组，作为PriorityQueue的底层存储结构。前面分析过，PriorityQueue的底层并不是链表，而是数组。这个数组会按照完全二叉堆的规则来组织元素。例如，如果传入的初始容量是10：
PriorityQueue<Integer> queue = new PriorityQueue<>(10, null);那么底层大致相当于创建了这样一个数组：
Object[] queue = new Object[10];最后这行代码是把传入的比较器保存到当前优先队列对象中。如果comparator不为null，那么后续添加删除元素时，优先队列就会按照这个比较器来调整堆结构。
接下来是一些常用的方法，首先是添加元素的方法：
/**
* 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)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
siftUp(i, e);
size = i + 1;
return true;
}如果我们调用add方法的话本质上其实还是在调用offer方法，所以这里我们就直接讲解offer方法即可。我们先看最开始的第一段部分代码：
if (e == null)
throw new NullPointerException();这说明PriorityQueue不允许插入null元素。原因其实很简单，优先队列中的元素需要进行比较，只有能比较大小，才能判断谁的优先级更高。而null没有办法正常参与比较。另外，PriorityQueue的poll()方法在队列为空时也会返回null。如果允许插入null，就会产生歧义，到底是队列为空返回的null，还是队列中真的存了一个null元素？所以源码中直接禁止添加null。接着的代码是：
modCount++;modCount可以理解为修改次数。每次优先队列的结构发生变化，比如添加元素删除元素，modCount都会增加。它主要是给迭代器使用的。比如我们正在遍历一个优先队列时，如果队列结构被修改了，迭代器就可以通过modCount发现异常修改，从而抛出ConcurrentModificationException。通俗地说，modCount就像是一个版本号。队列每改一次，版本号就加一。迭代器遍历时会检查版本号有没有变化，如果发现版本号不对，就说明遍历过程中队列被改过。然后看下面这部分：
int i = size;
if (i >= queue.length)
grow(i + 1);这里把当前元素个数保存到变量i中。接着是扩容判断，queue.length表示底层数组的容量，size表示当前已经存放的元素个数。如果出现了这种情况：
size >= queue.length就说明底层数组已经满了，没有多余位置可以存放新元素。这时就需要调用grow方法对底层数组进行扩容：
grow(i + 1);这里传入的i + 1表示添加当前这个新元素后，至少需要这么大的容量。扩容完成之后，底层数组变大，新元素才有空间插入。最核心的是这行：
siftUp(i, e);添加元素时，PriorityQueue通常会先把新元素放到堆的最后一个位置，也就是数组的末尾位置。然后再让这个元素不断和父节点比较。如果新元素的优先级比父节点更高，就和父节点交换位置，继续往上比较，直到它找到合适的位置。这样调整之后，堆顶仍然是最小元素，优先队列的性质就被维护住了。然后元素插入完成后，需要更新当前队列中的元素数量。
既然在上面的分析过程中我们看到了siftup方法，我们接下来就看下这个方法在源码中是如何实现的：
/**
* Inserts item x at position k, maintaining heap invariant by
* promoting x up the tree until it is greater than or equal to
* its parent, or is the root.
*
* To simplify and speed up coercions and comparisons, the
* Comparable and Comparator versions are separated into different
* methods that are otherwise identical. (Similarly for siftDown.)
*
* @param k the position to fill
* @param x the item to insert
*/
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x, queue, comparator);
else
siftUpComparable(k, x, queue);
}
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;
}
这个方法本身并不直接完成调整，而是根据是否存在自定义比较器，分成两种情况处理。如果comparator != null，说明用户创建优先队列时传入了自定义比较器，此时调用：
siftUpUsingComparator(k, x, queue, comparator);
如果comparator == null，说明没有自定义比较器，就使用元素自身的自然顺序，此时调用：
siftUpComparable(k, x, queue);源码把这两种情况拆成两个方法，是为了减少每次比较时的判断和类型转换，让执行效率更高。
我们先看没有比较器的版本：
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;
}这个方法用于自然排序。第一行的代码表示把新插入的元素x强制转换成Comparable类型：
Comparable<? super T> key = (Comparable<? super T>) x;因为没有传入自定义比较器，所以元素本身必须具备比较能力。例如Integer、String这些类型本身就实现了Comparable接口，可以直接比较大小。如果元素没有实现Comparable，又没有传入比较器，那么在这里就可能出现类型转换异常。接着看循环条件：
while (k > 0)这里的k表示新元素当前准备放入的位置。为什么是k > 0呢？这是因为数组下标0是堆顶，也就是根节点。如果k == 0，说明新元素已经移动到堆顶了，上面已经没有父节点，就不需要继续调整了。然后计算父节点下标：
int parent = (k - 1) >>> 1;在数组实现的完全二叉堆中，如果当前节点下标是k，那么它的父节点下标就是：
parent = (k - 1) / 2源码中使用的是>>> 1，表示的是无符号右移一位。对于非负整数来说，右移一位的效果基本等价于除以2。所以这行代码可以简单理解为：
int parent = (k - 1) / 2;接着取出父节点元素：
Object e = es[parent];然后比较新元素和父节点：
if (key.compareTo((T) e) >= 0)
break;这里是整个siftUp的核心判断。在小顶堆中，父节点应该小于等于子节点。如果新元素 >= 父节点，说明当前已经满足小顶堆规则，不需要继续向上调整，直接break退出循环。如果新元素 < 父节点，说明新元素比父节点更小，它的优先级更高，应该继续向上移动。如果新元素比父节点更小会执行：
es[k] = e;
k = parent;这两行代码非常关键。它能够把父节点元素往下移动到当前k位置，并且新元素接下来要尝试放到父节点的位置。这里需要注意一个问题，源码并没有每次都直接交换x和父节点，而是采用了类似挖坑的方式。可以这样理解，新元素x先不急着放入数组。如果父节点比x大，就把父节点往下挪，然后空出来的位置继续向上寻找，最后找到合适位置后，再一次性把x放进去。
最后这行代码就是把新元素放到最终确定的位置。这种写法比反复交换更高效，因为它减少了赋值次数。
es[k] = key;接下来我们再看使用自定义比较器的版本，这个方法和siftUpComparable的逻辑几乎完全一样，区别只在于比较方式不同。自然排序版本和自定义比较器版本分别使用：
key.compareTo((T) e)
cmp.compare(x, (T) e)也就是说，如果用户创建优先队列时传入了比较器，那么元素之间谁优先，就由这个比较器决定。所以理论上来说，我们可以通过重写比较器接口来实现使用大根堆而非小根堆的方式：
import java.util.Comparator;
import java.util.PriorityQueue;
class Intcmp implements Comparator<Integer> {
public int compare(Integer o1, Integer o2){
return o2.compareTo(o1);
}
}
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>(new Intcmp());
pq.offer(10);
pq.offer(20);
pq.offer(30);
System.out.println(pq.peek());
}
}其运行结果如下：
这时候就说明我们是按照大根堆的方式来排序了。除此之外，我们再来看看扩容的方法：
/**
* Increases the capacity of the array.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1
/* preferred growth */);
queue = Arrays.copyOf(queue, newCapacity);
}其实这个扩容方法我们之前也讲过类似的，也写过差不多的。这个代码其实就是告诉我们说如果优先队列的容量比较小的话，我们就二倍扩容，大点的话就1.5倍扩容。
四、堆和优先队列的相关应用：
堆排序即利用堆的思想来进行排序，总共分为两个步骤，先建堆，升序建大堆，降序建小堆；然后利用堆删除思想来进行排序。建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
通过我们上面实现的代码，我们就可以很容易完成堆排序了：
public void heapSort(){
int end = usedSize - 1;
while(end > 0){
int temp = elem[end];
elem[end] = elem[0];
elem[0] = temp;
siftdown(0,end);
end--;
}
}public class Main {
public static void main(String[] args) {
int[] array = {27,15,19,18,28,34,65,49,25,37};
TestHeap testHeap = new TestHeap();
testHeap.initElem(array);
testHeap.createHeap();
testHeap.heapSort();
}
}可以看到此时完成了对elem数组的升序排序：
在堆和优先队列这部分，比较出名的问题其实就是top-K问题了，这类问题就是在问我们最大或者最小的前k个数据。大致来说，我们解决的方法有三种。如果说我们是找前k个最小的元素的话，第一种做法就是整体进行排序；第二种方法就是整体建立一个大小为N的小根堆，差不多就是下面这个意思：
class Solution {
public int[] smallestK(int[] arr, int k) {
// 参数检测
if(null == arr || k <= 0)
return new int[0];
PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
// 将数组中的元素依次放到堆中
for(int i = 0; i < arr.length; ++i){
q.offer(arr[i]);
}
// 将优先级队列的前k个元素放到数组中
int[] ret = new int[k];
for(int i = 0; i < k; ++i){
ret[i] = q.poll();
}
return ret;
}
}我们可以访问下面这个测试的链接：面试题 17.14. 最小K个数 - 力扣（LeetCode）
用我们刚才分析的思路就可以得到答案，我的代码如下：
class Solution {
public int[] smallestK(int[] arr, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int i = 0; i < arr.length; i++){
pq.offer(arr[i]);
}
int[] ret = new int[k];
for(int i = 0; i < k; i++){
ret[i] = pq.poll();
}
return ret;
}
}
该解法只是PriorityQueue的简单使用，并不是top-K最好的做法，那该如何实现？这就涉及到第三种方法了，第三种方法就是把前k个元素创建为大根堆，遍历剩下的元素和堆顶比较，如果比堆顶元素小，就删除堆顶元素，当前元素入堆。读者可以思考如何实现，我这里给出我的代码：
class Intcmp implements Comparator<Integer> {
public int compare(Integer o1, Integer o2){
return o2.compareTo(o1);
}
}
class Solution {
public int[] smallestK(int[] arr, int k) {
int[] ret = new int[k];
if(arr == null || k == 0){
return ret;
}
PriorityQueue<Integer> pq = new PriorityQueue<>(new Intcmp());
for(int i = 0; i < k; i++){
pq.offer(arr[i]);
}
for(int i = k; i < arr.length; i++){
int peekVal = pq.peek();
if(arr[i] < peekVal){
pq.poll();
pq.offer(peekVal);
}
}
for(int i = 0; i < k; i++){
ret[i] = pq.poll();
}
return ret;
}
}
总结
本文详细介绍了Java中优先队列（PriorityQueue）与堆（Heap）的概念、实现和应用。主要内容包括基本概念，优先队列是一种支持按优先级获取元素的数据结构，JDK中通过堆实现；堆分为大根堆（父节点值≥子节点）和小根堆（父节点值≤子节点），是完全二叉树结构。模拟实现，通过数组存储堆元素，演示了建堆、插入(push)和删除(poll)的核心操作；重点分析了向下调整(siftDown)和向上调整(siftUp)算法，时间复杂度为O(logN)。JDK源码分析，PriorityQueue底层使用数组存储，默认小根堆，可通过Comparator自定义排序；关键方法offer()通过siftUp维护堆性质，grow()方法实现动态扩容（小容量2倍，大容量1.5倍）。典型应用，堆排序先建堆再通过不断删除堆顶元素实现排序；Top-K问题使用大小为K的堆高效找出最大/最小的K个元素，给出两种解法对比。本文通过代码示例和复杂度分析，系统性地讲解了优先队列和堆的实现原理及使用场景，为处理优先级相关算法问题提供了实践指导。
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
7
0- 0
已为社区贡献14条内容
所有评论(0)