队列（Queue）是一种先进先出的数据结构，是一个实现了Collection接口的接口，在JDK中自带了非常多的实现类，比如PriorityQueue、LinkedList，ConcurrentLinkedQueue，LinkedBlockingQueue等。其中 PriorityQueue 比较特殊，称为优先级队列，通过堆实现，它的作用是能保证每次取出的元素都是队列中权值最小的（或最大的）。PriorityQueue是默认是通过小顶堆来实现优先级队列的（每次取出最小值），也可以指定Comparator自定义实现队列的优先级。
- 堆排序参考：java排序算法之堆排序
1、PriorityQueue及相关概念
1.1 PriorityQueue特点
队列是遵循先进先出（First-In-First-Out）模式的，PriorityQueue 是一种特殊的队列（优先级队列），能够对其中的元素进行排序，在Java1.5中引入并作为 Java Collections Framework 的一部分。PriorityQueue 默认是通过小顶堆来实现优先级队列的，也可以指定Comparator自定义实现队列的优先级。可以用一棵完全二叉树来表示。优先队列的作用是能保证每次取出的元素都是队列中权值最小的（Java的优先队列每次取最小元素，C++的优先队列每次取最大元素）。特点如下：
- 通过堆实现，是基于优先堆的一个无界队列，这个优先队列中的元素可以默认自然排序或者通过提供的Comparator（比较器）在队列实例化的时排序。（不指定Comparator时默认为最小堆），优先队列的头是基于自然排序或者Comparator排序的最小元素。
- 能够对其中的元素进行排序，支持基本类型的包装类及自定义类，对于基本类型的包装类，优先队列默认按升序排列。
- 底层用数组实现，但是数组大小可以动态增加，容量无限。
- 堆排序只能保证根是最大（最小）的，整个堆并不是有序的。
- 优先队列不允许存储空值（null元素）。
- 不支持non-comparable（不可比较）的对象，比如用户自定义的类。优先队列要求使用Java Comparable和Comparator接口给对象排序。
- PriorityQueue是非线程安全的，Java提供了PriorityBlockingQueue（实现BlockingQueue接口）用于Java多线程环境。
- 优先队列的大小是不受限制的，但在创建时可以指定初始大小。当我们向优先队列增加元素的时候，队列大小会自动增加。
- 插入方法（offer()、poll()、remove() 、add() 方法）时间复杂度为O(log(n)) ；remove(Object) 和 contains(Object) 时间复杂度为O(n)；检索方法（peek、element 和 size）时间复杂度为常量。
- 方法iterator()中提供的迭代器并不保证以有序的方式遍历优先级队列中的元素。如果需要按顺序遍历，可用Arrays.sort(pq.toArray())。
- 可以在构造函数中指定如何排序。
上图中我们给每个元素按照层序遍历的方式进行了编号，仔细观察可以发现父节点和子节点的编号是有联系的，更确切的说父子节点的编号之间有如下关系：
leftNo = parentNo*2+1
rightNo = parentNo*2+2
parentNo = (nodeNo-1)/2
通过上述三个公式，可以轻易计算出某个节点的父节点以及子节点的下标。这也就是为什么可以直接用数组来存储堆的原因。
1.2 大顶堆与小顶堆
堆是一种非线性结构，是一种特殊的逻辑结构，堆可以使用数组来实现，把堆看作一个数组，也可以被看作一个完全二叉树，通俗来讲，堆其实就是利用完全二叉树的结构来维护一个数组，但堆并不一定是完全二叉树。堆在内存中实际的物理结构是一个顺序数组。通过堆排序算法可以将无序堆经O(logn)时间排序为一个大顶堆或小顶堆，从而快速获取最大值和最小值。
-
完全二叉树是一种每一层都是从左往右放值直到把该层放满才会增长至更深层的结构。
-
堆的数组到堆结构的映射关系满足：数组中第i个元素的左孩子为第
2*i+1的元素，右孩子为第2*i+2的元素，父节点为第(i-1)/2（取整数位，0位的父节点是自己）的元素。
所谓大顶堆通俗意义上来讲就是大的数放顶上，小的数放下面、也就是降序。所以需要保证每一个父节点都大于他的两个子节点（即任何一非叶节点满足：Key[i]>=Key[2i+1]&&key>=key[2i+2]）。
- 大顶堆即对于堆中任何一颗子树来说，该子树的最大值一定是其根节点。（大顶堆堆顶为堆中最大的值）
小顶堆和大顶堆相反，小的数放上面，大的数放下面，也就是升序、所以需要保证每一个父节点都小于他的两个子节点（即任何一非叶节点满足：Key[i]<=key[2i+1]&&Key[i]<=key[2i+2] ）。
- 小顶堆即对于堆中任何一颗子树来说，该子树的最小值一定是其根节点。（小顶堆堆顶为堆中最小的值）
使用PriorityQueue改造大小顶堆非常便捷：
- 构造小顶堆：
PriorityQueue small=new PriorityQueue<>();
- 构造大顶堆：
PriorityQueue small=new PriorityQueue<>(Collections.reverseOrder());
1.3 堆排序思想
利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序队列中选择最大记录(最小记录)变得简单。
堆排序的基本思想：将待排序序列构造成一个堆（根据升序降序需求选择大顶堆或小顶堆），此时，整个序列的最大值/最小值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值/最小值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次大值/次小值。如此反复执行，便能得到一个有序序列了。具体步骤如下：
- 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
- 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆/小顶堆，此堆为初始的无序区；
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。
不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
2、常用方法解析
Queue接口中比较常用的接口add(e)，offer(e)，poll()，peek()方法，其中add和offer方法的区别是add失败会抛出异常，offer方法失败返回false，有些实现类add方法直接调用offer方法。poll和peek的区别就是poll删除第一个元素并返回，peek直接返回第一个元素不删除。以下基于JDK 1.8讲解常用方法。
2.1 构造方法
PriorityQueue()
使用默认的初始容量（11）创建一个 PriorityQueue，并根据其自然顺序来排序其元素（使用 Comparable）。
PriorityQueue(int initialCapacity)
使用指定的初始容量创建一个 PriorityQueue，并根据其自然顺序来排序其元素（使用 Comparable）。
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
使用指定的初始容量创建一个 PriorityQueue，并根据指定的比较器comparator来排序其元素。
PriorityQueue(Collection<? extends E> c)
创建一个还有Collection集合中的元素的PriorityQueue。
PriorityQueue(PriorityQueue<? extends E> c)
创建包含 PriorityQueue优先级队列中的元素的PriorityQueue。
PriorityQueue(SortedSet<? extends E> c)
创建一个 PriorityQueue指定排序集中的元素的PriorityQueue。
2.2 add()和offer()
add(E e)和offer(E e)的语义完全相同，都是向优先队列中插入元素，只是Queue接口规定二者对插入失败时的处理不同，前者在插入失败时抛出异常，后则则会返回false。而对于PriorityQueue这两个方法其实没什么差别。add()方法内部是调用的offer()，所以两个方法没啥区别。
//offer(E e)
public boolean offer(E e) {
if (e == null)//不允许放入null元素
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);//自动扩容
size = i + 1;
if (i == 0)//队列原来为空，这是插入的第一个元素
queue[0] = e;
else
siftUp(i, e);//调整
return true;
}
上述代码中，扩容函数grow()类似于 ArrayList 里的grow()函数，就是再申请一个更大的数组，并将原数组的元素复制过去，这里不再赘述。需要注意的是siftUp(int k, E x)方法，该方法用于插入元素x并维持堆的特性。
//siftUp()
private void siftUp(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2，这里要注意下标是从0开始保证了这里的正确性
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)//调用比较器的比较方法，如果x>=e，break
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
新加入的元素x可能会破坏小顶堆的性质，因此需要进行调整。调整的过程为：从k指定的位置开始，将x逐层与当前点的parent进行比较并交换，直到满足 x >= queue[parent] 为止。注意这里的比较可以是元素的自然顺序，也可以是依靠比较器的顺序。
2.3 element()和peek()
element()和peek()的语义完全相同，都是获取但不删除队首元素，也就是队列中权值最小的那个元素，二者唯一的区别是当方法失败时前者抛出异常，后者返回null。根据小顶堆的性质，堆顶那个元素就是全局最小的那个；由于堆用数组表示，根据下标关系，0下标处的那个元素既是堆顶元素。所以直接返回数组0下标处的那个元素即可。
//peek()
public E peek() {
if (size == 0)
return null;
return (E) queue[0];//0下标处的那个元素就是最小的那个
}
2.4 remove(Object o)
remove()和poll()方法的语义也完全相同，remove(Object o)方法用于删除队列中跟o相等的某一个元素（如果有多个相等，只删除一个），该方法不是Queue接口内的方法，而是Collection接口的方法。由于删除操作会改变队列结构，所以要进行调整；又由于删除元素的位置可能是任意的，所以调整过程比其它函数稍加繁琐。具体来说，remove(Object o)可以分为2种情况：
- 删除的是最后一个元素。直接删除即可，不需要调整。
- 删除的不是最后一个元素，从删除点开始以最后一个元素为参照调用一次siftDown()即可，这里就是删除顶部元素的一般体现。此处不再赘述。
//remove(Object o)
public boolean remove(Object o) {
//通过遍历数组的方式找到第一个满足o.equals(queue[i])元素的下标
int i = indexOf(o);
if (i == -1)
return false;
int s = --size;
if (s == i) //情况1
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);//情况2
......
}
return true;
}
2.4 poll()
poll()方法是获取并删除队首元素，与remove的区别是当方法失败时前者抛出异常，后者返回null。由于删除操作会改变队列的结构，为维护小顶堆的性质，需要进行必要的调整。
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];//0下标处的那个元素就是最小的那个
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);//调整
return result;
}
上述代码首先记录0下标处的元素，并用最后一个元素替换0下标位置的元素，之后调用siftDown()方法对堆进行调整，最后返回原来0下标处的那个元素（也就是最小的那个元素）。重点是siftDown(int k, E x)方法，该方法的作用是从k指定的位置开始，将x逐层向下与当前点的左右孩子中较小的那个交换，直到x小于或等于左右孩子中的任何一个为止。
//siftDown()
private void siftDown(int k, E x) {
int half = size >>> 1;
while (k < half) {
//首先找到左右孩子中较小的那个，记录到c里，并用child记录其下标
int child = (k << 1) + 1;//leftNo = parentNo*2+1
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)// 找到左右孩子中较小的
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;//然后用c取代原来的值
k = child;
}
queue[k] = x;
}
2.5 其他方法
boolean add(E e) 将指定的元素插入到此优先级队列中。
void clear() 从此优先级队列中删除所有元素。
boolean contains(Object o) 如果此队列包含指定的元素，则返回 true 。
Iterator<E> iterator() 返回此队列中的元素的迭代器。
boolean offer(E e) 将指定的元素插入到此优先级队列中。
E peek() 检索但不删除此队列的头，如果此队列为空，则返回 null 。
E poll() 检索并删除此队列的头，如果此队列为空，则返回 null 。
boolean remove(Object o) 从该队列中删除指定元素的单个实例（如果存在）。
int size() 返回此集合中的元素数。
Spliterator<E> spliterator() 在此队列中的元素上创建late-binding和失败快速 Spliterator 。
Object[] toArray() 返回一个包含此队列中所有元素的数组。
<T> T[] toArray(T[] a) 返回一个包含此队列中所有元素的数组; 返回的数组的运行时类型是指定数组的运行时类型。
Comparator<? super E> comparator() 返回用于为了在这个队列中的元素，或比较null如果此队列根据所述排序natural ordering的元素。
3、实际应用例子
3.1 求数组中前k个最小的数字
利用优先队列 PriorityQueue 求数组中前k个最小的数字，时间复杂度：O（nlogk），如输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
package com.kz.example.algorithm.demo;
import java.util.PriorityQueue;
// 利用 优先队列PriorityQueue 求数组中前k个最小的数字，时间复杂度：O（nlogk）
// 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
// 示例 1：
// 输入：arr = [3,2,1], k = 2
// 输出：[1,2] 或者 [2,1]
// 示例 2：
// 输入：arr = [0,1,2,1], k = 1
// 输出：[0]
public class LeastNumber {
/**
* 在数组中找出最小的K个数
* @param arr 数组
* @param k 数量
* @return
*/
public static int[] getLeastNumbers(int[] arr, int k) {
if(arr == null || k <= 0 || k > arr.length) {
return new int[]{};
}
PriorityQueue<Integer> pQueue = new PriorityQueue();//默认小顶堆
for (int i : arr) {
pQueue.add(i);
}
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = pQueue.poll();
}
return result;
}
public static void main(String[] args) {
int[] arr = {2, 34, 55, 22, 11};
int k = 4;
int[] arr2 = getLeastNumbers(arr, k);
for(int a: arr2) {
System.out.println(a);
}
}
}
3.2 求数组中前k个最大的数字
package com.kz.example.algorithm.demo;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
// 利用 优先队列PriorityQueue 求数组中前k个最大的数字，时间复杂度：O（nlogk）
// 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是4、5、6、7。
// 示例 1：
// 输入：arr = [4,6,7], k = 2
// 输出：[6,7] 或者 [7,6]
// 示例 2：
// 输入：arr = [0,1,2,1], k = 1
// 输出：[2]
public class MaximalNumber {
/**
* 在数组中找出最大的K个数
*
* @param arr 数组
* @param k 数量
* @return
*/
public static int[] getMaximalNumbers(int[] arr, int k) {
if (arr == null || k <= 0 || k > arr.length) {
return new int[]{};
}
PriorityQueue<Integer> pQueue = new PriorityQueue(Collections.reverseOrder());//大顶堆
for (int i : arr) {
pQueue.add(i);
}
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = pQueue.poll();
}
return result;
}
/**
* 在数组中找出最大的K个数
*
* @param arr 数组
* @param k 数量
* @return
*/
public static int[] getMaximalNumbers2(int[] arr, int k) {
int[] result = {};
if (arr == null || k > arr.length || k <= 0) {
return result;
}
//大顶堆o2 - o1 小顶堆o1 - o2
PriorityQueue<Integer> pQueue = new PriorityQueue<>(arr.length, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for (int i : arr) {
pQueue.add(i);
}
result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = pQueue.poll();
}
return result;
}
public static void main(String[] args) {
int[] arr = {2, 34, 55, 22, 11};
int k = 4;
int[] arr2 = getMaximalNumbers(arr, k);
for (int a : arr2) {
System.out.println(a);
}
int[] arr3 = getMaximalNumbers2(arr, k);
for (int a : arr3) {
System.out.println(a);
}
}
}
3.3 自定义类型优先队列
我们有一个用户类Customer，它没有提供任何类型的排序。当我们用它建立优先队列时，应该为其提供一个比较器对象。
package com.kz.example.algorithm.demo;
public class Customer {
private int id;
private String name;
public Customer(int i, String n){
this.id=i;
this.name=n;
}
public int getId() {
return id;
}
public String getName() {
return name;
}
}
使用Java随机数来生成随机用户对象。对于自然排序，我们使用Integer对象，这也是一个封装过的Java对象。而自定义Customer类实现了Comparator接口的Java匿名类，并且实现了基于id的比较器。如果不实现Comparator，在建立customerPriorityQueue时会抛出ClassCastException。
package com.kz.example.algorithm.demo;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
public class CustomerPriorityQueue {
public static void main(String[] args) {
//优先队列自然排序示例
Queue<Integer> integerPriorityQueue = new PriorityQueue<>(7);
Random rand = new Random();
for (int i = 0; i < 7; i++) {
integerPriorityQueue.add(new Integer(rand.nextInt(100)));
}
for (int i = 0; i < 7; i++) {
Integer in = integerPriorityQueue.poll();
System.out.println("Processing Integer:" + in);
}
//优先队列使用自定义类型示例
Queue<Customer> customerPriorityQueue = new PriorityQueue<>(7, idComparator);
addDataToQueue(customerPriorityQueue);
pollDataFromQueue(customerPriorityQueue);
}
//匿名Comparator实现
public static Comparator<Customer> idComparator = new Comparator<Customer>() {
@Override
public int compare(Customer c1, Customer c2) {
return (int) (c1.getId() - c2.getId());
}
};
//用于往队列增加数据的通用方法
private static void addDataToQueue(Queue<Customer> customerPriorityQueue) {
Random rand = new Random();
for (int i = 0; i < 7; i++) {
int id = rand.nextInt(100);
customerPriorityQueue.add(new Customer(id, "Pankaj " + id));
}
}
//用于从队列取数据的通用方法
private static void pollDataFromQueue(Queue<Customer> customerPriorityQueue) {
while (true) {
Customer cust = customerPriorityQueue.poll();
if (cust == null) break;
System.out.println("Processing Customer with ID=" + cust.getId());
}
}
}
3.4 自定义堆排序
实际中我们进行堆排序是为了取得一定条件下的最大值或最小值，例如：需要在100个数中找到10个最大值，因此我们定义一个大小为10的堆，把100中的前十个数据建立成小顶堆（堆顶最小），然后从100个数据中的第11个数据开始与堆顶比较，若堆顶小于当前数据，则把堆顶弹出，把当前数据压入堆顶，然后把数据从堆顶下移到一定位置即可，
package com.kz.example.algorithm.demo;
import java.util.Scanner;
public class HeapSort {
static int[] arr;//堆数组，有效数组
public HeapSort(int m) {
arr = new int[m];
}
static int m = 0;
static int size = 0;//用来标记堆中有效的数据
public void addToSmall(int v) {
//int[] a = {16,4,5,9,1,10,11,12,13,14,15,2,3,6,7,8,111,222,333,555,66,67,54};
//堆的大小为10
//arr = new int[10];
if (size < arr.length) {
arr[size] = v;
add_sort(size);
//add_sort1(size);
size++;
} else {
arr[0] = v;
add_sort1(0);
}
}
public void printSmall() {
for (int i = 0; i < size; i++) {
System.out.println(arr[i]);
}
}
public void del() {
size--;
arr[0] = arr[9];
add_sort1(0);
}
public void Small(int index) {
if (m < arr.length) {
add_sort(index);
m++;
} else {
add_sort1(index);
m++;
}
}
public void add_sort(int index) {//小顶堆，建堆
/**
* 父节点坐标：index
* 左孩子节点：index*2
* 右孩子节点：index*2+1
* 若数组中最后一个为奇数则为 左孩子
* 若数组中最后一个为偶数则为 右孩子
* 若孩子节点比父节点的值大，则进行值交换，若右孩子比左孩子大则进行值交换
*
*/
int par;
if (index != 0) {
if (index % 2 == 0) {
par = (index - 1) / 2;
if (arr[index] < arr[par]) {
swap(arr, index, par);
add_sort(par);
}
if (arr[index] > arr[par * 2]) {
swap(arr, index, par * 2);
if (arr[index] < arr[par]) {
swap(arr, index, par);
}
add_sort(par);
}
} else {
par = index / 2;
if (arr[index] < arr[par]) {
swap(arr, index, par);
add_sort(par);
}
if (arr[index] < arr[par * 2 + 1]) {
swap(arr, index, par * 2 + 1);
if (arr[index] < arr[par]) {
swap(arr, index, par);
}
add_sort(par);
}
}
}
}
public void add_sort1(int index) {//调整小顶堆
/**
* 调整自顶向下
* 只要孩子节点比父节点的值大，就进行值交换，
*/
int left = index * 2;
int right = index * 2 + 1;
int max = 0;
if (left < 10 && arr[left] < arr[index]) {
max = left;
} else {
max = index;
}
if (right < 10 && arr[right] < arr[max]) {
max = right;
}
if (max != index) {
swap(arr, max, index);
add_sort1(max);
}
}
// 交换元素位置
private void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}
public static void main(String args[]) {
Scanner scan = new Scanner(System.in);
System.out.println("(小顶堆)请输入堆大小：");
int m = scan.nextInt();
HeapSort test = new HeapSort(m);
int[] a = {16, 4, 5, 9, 1, 10, 11, 12, 13, 14, 15, 2, 3, 6, 7, 8};
for (int i = 0; i < a.length; i++) {
test.addToSmall(a[i]);
}
test.printSmall();
test.del();
test.printSmall();
scan.close();
}
}
评论区