数据结构——优先队列
2022-02-20 本文已影响0人
小波同学
一、优先队列
优先队列顾名思义，就是优先权最大的排在队列的头部，而优先权的判断是根据对象的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 个数
- 采用上面自定义的最大堆实现
/**
* @Author: huangyibo
* @Date: 2022/2/19 18:05
* @Description: 在N个元素中选出最小的K个元素
*/
public class Solution {
public int[] getLeastNumbers(int[] arr, int k){
PriorityQueue<Integer> pq = new PriorityQueue<>();
//现将k个元素放进优先队列中
for (int i = 0; i < k; i++) {
pq.enqueue(arr[i]);
}
//数组余下的元素和pq最大的元素进行比较
for (int i = k; i < arr.length; i++) {
//如果数组元素比优先队列中最大的元素小的话
if(!pq.isEmpty() && arr[i] < pq.getFront()){
//优先队列中最大元素出队
pq.dequeue();
//将数组元素放入优先队列中
pq.enqueue(arr[i]);
}
}
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = pq.dequeue();
}
return result;
}
}
3.2 在N个元素中选出最小的K个元素
- 输入整数数组 arr ，找出其中最小的 k 个数。
- 采用java.util.PriorityQueue实现
import java.util.Collections;
import java.util.PriorityQueue;
/**
* @Author: huangyibo
* @Date: 2022/2/19 18:05
* @Description: 输入整数数组 arr ，找出其中最小的 k 个数
*/
public class Solution2 {
public int[] getLeastNumbers(int[] arr, int k){
//java.util.PriorityQueue 默认为最小堆实现
//PriorityQueue 构造函数传入Collections.reverseOrder(), 则按最大堆的逻辑进行构建
//Collections.reverseOrder() 反向比较器
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
//现将k个元素放进优先队列中
for (int i = 0; i < k; i++) {
pq.add(arr[i]);
}
//数组余下的元素和pq最大的元素进行比较
for (int i = k; i < arr.length; i++) {
//如果数组元素比优先队列中最大的元素小的话
if(!pq.isEmpty() && arr[i] < pq.peek()){
//优先队列中最大元素出队
pq.remove();
//将数组元素放入优先队列中
pq.add(arr[i]);
}
}
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = pq.remove();
}
return result;
}
}
3.3 在N个元素中选出第 k 个最大的元素
- 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
- 采用java.util.PriorityQueue实现
import java.util.PriorityQueue;
/**
* @Author: huangyibo
* @Date: 2022/2/19 18:05
* @Description: 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
*
* 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
*/
public class Solution3 {
public int findKthLargest(int[] nums, int k) {
//java.util.PriorityQueue 默认为最小堆实现
PriorityQueue<Integer> pq = new PriorityQueue<>();
//现将k个元素放进优先队列中
for (int i = 0; i < k; i++) {
pq.add(nums[i]);
}
//数组余下的元素和pq最大的元素进行比较
for (int i = k; i < nums.length; i++) {
//如果数组元素比优先队列中最小的元素大的话
if(!pq.isEmpty() && nums[i] > pq.peek()){
//优先队列中最小元素出队
pq.remove();
//将数组元素放入优先队列中
pq.add(nums[i]);
}
}
return pq.peek();
}
}
参考：
https://blog.csdn.net/love905661433/article/details/82989608
