优先级队列就是在堆的基础上进行改造,那么什么是堆,又什么是优先级队列呢? 我们一起来看看吧!
堆就是堆中某个节点的值总是不大于或不小于其父节点的值。
堆总是完全二叉树。
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];
}
@Override
public int compare(Integer o1,Integer o2) {
return o2.compareTo(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.com)
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) | 用一个集合创建优先级队列 |
优先级队列扩容说明:
求前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> {
@Override
public int compare(Integer a, Integer b){
return b.compareTo(a);
}
}
小编能力有限,欢迎大家指出错误哦~
这篇博客如果对你有帮助,给博主一个免费的点赞以示鼓励,欢迎各位🔎点赞👍评论收藏⭐,谢谢!!!