浏览 7065 次
|
精华帖 (0) :: 良好帖 (0) :: 新手帖 (5) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2008-05-25
java库里的PriorityQueue无法满足我，它不能固定容量，不遍历（遍历后就无序了），它的排序因字是从小到大（虽然可以用Comparator来反转大小顺序）。我所要的是可以固定容量（在一大堆数据通信中选择最大或最小的几个数时很有用），可遍历（不是一个个poll()）。 package net.blogjava.chenlb.util;
import java.util.AbstractQueue; import java.util.Comparator; import java.util.Iterator; /** * @param <E> * 容量capacity大于0,最多只能添加capacity个,多出的被删除掉.<br/> * 删除时根据{@link Comparable}或{@link Comparator} 和 desc * 如果comparator==null时使用Comparable<br/> * non-thread safe * @author chenlb 2008-4-23 下午11:31:06 */ public class TopPriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable { private static final long serialVersionUID = 1L; private int size; private LinkedItem head; private LinkedItem last; private int top; //top>0后,容量有限制 private Comparator<? super E> comparator; private boolean desc; //降序 /** * 容量无限制,升序. */ public TopPriorityQueue() { this(0, null, false); } /** * 容量无限制, * @param desc true为降序. */ public TopPriorityQueue(boolean desc) { this(0, null, desc); } /** * 容量无限制,升序,用comparator排序 */ public TopPriorityQueue(Comparator<? super E> comparator) { this(0, comparator, false); } /** * 容量无限制,用comparator排序 * @param desc true为降序 */ public TopPriorityQueue(Comparator<? super E> comparator, boolean desc) { this(0, comparator, desc); } /** * 容量限制为capacity.超出容量限制的,会删除优先级最小(队尾). */ public TopPriorityQueue(int capacity) { this(capacity, null, false); } public TopPriorityQueue(int capacity, boolean desc) { this(capacity, null, desc); } public TopPriorityQueue(int capacity, Comparator<? super E> comparator) { this(capacity, comparator, false); } public TopPriorityQueue(int capacity, Comparator<? super E> comparator, boolean desc) { head = new LinkedItem(); last = head; top = capacity; this.comparator = comparator; this.desc = desc; } @Override public Iterator<E> iterator() { // TODO 迭代器 return new It(head); } @Override public int size() { return size; } public boolean offer(E o) { // TODO 添加到适当的位置 if(o == null) { throw new IllegalArgumentException("不能添加值为null的!"); } LinkedItem temp = new LinkedItem(o); /*last.next = temp; temp.prev = last;*/ if(last == head) { //第一个 last.next = temp; temp.prev = last; last = temp; } else { LinkedItem tempPrev = last; if(comparator != null) { while(tempPrev!=null && tempPrev != head) { int r = comparator.compare(tempPrev.data, temp.data); if(desc) { r = 0 - r; } if(r == 1) { //tempPrev > temp //重置,继续向前找 tempPrev = tempPrev.prev; } else { //找到插入的位置 break; } } } else if(o instanceof Comparable) { //用Comparable while(tempPrev!=null && tempPrev != head) { Comparable<E> tPrev = (Comparable<E>) tempPrev.data; int r = tPrev.compareTo(temp.data); if(desc) { r = 0 - r; } if(r == 1) { //tempPrev > temp //重置,继续向前找 tempPrev = tempPrev.prev; } else { //找到插入的位置 break; } } } if(tempPrev != null) { //插入 if(tempPrev == last) { //后面添加的 last = temp; } temp.next = tempPrev.next; if(tempPrev.next != null) { tempPrev.next.prev = temp; } tempPrev.next = temp; temp.prev = tempPrev; } } size++; if(top > 0 && size > top) { //去掉优先级最小的 tail(); } return true; } /** * 从栈底去除 */ public E tail() { if(last == head) { return null; } LinkedItem laster = last; last = last.prev; last.next = null; laster.prev = null; size--; return laster.data; } public E peek() { // TODO 取得栈顶值 LinkedItem first = head.next; if(first != null) { return first.data; } return null; } public E poll() { // TODO 从栈顶去除 LinkedItem first = head.next; if(first != null) { head.next = first.next; if(first.next != null) { first.next.prev = head; } size--; return first.data; } return null; } private class It implements Iterator<E> { LinkedItem curr; public It(LinkedItem curr) { super(); this.curr = curr; } public boolean hasNext() { if(curr != null && curr.next != null) { return true; } return false; } public E next() { curr = curr.next; E d = curr.data; return d; } public void remove() { curr.prev.next = curr.next; if(curr.next != null) { curr.next.prev = curr.prev; } size--; } } /** * @param <E> * 链结点. * @author chenlb 2008-5-4 下午04:48:17 */ private class LinkedItem { LinkedItem prev; E data; LinkedItem next; public LinkedItem() { } public LinkedItem(E o) { this.data = o; } } } 声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2008-05-25
或许已经有第三方的库类似实现，各位朋友推荐下。
|
| 返回顶楼 | |
|
发表时间：2008-05-25
现在我用的是插入排序,链表的.
|
| 返回顶楼 | |
|
发表时间：2008-06-12
取决于你需要解决的问题，插入排序用TreeSet。
插入和移除手段可以多样，真正要关注的是否需要多线程访问。 |
| 返回顶楼 | |
|
发表时间：2008-06-12
引用 于是，在有空的时间里写了一下。内容是一个双向链表（带头的，头不作保存数据），用插入排序。个人认为一个个添加的用插入排序效果比较好。从队尾到队头找合适的插入位置，是稳定的排序。
这样来看，这个就是一个排序的双向链表而已。当然，由于有了排序，也可以当作优先队列来用。只是要看数据的规模，这种双向链表的插入在数据量比较大的情况下，需要做的比较次数太多了。 算法书上通常会提到用 heap 结构来实现优先队列，主要是考虑在大规模的数据量情况，heap 是一种性能比较好的结构，在优先队列的使用场景中比二叉树更好一点。 |
| 返回顶楼 | |
|
发表时间：2008-07-01
lucene 2.32 中用来实现查询结果存放缓存的时候 在代码里有一个这样的实现可以去看下得
org.apache.lucene.util.PriorityQueue 这个是抽象类，里面也有它的实现 |
| 返回顶楼 | |
