java用数组实现优先级队列(小顶堆)

硅谷探秘者 3552 0 2

优先级队列

        普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。通常采用堆数据结构来实现。

        优先级队列 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。

操作:

        1.往队列中添加数据

        2.从队列中获取数据

        优先级队列通常采用堆数据结构处理

        用数组实现


文档下载:java数组实现优先级队列(小顶堆).docx

插入数据:

算法:

    先将数据插入到数组末尾,然后进行上浮操作,

    如果父节点大于大于该子节点,则执行上浮操作,直到该节点为根节点。

//交换
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;
             }
         }

s.png


从队列中获取数据

算法:

        把数组首节点和尾节点交换,删除尾节点,队列元素个数-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;
             }
         }

dd.png

代码实现:

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 1869 了解的详细叙述请访问(java):java验目的: 按key,如果key值相等再按value.hg。 插入据案例
数据结构与算法 1613 上一篇:广度搜索算法(bfs、广搜)java-据结构和算法邻接矩阵表示图的定点之间的关系如下图据结构则邻接矩阵表示为: privatestaticintmap
official 855 一个时间片内执行完,则剥夺处理机,将进程重新放到就绪尾重新排于作业/进程调度:于进程调度(只有作业放入内存建立了相应的进程后,才能被分配处理机时间片)是否可抢占?若进程未能在时间片内运行完
数据结构与算法 1608 广度搜索算法(dfs、深搜)java-据结构和算法邻接矩阵表示图的定点之间的关系如下图的据结构:则邻接矩阵表示为: privatestaticintmap[][]={ {0,3,6
数据结构与算法 1124 ) 跳跃表(知道原理,应,最后自己一遍) 并查集(建议结合刷题学习) 栈与 栈(必学) (必学) (必学) 多反馈(原理与应) 哈希表(必学)
数据结构与算法 8526 题意的最短路径。遍历过程中需要一个记录遍历的过程,即经过一个节点时,需要记录下是从哪一个节点(或者是以什么方式)到达此节点的。然后利这个过程关系,可以推出整个过程路径。代码:packagecl
数据结构与算法 858 ,放入后台的一个执行中,后台可以慢慢执行,当中没有业务据时,使该执行线程进入等待状态。当业务据添加进中后唤醒处于等待状态的执行线程,继续处理业务。一、阻塞packagecom.
数据结构与算法 4275 作对于一个非叶子节点的下沉操作指的是:如果父节点大于子节点的任何一个节点,那么父节点就要和子节点中的最的节点交换。代码描述 /** *下沉操作,构造 *@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月  3 2022年09月  2 2022年10月  2
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。