一、优先队列 优先队列顾名思义，就是优先权最大的排在队列的头部，而优先权的判断是根据对象的compare方法比较获取的，保证根节点的优先级一定比子节点的优先级大。所以放入到
一、优先队列
优先队列顾名思义，就是优先权最大的排在队列的头部，而优先权的判断是根据对象的compare方法比较获取的，保证根节点的优先级一定比子节点的优先级大。所以放入到优先队列的元素要么实现了Comparable接口，要么在创造这个优先队列时，指定一个比较器。
普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。通常采用堆数据结构来实现。
二、代码实现
- 优先队列通常采用堆数据结构来实现，而堆数据结构通常采用数组为底层数据结构实现。
2.1 动态数组的底层实现
/** * @Author: huangyibo * @Date: 2021/12/25 17:29 * @Description: 动态数组实现 */ public class Array<E> { private E[] data; private int size; public Array(){ this(10); } public Array(int capacity){ this.data = (E[]) new Object[capacity]; this.size = 0; } public Array(E[] arr){ this.data = (E[]) new Object[arr.length]; for (int i = 0; i < arr.length; i++) { data[i] = arr[i]; } this.size = arr.length; } /** * 获取数组中元素个数 * @return */ public int getSize(){ return size; } /** * 获取数组容量 * @return */ public int getCapacity(){ return data.length; } /** * 返回数组是否为空 * @return */ public boolean isEmpty(){ return size == 0; } /** * 数组尾部新增元素 * @param e */ public void addLast(E e){ add(size, e); } /** * 数组头部新增元素 * @param e */ public void addFirst(E e){ add(0, e); } /** * 在指定位置插入元素 * @param index * @param e */ public void add(int index, E e){ if(index < 0 || index > size){ throw new IllegalArgumentException("AddLast failed. require index >=0 and index <= size"); } if(size == data.length){ //扩容 resize(2 * data.length); } for(int i = size - 1; i >= index; i --){ data[i + 1] = data[i]; } data[index] = e; size ++; } /** * 数组扩容 * @param newCapacity */ private void resize(int newCapacity){ E[] newData = (E[])new Object[newCapacity]; for (int i = 0; i < size; i++) { newData[i] = data[i]; } data = newData; } /** * 获取指定索引位置的值 * @param index * @return */ public E get(int index){ if(index < 0 || index >= size){ throw new IllegalArgumentException("Get failed. index is illegal."); } return data[index]; } /** * 替换指定索引位置的值 * @param index * @param e */ public void set(int index, E e){ if(index < 0 || index >= size){ throw new IllegalArgumentException("Set failed. index is illegal."); } data[index] = e; } /** * 数组是否包含元素e * @param e * @return */ public boolean contains(E e){ for (int i = 0; i < size; i++) { if(data[i].equals(e)){ return true; } } return false; } /** * 查找数组中元素e所在的索引,不存在元素e,返回-1 * @param e * @return */ public int find(E e){ for (int i = 0; i < size; i++) { if(data[i].equals(e)){ return i; } } return -1; } /** * 删除数组中index位置的元素, 并返回删除的元素 * @param index * @return */ public E remove(int index){ if(index < 0 || index >= size){ throw new IllegalArgumentException("Remove failed. index is illegal."); } E ret = data[index]; for (int i = index; i < size - 1; i++) { data[i] = data[i + 1]; } size --; data[size] = null; if(size == data.length / 4 && data.length / 2 != 0){ //当数组长度缩小为原数组的4分之一的时候才进行数组的缩容， //缩小为原数组的2分之一，预留空间，防止有数据添加导致扩容浪费性能 resize(data.length / 2); } return ret; } /** * 删除数组中第一个元素 * @return */ public E removeFirst(){ return remove(0); } /** * 删除数组中最后一个元素 * @return */ public E removeLast(){ return remove(size - 1); } /** * 从数组中删除元素e * @param e */ public void removeElement(E e){ int index = find(e); if(index != -1){ remove(index); } } /** * 数组索引元素交换 * @param i * @param j */ public void swap(int i, int j){ if(i < 0 || i >= size || j < 0 || j >= size){ throw new IllegalArgumentException("Index is illegal."); } E temp = data[i]; data[i] = data[j]; data[j] = temp; } @Override public String toString(){ StringBuilder sb = new StringBuilder(); sb.append(String.format("Array: size = %d, capacity = %d\n",size,data.length)); sb.append("["); for (int i = 0; i < size; i++) { sb.append(data[i]); if(i != size - 1){ sb.append(", "); } } sb.append("]"); return sb.toString(); } }2.2 最大堆——使用动态数组作为底层实现
/** * @Author: huangyibo * @Date: 2022/2/17 22:54 * @Description: 最大堆 完全二叉树，父亲节点大于等于孩子节点，采用数组表示 */ public class MaxHeap<E extends Comparable<E>> { //这里使用数组作为底层实现 private Array<E> data; public MaxHeap(){ data = new Array<>(); } public MaxHeap(int capacity){ data = new Array<>(capacity); } /** * 将任意数组整理成堆的形状 * @param arr */ public MaxHeap(E[] arr){ data = new Array<>(arr); //从最后一个叶子节点的父节点开始进行siftDown操作,不断循环 for(int i = parent(arr.length - 1); i >= 0; i --){ siftDown(i); } } /** * 返回堆中的元素个数 * @return */ public int getSize(){ return data.getSize(); } /** *堆是否为空 * @return */ public boolean isEmpty(){ return data.isEmpty(); } /** * 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引 * @param index * @return */ private int parent(int index){ if(index == 0){ throw new IllegalArgumentException("index-0 doesn't have parent."); } return (index - 1) / 2; } /** * 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引 * @return */ private int leftChild(int index){ return index * 2 + 1; } /** * 回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引 * @param index * @return */ private int rightChild(int index){ return index * 2 + 2; } /** * 向堆中添加元素 * @param e */ public void add(E e){ data.addLast(e); //当前元素在数组中的索引为 data.getSize() - 1 //比较当前元素和其父亲节点的元素，大于父亲节点元素则交换位置 siftUp(data.getSize() - 1); } /** * k索引元素比父节点元素大，则交换位置，不断循环 * @param k */ private void siftUp(int k){ //k > 0 并且k索引元素比父节点元素大，则交换位置，不断循环 while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0){ data.swap(parent(k), k); k = parent(k); } } /** * 查看堆中最大元素 * @return */ public E findMax(){ if(data.getSize() == 0){ throw new IllegalArgumentException("Can not findMax when heap is empty."); } return data.get(0); } /** * 取出堆中最大元素 * @return */ public E extractMax(){ //获取堆中最大元素 E ret = findMax(); //堆中最开始的元素和最后元素交换位置 data.swap(0,data.getSize() - 1); //删除堆中最后一个元素 data.removeLast(); //0索引元素比左右孩子节点元素小，则交换位置，不断循环 siftDown(0); return ret; } /** * k索引元素比左右孩子节点元素小，则交换位置，不断循环 * @param k */ private void siftDown(int k){ while (leftChild(k) < data.getSize()){ //获取k索引的左孩子的索引 int j = leftChild(k); //j + 1 < data.getSize() if(j + 1 < data.getSize() && //如果右孩子比左孩子大 data.get(j + 1).compareTo(data.get(j)) > 0){ //最大孩子的索引赋值给j j = rightChild(k); } //此时data[j]是leftChild和rightChild中的最大值 if(data.get(k).compareTo(data.get(j)) >= 0){ //如果父亲节点大于等于左右孩子节点，跳出循环 break; } //如果父亲节点小于左右孩子节点(中的最大值)，交换索引的值 data.swap(k, j); //交换完成之后，将j赋值给K,重新进入循环 k = j; } } /** * 取出堆中最大元素，并且替换成元素e * @param e * @return */ public E replace(E e){ //获取堆中的最大值 E ret = findMax(); //用新添加的元素替换最大的元素 data.set(0, e); //0索引元素比左右孩子节点元素小，则交换位置，不断循环 siftDown(0); return ret; } }2.3 队列的抽象接口
public interface Queue<E> { /** * 队列的容量 * @return */ int getSize(); /** * 队列是否为空 * @return */ boolean isEmpty(); /** * 向队列中添加元素 * @param e */ void enqueue(E e); /** * 向队列取出元素 * @return */ E dequeue(); /** * 查看队列第一个元素 * @return */ E getFront(); }2.4 优先队列——基于最大堆实现
/** * @Author: huangyibo * @Date: 2022/2/19 17:52 * @Description: 优先队列：基于最大堆实现 */ public class PriorityQueue<E extends Comparable<E>> implements Queue<E> { private MaxHeap<E> maxHeap; public PriorityQueue(){ maxHeap = new MaxHeap<>(); } @Override public int getSize() { return maxHeap.getSize(); } @Override public boolean isEmpty() { return maxHeap.isEmpty(); } @Override public E getFront() { return maxHeap.findMax(); } @Override public void enqueue(E e) { maxHeap.add(e); } @Override public E dequeue() { return maxHeap.extractMax(); } }三、java中的priorityqueue
在Java中也实现了自己的优先队列java.util.PriorityQueue，与我们自己写的不同之处在于，Java中内置的为最小堆，然后就是一些函数名不一样，底层还是维护了一个Object类型的数组，大家可以戳戳看有什么不同，另外如果想要把最小堆变成最大堆可以给PriorityQueue传入自己的比较器。
3.1 在N个元素中选出最小的K个元素
- 输入整数数组 arr ，找出其中最小的 k 个数
- 采用上面自定义的最大堆实现
3.2 在N个元素中选出最小的K个元素
- 输入整数数组 arr ，找出其中最小的 k 个数。
- 采用java.util.PriorityQueue实现
3.3 在N个元素中选出第 k 个最大的元素
- 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
- 采用java.util.PriorityQueue实现
参考： https://blog.csdn.net/love905661433/article/details/82989608
https://www.cnblogs.com/wmyskxz/p/9301021.html