java用数组实现优先级队列(小顶堆)
优先级队列
普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。通常采用堆数据结构来实现。
优先级队列 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。
操作:
1.往队列中添加数据
2.从队列中获取数据
优先级队列通常采用堆数据结构处理
用数组实现
插入数据:
算法:
先将数据插入到数组末尾,然后进行上浮操作,
如果父节点大于大于该子节点,则执行上浮操作,直到该节点为根节点。
//交换
private void exchange(int i,int j) {
queue[i]=queue[i]+queue[j];
queue[j]=queue[i]-queue[j];
queue[i]=queue[i]-queue[j];
}
//上浮
private void swim(int k) {
while (k > 1 && compare(k>>1, k)) {
exchange(k, k>>1);
k = k>>1;
}
}
从队列中获取数据
算法:
把数组首节点和尾节点交换,删除尾节点,队列元素个数-1,此时队列可能不满足优先队列的条件,需要执行下沉操作。
具体是先比较下沉节点的的两个子节点的元素大小,选择较小的子节点交换,反复进行此操作,直到树的叶子节点。
private void sink(int k) {
while (k<<1 <= n) {
int j = k<<1;
if (j < n && compare(j, j+1))
j++;
if (!compare(k, j))
break;
exchange(k, j);
k = j;
}
}
代码实现:
package com.itdragon.controller;
/**
* 优先级队列(小顶堆)
* @author JIA_JIAJIA
* @website http://www.jiajiajia.club
* @da2019年5月11日
*/
public class PriorityQueue {
/**
* 队列元素
*/
private int queue[];
/**
* 队列长度
*/
int n;
/**
* 循序打印数组中的值,相当于二叉树的层级遍历
*/
public void printf() {
for(int i=1;i<n+1;i++) {
System.out.print(queue[i]+" ");
}
}
/**
* 初始化队列大小
* @param size
*/
public PriorityQueue(int size) {
/**
* 初始化队列的元素数组,和队列大小
*/
queue=new int[size+1];
n=0;
}
/**
* 插入数据到队列中
* @param data
* @return
*/
public boolean insert(int data) {
/**
* 如果数组容量不够则进行扩容操作(在原来数组容量的基础上+10)
*/
if (n >= queue.length - 1)
queue=java.util.Arrays.copyOf(queue,queue.length+10);
queue[++n] = data;
swim(n);
System.out.println(isPriorityQueue());
return true;
}
/***
* 从队列中获取数据
* @return
*/
public int getDate() {
int data = queue[1];
exchange(1, n);
n--;
sink(1);
queue[n+1]=0;
if ((n > 0) && (n == (queue.length - 1) / 4))
queue=java.util.Arrays.copyOf(queue,queue.length/2);
System.out.println(isPriorityQueue());
return data;
}
/**
* 比较元素的大小,queue[i]>queue[j]返回true,queue[i]<queue[j]返回false
* @param i
* @param j
* @return
*/
public boolean compare(int i,int j) {
return queue[i]>queue[j]?true:false;
}
/**
* 交换queue中i位置和j位置的值
* @param i
* @param j
*/
private void exchange(int i,int j) {
/**
* 不用第三个变量做中间变量,交换两个整数变量的值
* 例:
* a=a+b;
* b=a-b;
* a=a-b;
* 这样a,b的值就交换了
*/
queue[i]=queue[i]+queue[j];
queue[j]=queue[i]-queue[j];
queue[i]=queue[i]-queue[j];
}
/**
* 上浮操作
* @param k 数组下标k
*/
private void swim(int k) {
/**
* 对于小顶堆,如果父节点的值大于该子节点,那么交换该节点和父节点,然后继续比较该节点与父节点...
* 直到该节点是根节点。
* 右移(>>)相当于除以2,参考 http://www.jiajiajia.club/blog/artical/200
*
* 用数组表示二叉树,有如下性质
* 子节点的下标位置>>2等于父节点的下标位置。适用于左节点和右节点。
*/
while (k > 1 && compare(k>>1, k)) {
exchange(k, k>>1);
k = k>>1;
}
}
/**
* 下沉操作
* @param k 数组下标k
*/
private void sink(int k) {
/**
* 从头结点开始,如果当前节点还有子节点,则一直判断是否还可以下沉
*/
while (k<<1 <= n) {
int j = k<<1;//
/**
* j当前节点的左节点,compare(j, j+1)是为了比较做节点大,还是右节点大
* 从而可以判断父节点是向左节点下沉,还是右节点下沉,如果是向右节点下沉则j++
*/
if (j < n && compare(j, j+1))
j++;
/**
* 如果父节点小于子节点的最小值,则下沉结束。
*/
if (!compare(k, j))
break;
/**
* 交换子节点和父节点,当前节点变为子节点,继续判断是否还可以下沉
*/
exchange(k, j);
k = j;
}
}
/**
* 判断是否满足堆得性质
* @return
*/
private boolean isPriorityQueue() {
return isPriorityQueue(1);
}
/**
* 递归遍历判断该堆是否满足堆得性质
* @param k
* @return
*/
private boolean isPriorityQueue(int k) {
if (k > n)
return true;
/**
* 左子树下标位置
*/
int left = k<<1;
/**
* 右子树下标位置
*/
int right = k<<1 + 1;
if (left <= n && compare(k, left))
return false;
if (right <= n && compare(k, right))
return false;
/**
* 递归遍历左右子树
*/
return isPriorityQueue(left) && isPriorityQueue(right);
}
}
package com.itdragon.controller;
import org.junit.Test;
/**
* @author JIA_JIAJIA
* @website http://www.jiajiajia.club
* @da2019年5月11日
*/
public class TestMain2 {
@Test
public void test() {
PriorityQueue pq=new PriorityQueue(10);
pq.insert(9);
pq.insert(8);
pq.insert(7);
pq.insert(6);
pq.insert(5);
pq.insert(4);
System.out.println(pq.getDate());
pq.printf();
}
}
猜你喜欢
weblog
1642
了解优先级队列的详细叙述请访问(java实现):java用数组实现优先级队列(小顶堆)
实验目的:
先按key优先,如果key值相等再按value.hg优先。
插入数据案例
数据结构与算法
1387
上一篇:广度优先搜索算法(bfs、广搜)java实现-数据结构和算法用邻接矩阵表示图的定点之间的关系如下图数据结构则用邻接矩阵表示为: privatestaticintmap
official
668
一个时间片内执行完,则剥夺处理机,将进程重新放到就绪队列队尾重新排队。用于作业/进程调度:用于进程调度(只有作业放入内存建立了相应的进程后,才能被分配处理机时间片)是否可抢占?若进程未能在时间片内运行完
数据结构与算法
1379
广度优先搜索算法(dfs、深搜)java实现-数据结构和算法用邻接矩阵表示图的定点之间的关系如下图的数据结构:则用邻接矩阵表示为: privatestaticintmap[][]={ {0,3,6
blog
程序员必须掌握的数据结构和算法
数据结构与算法
910
) 跳跃表(知道原理,应用,最后自己实现一遍) 并查集(建议结合刷题学习) 栈与队列 栈(必学) 队列(必学) 优先队列、堆(必学) 多级反馈队列(原理与应用) 哈希表(必学)
blog
算法-迷宫问题-广度优先搜索-队列
数据结构与算法
8373
题意的最短路径。遍历过程中需要一个数组记录遍历的过程,即经过一个节点时,需要记录下是从哪一个节点(或者是以什么方式)到达此节点的。然后利用这个过程关系,可以推出整个过程路径。代码实现:packagecl
blog
java阻塞队列实现 生产者消费者 模型
数据结构与算法
714
,放入后台的一个执行队列中,后台可以慢慢执行,当队列中没有业务数据时,使该执行线程进入等待状态。当业务数据添加进队列中后唤醒处于等待状态的执行线程,继续处理业务。一、阻塞队列的实现packagecom.
blog
数据结构+算法-堆排序
数据结构与算法
4131
作对于一个非叶子节点的下沉操作指的是:如果父节点大于子节点的任何一个节点,那么父节点就要和子节点中的最小的节点交换。代码描述 /** *下沉操作,构造小顶堆 *@paramheap元素数组 *@para
最近发表
归档
2018年11月
12
2018年12月
33
2019年01月
28
2019年02月
28
2019年03月
32
2019年04月
27
2019年05月
33
2019年06月
6
2019年07月
12
2019年08月
12
2019年09月
21
2019年10月
8
2019年11月
15
2019年12月
25
2020年01月
9
2020年02月
5
2020年03月
16
2020年04月
4
2020年06月
1
2020年07月
7
2020年08月
13
2020年09月
9
2020年10月
5
2020年12月
3
2021年01月
1
2021年02月
5
2021年03月
7
2021年04月
4
2021年05月
4
2021年06月
1
2021年07月
7
2021年08月
2
2021年09月
8
2021年10月
9
2021年11月
16
2021年12月
14
2022年01月
7
2022年05月
1
2022年08月
1
标签
算法基础
linux
前端
c++
数据结构
框架
数据库
计算机基础
储备知识
java基础
ASM
其他
深入理解java虚拟机
nginx
git
消息中间件
搜索
maven
redis
docker
dubbo
vue
导入导出
软件使用
idea插件
协议
无聊的知识
jenkins
springboot
mqtt协议
keepalived
minio
目录
祝愿神州十三飞行乘组平安归来