优先队列,顾名思义,就是一种根据一定优先级存储和取出数据的队列。它可以说是队列和排序的完美结合体,不仅可以存储数据,还可以将这些数据按照我们设定的规则进行排序。
优先队列主要方法:
void add(Object o);//进队
void offer(Object o);//进队
Object poll();//出队
Object peek();//查看队列首元素
boolean isEmpty();
int size();
在下面例子中用基于数组的堆实现优先队列,即堆中的元素保存在一个数组中。堆是一种二叉树,所遵守的唯一规律为:所有的子节点都要大于(小于)父节点。而这个数组元素的保存也是按照一定规律的:如果父结点的位置为n,那么,其对应的左右子结点的位置分别是2n+1和2n+2。
堆有两个很基本的操作:
增加一个节点,直接加在最后,然后用重新调整堆(参看
http://128kj.iteye.com/blog/1728555)
删除一个节点,则把要删除的节点与最后节点交换,然后删除交换后的节点(既最后一个点),然后重新调整堆.
class PriorityQueue {
protected Comparator comparator;
final static int ROOT_INDEX = 0;
final static int PRE_ROOT_INDEX = ROOT_INDEX - 1;
List heap;//存放队列元素的堆
public PriorityQueue() {
heap = new ArrayList();
}
public PriorityQueue(Comparator c) {
heap = new ArrayList();
comparator = c;
}
public void add(Object o) {
heap.add(o);//在最后增加一个元素
int index = heap.size() - 1;//最后一个元素的索引
while (index > ROOT_INDEX) {//在堆中加一个元素后,调整堆使其再成为一个堆
index = stepUpHeap(index);//上浮
}
}
public void offer(Object o){
add(o);
}
protected int stepUpHeap(int index) {
int parentIndex = parent(index);//获取父节点的索引
Object element = heap.get(index);
Object parent = heap.get(parentIndex);
if (compare(parent, element) > 0) { //父节点大于儿子节点,交换
heap.set(parentIndex, element);
heap.set(index, parent);
return parentIndex; // 跳到父索引
} else
return ROOT_INDEX; //不需要交换
}
//比较器
protected int compare(Object element, Object other) {
if (comparator == null) {
Comparable e = (Comparable) element;
Comparable o = (Comparable) other;
return e.compareTo(o);
} else
return comparator.compare(element, other);
}
protected int parent(int index) {
return (index - PRE_ROOT_INDEX) / 2 + PRE_ROOT_INDEX;
}
public String toString() {
return heap.toString();
}
public boolean isEmpty() {
return heap.isEmpty();
}
public int size() {
return heap.size();
}
public Object peek() throws RuntimeException{
if (isEmpty())
throw new RuntimeException();
return heap.get(0);
}
public Object poll() throws RuntimeException{//取优先队列头元素
if (isEmpty())
throw new RuntimeException();
int index = heap.size() - 1;//最后一个元素的索引
Object least;
if(index==0){
least = heap.get(index);
heap.remove(index);
}
else{
Object element = heap.get(index);//取最后一个元素
least = heap.get(ROOT_INDEX);//取堆的根元素
heap.set(ROOT_INDEX, element);//交换这两个元素
heap.set(index, least);
heap.remove(index);//删除最后一个元素
stepDownHeap(ROOT_INDEX);//下沉调整,使之再次成为堆
}
return least;
}
public void stepDownHeap(int index){
int p = index;
int c = 2*p + 1;//左子节点
Object temp = heap.get(p);//
while(c<heap.size()){
if(c+1<heap.size() && compare(heap.get(c+1),heap.get(c))<0)//右节点比左节点小
c = c + 1;//取两个儿子节点中小的一个
if(compare(temp,heap.get(c))<=0)//不需要调整了
break;
else {
heap.set(p,heap.get(c));//较小的儿子节点上浮
p = c;
c = 2*p + 1;//继续调整
}
}
heap.set(p,temp);//最后要将temp放到p
}
}
测试:
import java.util.Comparator;
public class PQTest {
public static void main(String[] args) {
Comparator c=comparableComparator();
PriorityQueue pq=new PriorityQueue(c);
pq.add(2);
pq.add(101);
pq.add(1);
System.out.println(pq.poll());
System.out.println(pq.peek());
}
static Comparator comparableComparator() {
return new Comparator() {
public int compare(Object x, Object y) {
return ((Comparable) x).compareTo(y);
}
};
}
}
运行:
D:\ex>java PQTest
1
2
下载源码
分享到:
相关推荐
主要介绍了Java基于堆结构实现优先队列功能,结合实例形式分析了java优先队列的简单定义与使用方法,需要的朋友可以参考下
优先队列(堆)6.1 模型6.2 一些简单的实现6.3 二叉堆6.3.1 结构性质6.3.2 堆序性质6.3.3 基本的堆操作6.3.4 其他的堆操作6.4 优先队列的应用6.4.1 选择问题6.4.2 事件模拟6.5 d-堆6.6 左式堆6.6.1 左式堆性质...
优先队列(堆)6.1 模型6.2 一些简单的实现6.3 二叉堆6.3.1 结构性质6.3.2 堆序性质6.3.3 基本的堆操作6.3.4 其他的堆操作6.4 优先队列的应用6.4.1 选择问题6.4.2 事件模拟6.5 d-堆6.6 左式堆6.6.1 左式堆性质6.6.2 ...
优先队列(堆)6.1 模型6.2 一些简单的实现6.3 二叉堆6.3.1 结构性质6.3.2 堆序性质6.3.3 基本的堆操作6.3.4 其他的堆操作6.4 优先队列的应用6.4.1 选择问题6.4.2 事件模拟6.5 d-堆6.6 左式堆6.6.1 左式堆性质6.6.2 ...
小结 练习 参考文献第6章 优先队列(堆) 6.1 模型 6.2 一些简单的实现 6.3 二叉堆 6.3.1 结构性质 6.3.2 堆序性质 6.3.3 基本的堆操作 6.3.4 其他的堆操作 6.4 优先队列的应用 6.4.1 选择问题...
小结 练习 参考文献第6章 优先队列(堆) 6.1 模型 6.2 一些简单的实现 6.3 二叉堆 6.3.1 结构性质 6.3.2 堆序性质 6.3.3 基本的堆操作 6.3.4 其他的堆操作 6.4 优先队列的应用 6.4.1 选择问题...
第6章 优先队列(堆) 6.1 模型 6.2 一些简单的实现 6.3 二叉堆 6.3.1 结构性质 6.3.2 堆序性质 6.3.3 基本的堆操作 6.3.4 其他的堆操作 6.4 优先队列的应用 6.4.1 选择问题 6.4.2 事件模拟 6.5 d-堆 6.6 左式堆 ...
小结 练习 参考文献 第6章 优先队列(堆) 6.1 模型 6.2 一些简单的实现 6.3 二叉堆 6.3.1 结构性质 6.3.2 堆序性质 6.3.3 基本的堆操作 6.3.4 其他的堆操作 6.4 优先队列的应用 6.4.1 选择问题 6.4.2...
寻求使用优先队列的人应该使用 Java 已经提供的类:java.util.PriorityQueue 介绍。 优先级队列是一种数据类型,其中每个元素都有一个与之关联的“优先级”。 在优先级队列中,优先级较高的元素在优先级较低的元素...
17.3 ADT优先队列的堆实现 502 17.4 堆排序 504 第18章 字典及其实现 511 18.1 ADT字典 512 18.2 可能的实现 517 18.2.1 ADT字典的基于数组的有序实现 519 18.2.2 ADT字典的二叉查找树实现 521 18.3 选择实现...
我正在考虑使用现有的斐波那契堆的开源实现的具有二元堆和优先级队列的简单优先队列和斐波那契堆类型实现。 我在这个实验中的目标是展示不同实现的强度,并调查现有开源斐波那契堆实现的性能。 所有的理论知识都...
优先队列 树 均衡 红黑树 AVL树 八叉树 非平衡 二叉树 二进制搜索树 B树 特里 到目前为止,下面的主题/问题已涵盖在内。 1.琴弦 2.数组 3.链表 4.堆叠 列表中的简单堆栈 基于数组的实现 基于LinkedList的实现 ...
java lru leetcode 数组 & 链表 & 字符串 题号 题目链接 本仓库题解代码 ...简单 ...简单 ...简单 ...简单 ...简单 ...简单 ...简单 ...简单 ...简单 ...简单 ...简单 ...简单 ...简单 ...简单 ...简单 ...优先队列 (第K大数据,优先级队列:最小堆
了解队列的实现,链队列和循环队列,注意链队列中的出队列操作 算法: 注意循环队列空和满的条件(A,P) 会运用栈和队列 5. 串 掌握相关概念 会运用串的基本操作(C),特别是Concat(),Substring(),Index()和...
优先队列 必须知道的算法: 归并排序 快速排序 分布式文件系统 BFS 前序、中序、后序树遍历 二分查找 当前实现的数据结构: Java: 链表 二叉搜索树 队列 堆 特里 最大堆 Python: (进行中)链表 C: (进行中)...
前K个高频元素,学习优先队列和堆相关知识 2018/07/05:完成线段树相关问题 2018/07/06:Leetcode完成字段数Trie相关习题 2018/07/07:Leetcode完成204素数、405 16进制转换问题、415 字符串相加10进制、67 字符串...
往往实现静态队列,我们都是做成循环队列 链队列 循环队列 双端队列 Java中的Deque接口 顺序表 链表 单链表 链表是离散存储线性结构 优点 空间没有限制 插入删除元素很快 ...
•一个类可以实现一个或多个接口,继承使用extends关键字,实现接口则使用implements关键字。 实现接口 •一个类实现了一个或多个接口之后,这个类必须完全实现这些接口里所定义的全部抽象方法(也就是...