在现实的生活工作中,有许多情况下都要处理有序的元素,但又不要求全部有序,再或者不要求一次就将它们全部排序,这种情况下一种叫“优先队列”的算法就派上了用场。比如说,不要求全排序一个大数据集合的数据,或内存一次装不下整个数据集,但是要求获得最大或最小的M有序的数组。
本节我们会学习基于二叉堆数据结构的优先队列的实现。优先队列最重要的操作就是删除最大元素和插入元素两种操作。数据结构二叉堆能够很好地实现优先队列的基本操作。在二叉堆的数组中,每个元素都要保证大于等于两外2个特定位置的元素。(当一颗二叉的每个节点都大于等于它的两个孩子节点时,被称为堆有序。)
用数组(堆)实现的完全二叉树,结构严格有灵活,能实现对数级别的插入元素和删除最大元素的操作。代码如下:
/**
* 基于数组(堆)实现的完全二叉树的优先队列
* @author jacky
*
*/
public class MaxPriorityQueue<Key extends Comparable<Key>>{
//基于堆的完全二叉树
private Key[] pq;
//将数据存储在pq[1 ... N]中,pq[0]不使用
private int size = 0;
/**
* 默认创建一个大小为Integer.MAX_VALUE的队列
*/
public MaxPriorityQueue(){
pq = (Key[])new Comparable[Integer.MAX_VALUE];
}
public MaxPriorityQueue(int max){
pq = (Key[])new Comparable[max + 1];
}
/**
* 向优先队列中添加元素,将元素添加到数组的pq[++size]
* @param v
*/
public void push(Key v){
pq[++size] = v;
//由下至上的对有序化
swim(size);
}
/**
* 由下至上的对有序化:循环比较pq[size/2]和pq[k],若pq[size/2] < pq[k]则
* 交换数据,知道k = 1
* @param k
*/
private void swim(int k){
int cmp = k/2;
while(k > 1 && less(cmp,k)){
exch(cmp,k);
cmp = k/2;
}
}
/**
* 将最大的元素从优先队列中取出
* @return
*/
public Key delMax(){
Key max = pq[1];//从根节点得到最大的元素
exch(1,size--);//将其和最后一个节点交换
pq[size+1] = null;//防止越界
sink(1);//由上到下恢复对的有序性
return max;
}
/**
* 由上到下的对有序化
* @param k
*/
private void sink(int k){
while(2 * k <= size){
int j = 2 * k;
if(j < size && less(j,j+1)){
j++;
}else if(!less(k,j)){
break;
}
exch(k,j);
k = j;
}
}
private boolean less(int i,int j){
return pq[i].compareTo(pq[j]) < 0;
}
private void exch(int i,int j){
Key tmp = pq[i];
pq[i] = pq[j];
pq[j] = tmp;
}
public boolean isEmpty(){
return size == 0;
}
public int size(){
return size;
}
}
分享到:
相关推荐
编写优先队列数据(priority_queue)类型,优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除.在最小优先队列(min priority queue)中,查找操作...
优先队列-java可以选择属性和升序降序
用C语言实现一个优先队列;压缩文件中包括三个文件:1.HeapQueue.h优先队列源代码,2.main.cpp测试主函数;3.HeapQueue.h使用说明
可嵌入到matlab中的优先队列,包括pq_create,插入,删去,取顶端,
提出了基于优先队列的时变网络最短路径算法,能克服传统最短路径算法难以对时变网络求解最短路径的缺陷。提出的时间窗选择策略能够在算法求解过程中为节点选择合适的时间窗以降低路径长度,从而求得精确解。进一步地...
堆排序实现优先队列,利用优先队列做了一个小程序,有兴趣看看
数据结构优先队列,是一个简易版优先队列,输入数据及权值可以对其进行插入,删除等操作。
数据结构,课程设计优先队列实验报告 用最大堆实现的优先队列
C语言 堆 优先队列
优先队列求无序整数序列中第k小的元素.cpp
本文提出一种基于K 叉树的优先队列的算法, 通过建立K 叉树堆的数据结构, 从n 个元素中 得到m 个元素的优先队列, 其算法的最坏时间复杂度为O (2m log2n + 2n ). 本算法是基于二叉树堆 的优先队列算法的推广, 并具有较...
分支限界法中的优先队列式分支限界法解装载问题
c++实现的批处理作业调度问题·优先队列式分支限界法·回溯法包括了FlowShop和make类模板,有测试数据data
数据结构 基于链表实现的优先队列 Cpp文件
采用优先队列式分枝限界法求解0/1背包问题,算法设计第五章,描述的很清晰,里面有完整代码,由于害怕你弄混,所以完整运行的代码参考我的博客文章即可
该算法基于Java语言,对算法设计中的优先队列进行了实现,本人能力有限,如有bug请多指教
本程序主要由堆来实现优先队列的数据结构,主要有优先队列的删除,插入。算法复杂度为logn
优先队列课程设计
用头文件封装的优先队列!可以进行插入、查找、删除等操作!