专栏：Java数据结构秘籍
个人主页：
目录
一、优先级队列常用接口
1.1. 优先级队列的特性
1.2. 优先级队列的使用
1.3. 最小K个数
二、堆的应用
2.1. 堆排序
一、优先级队列常用接口
1.1. 优先级队列的特性
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列， PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的。注意，使⽤PriorityQueue时必须导⼊PriorityQueue所在的包。
import java.util.PriorityQueue;
从上图中我们可以看出，PriorityQueue实现了AbstractQueue接口，我们来看一下PriorityQueue的源码里面继承了AbstractQueue类。而AbstractQueue类里面继承AbstractCollection类和实现了Queue接口。
public class PriorityQueue<E> extends AbstractQueue<E>implements java.io.Serializable {
public abstract class AbstractQueue<E>extends AbstractCollection<E>implements Queue<E>插入元素：
import java.util.PriorityQueue;public class Test {public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>();queue.offer(10);queue.offer(4);queue.offer(7);}
}
offer的源码如下，从下面的逻辑中可以看出，它的向上调整是一个一个实现的，而不是直接去调整一个数组，所以下面的时间复杂度是。
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;}注意事项：
- PriorityQueue中放置的元素必须要能够⽐较⼤⼩，不能插⼊⽆法⽐较⼤⼩的对象，否则会抛出 ClassCastException异常。要想实现就必须实现Compareble的接口。
class Student{}public class Test {public static void main(String[] args) {PriorityQueue<Student> queue = new PriorityQueue<>();queue.offer(new Student());}
}
- 不能插⼊null对象，否则会抛出NullPointerException。
public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>();queue.offer(null);}
- “没有容量限制”，可以插⼊任意多个元素，其内部可以⾃动扩容。
- 插入和删除的时间复杂度为
1.2. 优先级队列的使用
| 构造器 | 功能 |
PriorityQueue() | 创建一个空的优先级队列，默认容量为11 |
| PriorityQueue(int initialCapacity) | 创建一个初始容量为initialCapacity的优先级队列 |
| PriorityQueue(Collection<? extends E> c) | 用一个集合来创建优先级队列 |
import java.util.ArrayList;
import java.util.PriorityQueue;public class Solution {public static void main(String[] args) {PriorityQueue<Integer> queue1 = new PriorityQueue<>();PriorityQueue<Integer> queue2 = new PriorityQueue<>();ArrayList<Integer> list = new ArrayList<>();list.add(4);list.add(3);list.add(2);list.add(1);PriorityQueue<Integer> queue3 = new PriorityQueue<>(list);System.out.println(queue3);}
}
//PriorityQueue所实现的成员变量，默认容量为11
private static final int DEFAULT_INITIAL_CAPACITY = 11;PriorityQueue<Character> queue3 = new PriorityQueue<>(list);如果优先级队列里的泛型不匹配，就会出现报错。我们该如何知道这里的类型呢？我们来看一下PriorityQueue构造方法的源码：Collection可以接受任何类型，后面可以继承它本身的类型或者是它的子类。而上面的Collection接收为ArrayList，E接收为Character，就会产生报错。
public PriorityQueue(Collection<? extends E> c)| 方法名 | 功能 |
| boolean offer(E e) | 插入元素，成功返回true。如果插入元素为空，抛出异常 |
| E peek() | 获取优先级最高的元素 |
| E poll() | 移除优先级最高的元素并返回 |
| int size() | 获取有效元素的个数 |
| void clear() | 清空 |
| boolean isEmpty() | 检查优先级队列是否为空 |
public class Solution {public static void main(String[] args) {PriorityQueue<Integer> queue1 = new PriorityQueue<>();queue1.offer(27);queue1.offer(15);queue1.offer(19);queue1.offer(28);queue1.offer(34);queue1.offer(49);System.out.println(queue1);System.out.println(queue1.isEmpty());System.out.println(queue1.size());System.out.println(queue1.peek());System.out.println(queue1.poll());queue1.clear();}
}public class Solution {public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>();queue.offer(10);queue.offer(5);}
}默认情况下，PriorityQueue队列是⼩堆，如果需要大堆需要用户提供比较器。我们来看一下offer里面sifup所实现的源码。当我们传入一个10的时候，通过Comparable进行强转，在传入数组。方法里面的k作为数组的下标，每传入一个元素，进行比较，而里面的k调用了compareTo接口
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;} private void siftUp(int k, E x) {if (comparator != null)siftUpUsingComparator(k, x, queue, comparator);elsesiftUpComparable(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;}我们来看一下Integer里面的源码，在Structure里面找到compare(int ,int)，因为10>5，进不来上面的循环，就可以走下面的代码，再把0下标给到5元素，从而实现小根堆。
public int compareTo(Integer anotherInteger) {return compare(this.value, anotherInteger.value);} public static int compare(int x, int y) {return (x < y) ? -1 : ((x == y) ? 0 : 1);}如果没有进入if语句，则相当于进行交换。我们如果想实现大根堆，就要走break这条语句。源码的Integer写死了，我们无法在这里进行修改，此时就需要用到比较器。
import java.util.Comparator;
import java.util.PriorityQueue;class BigTmp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
}public class Solution {public static void main(String[] args) {PriorityQueue<Integer> queue = new PriorityQueue<>(new BigTmp());queue.offer(10);queue.offer(5);System.out.println(queue.peek());}
}
1.3. 最小K个数
第一种解法，我们可以利用冒泡排序，排完序之后，找前k个数；第二种解法，利用小根堆，找出前k个数。
class Solution {public int[] smallestK(int[] arr, int k) {PriorityQueue<Integer> queue = new PriorityQueue<>();for (int i = 0; i < arr.length; i++) {queue.offer(arr[i]);}int[] ret = new int[k];for (int i = 0; i < k; i++) {ret[i] = queue.poll();}return ret;}
}除此之外，还有第三种解法，就是利用大根堆。先建立一个大小为k的大根堆，从数组的第k+1个元素开始遍历数组，如果数组元素比堆顶元素小，则交换，遍历结束之后，大根堆里的元素就是最小k个数。
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;public class Solution {public int[] smallestK(int[] arr, int k){PriorityQueue<Integer> queue = new PriorityQueue<>();for (int i = 0; i < arr.length; i++) {queue.offer(arr[i]);}for (int i = k; i < arr.length; i++) {int val = queue.peek();if(val > arr[i]){queue.poll();queue.offer(arr[i]);}}int[] ret = new int[k];for (int i = 0; i < k; i++) {ret[i] = queue.poll();}return ret;}public static void main(String[] args) {Scanner in = new Scanner(System.in);while(in.hasNextInt()){int size = in.nextInt();int[] arr = new int[size];for (int i = 0; i < size; i++) {arr[i] = in.nextInt();}int k = in.nextInt();Solution solution = new Solution();int[] ret = solution.smallestK(arr,k);System.out.println(Arrays.toString(ret));}}
}二、堆的应用
2.1. 堆排序
如果我们要使用堆排序的思想，是采用大根堆还是小根堆呢？如果采用小根堆，那么栈顶元素就是最小的，只需要弹出依次元素即可，空间复杂度也会变大，因为还需要额外的数组来接收弹出的元素。如果采用大根堆，我们的思路是将堆顶元素与最后一个元素进行交换，再把这棵树调整为大根堆。
完整代码实现：
public class MyHeap {public int[] elem;public int usedSize;public MyHeap() {elem = new int[10];}public void Initial(int[] array) {for (int i = 0; i < array.length; i++) {elem[i] = array[i];usedSize++;}}public void CreateHeap() {for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {ShiftDown(parent, usedSize);}}private void ShiftDown(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]) {swap(parent,child);parent = child;child = 2 * parent + 1;} else {break;}}}private void swap(int i, int j) {int tmp = elem[i];elem[i] = elem[j];elem[j] = tmp;}public void HeapSort(){int end = usedSize - 1;while (end > 0) {swap(0,end);ShiftDown(0,end);end--;}}
}public class Test {public static void main(String[] args) {int[] array = {27, 15, 19, 18, 28, 34, 65, 49, 25, 37};MyHeap heap = new MyHeap();heap.Initial(array);heap.CreateHeap();heap.HeapSort();System.out.println();}
}