TA的每日心情 | 开心 2021-3-12 23:18 |
---|
签到天数: 2 天 [LV.1]初来乍到
|
优先队列,顾名思义,就是一种根据一定优先级存储和取出数据的队列。它可以说是队列和排序的完美结合体,不仅可以存储数据,还可以将这些数据按照我们设定的规则进行排序。
优先队列主要方法:
void add(Object o);//进队
void offer(Object o);//进队
Object poll();//出队
Object peek();//查看队列首元素
boolean isEmpty();
int size();
在下面例子中用基于数组的堆实现优先队列,即堆中的元素保存在一个数组中。
堆是一种二叉树,所遵守的唯一规律为:所有的子节点都要大于(小于)父节点。而这个数组元素的保存也是按照一定规律的:如果父结点的位置为n,那么,其对应的左右子结点的位置分别是2n+1和2n+2。
堆有两个很基本的操作:
增加一个节点,直接加在最后,然后用重新调整堆.
删除一个节点,则把要删除的节点与最后一个节点交换,然后删除交换后的节点(既最后一个节点),然后重新调整堆.
假如有下面这样一个堆:

这时候,有一个元素1要添加进来,这时候应该怎么办呢?第一步,将元素添加到堆的最后一个位置:
第二步,将新加入的元素与其父结点的值进行比较,若新结点的值比其父结点的值要小(就像这个例子一样),那么,交换两个结点的值,重复第二步,直到形成一个小顶堆:

这样,一个新的小顶堆诞生了!
然后就是从堆中删除一个元素了,假设在这个新的小顶堆中,我们打算删除堆顶元素:
第一步,将这个1删掉,假设其结点上当前没有值:
第二步,将最后一个结点的值放在根的位置,然后进行下滤,比较一下两个子结点的值与根节点的值,将堆顶元素与其子结点中较小的交换,然后重复:
 
知道了这些基本的原理,对数据量更大的增加和删除也应该是触类旁通了吧。
有人会质疑堆中除堆顶元素之外的其他元素的顺序问题:
比如这里为什么4会放在5的右边兄弟结点上,这明显是受了二叉查找树的影响,因为堆对我们来说,一般只有堆顶元素有用,因此只要保证堆顶元素是最小的就行了(对小顶堆)。
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
}
}
[/code]
测试:
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);
}
};
}
}
[/code]
运行:
D:ex>java PQTest
1
2
源码下载:http://file.javaxxz.com/2014/12/4/000759015.zip |
|