优先级队列"/>
PriorityQueue优先级队列
前言
优先级队列就是在堆的基础上进行改造,那么什么是堆,又什么是优先级队列呢?
我们一起来看看吧!
目录
前言
一、堆
(一)堆的创建
(二)堆的插入
(三)堆的删除
(四)模拟实现堆
二、优先级队列
(一)常用方法:
(二)常考点
结语
一、堆
堆就是堆中某个节点的值总是不大于或不小于其父节点的值。
堆总是完全二叉树。
Java底层的堆是顺序表,按照层序遍历的规则存储数据。
堆分为小根堆和大根堆。
1.小根堆(又名最小堆):
就是堆中某个节点的值总是不小于其父节点的值。
例如:
2.大根堆(又名最大堆):
就是堆中某个节点的值总是不大于其父节点的值。
例如:
以创建最小堆为例,给出的数据顺序是: 5、3、6、7、4、2.
(一)堆的创建
首先,根据给出的数据顺序,创建如下二叉树:
从最后一个叶子节点开始调整(向上调整):
时间复杂度是:O(n)
(二)堆的插入
假设要插入数据0:
如果在插入数据时,堆满扩容;调整为向上调整。
时间复杂度是:O(log n)
(三)堆的删除
堆的删除一定删除的是堆顶元素。
时间复杂度是:O(log n)
(四)模拟实现堆
代码:
import java.util.Arrays;
import java.util.Comparator;class PriorityException extends RuntimeException{public PriorityException(String s){super(s);}
}public class MyPriortyQueue implements Comparator<Integer> {public int[] elem;public int usedSize;public MyPriortyQueue(int k) {elem = new int[k];}public MyPriortyQueue() {elem = new int[11];}@Overridepublic int compare(Integer o1,Integer o2) {return o2pareTo(o1);}/*** 建堆*/public void createHeap(int[] array) {for(int i = 0; i < array.length; i++){elem[i] = array[i];usedSize++;}for(int i = (usedSize-1-1)/2; i >= 0; i--){shiftDown(i,usedSize-1);}}/*** 向下调整* @param root 是每棵子树的根节点的下标* @param len 是每棵子树调整结束的结束条件* 向下调整的时间复杂度:O(logn)*/private void shiftDown(int root,int len) {int child = root*2+1;while(child < len){if(child+1<len && compare(elem[child],elem[child+1])>0){child++;}if(compare(elem[root],elem[child])>0){int tmp = elem[root];elem[root] = elem[child];elem[child] = tmp;root = child;child = root*2+1;}else{break;}}}/*** 入队:仍然要保持是大根堆* @param val*/public void push(int val) {if(isEmpty()){elem[0] = val;}else{elem[usedSize] = val;}usedSize++;shiftUp(usedSize-1);}/*** 向上调整* 默认除了需要调整的地方外,其余都是已经调整好了的*/private void shiftUp(int child) {int parent = (child-1)/2;while(child > 0){if(compare(elem[parent],elem[child])>0){int tmp = elem[parent];elem[parent] = elem[child];elem[child] = tmp;child = parent;parent = (child-1)/2;}else{break;}}}public boolean isFull() {return usedSize == elem.length;}/*** 出队【删除】:每次删除的都是优先级高的元素* 仍然要保持是大根堆*/public void pollHeap() throws PriorityException{if(isEmpty()){throw new PriorityException("pollHeap::队列无元素,删除失败");}elem[0] = elem[usedSize-1];usedSize--;shiftDown(0, usedSize-1);}public boolean isEmpty() {return usedSize == 0;}/*** 获取堆顶元素* @return*/public int peekHeap() throws PriorityException{if(isEmpty()){throw new PriorityException("peekEmpty::队列无元素,获取失败");}return elem[0];}public static void main(String[] args) {MyPriortyQueue p = new MyPriortyQueue();int[] arr = {2,4,2,5,7,9,5,3};p.createHeap(arr);System.out.println("+=========创建一个堆========+");System.out.println(Arrays.toString(p.elem));p.push(10);System.out.println("+=========入一个值========+");System.out.println(Arrays.toString(p.elem));System.out.println("+=========输出堆顶========+");System.out.println(p.peekHeap());p.pollHeap();System.out.println("+=========删除堆顶=======+");System.out.println(Arrays.toString(p.elem));}
}
代码链接在GitHub:堆_练习模拟实现2 · Yjun6/DataStructrue@98faae5 (github)
二、优先级队列
PriorityQueue<Integer> p = new PriorityQueue<>();
(一)常用方法:
boolean offer(E e) | 插入元素e,成功插入返回true;会自动扩容;如果e为空,会抛出异常 |
E peek() | 获取优先级队列最高的元素;若队列为空,返回null |
E poll() | 移除优先级队列最高的元素;若队列为空,返回null |
int size() | 获取有效元素个数 |
void clear() | 清空 |
boolean isEmpty() | 判断是否为空 |
关于创建优先级队列的方法:
PriorityQueue() | 初始容量为11,默认无比较器 |
PriorityQueue(int k) | 初始容量为k,k>0 |
PriorityQueue(Collection<? extend E> c) | 用一个集合创建优先级队列 |
优先级队列扩容说明:
- 如果容量小于64,按照2倍扩容;
- 如果容量大于等于64,按照1.5倍扩容;
- 如果容量超过 MAX_ARRAY_SIZE,按照 MAX_ARRAY_SIZE 进行扩容。
(二)常考点
求前k个最大值、前k个最小值、第k个最大值、第k个最小值……
面试题 17.14. 最小K个数 - 力扣(Leetcode)
代码:
class Solution {public int[] smallestK(int[] arr, int k) {if(arr == null || k == 0) return new int[k];Comp comp = new Comp();PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(comp);//求大根堆for(int i = 0; i < k; i++){priorityQueue.offer(arr[i]);}for(int i = k; i < arr.length; i++){if(arr[i] < priorityQueue.peek()){priorityQueue.poll();priorityQueue.offer(arr[i]);}}int[] str = new int[priorityQueue.size()];for(int i = 0; i < str.length; i++){str[i] = priorityQueue.poll();}return str;}
}class Comp implements Comparator<Integer> {@Overridepublic int compare(Integer a, Integer b){return bpareTo(a);}
}
结语
小编能力有限,欢迎大家指出错误哦~
这篇博客如果对你有帮助,给博主一个免费的点赞以示鼓励,欢迎各位🔎点赞👍评论收藏⭐,谢谢!!!
更多推荐
PriorityQueue优先级队列
发布评论