Java PriorityQueue with fixed size

这个问题来源于StackOverFlow：
http://stackoverflow.com/questions/1846225/java-priorityqueue-with-fixed-size

为方便各位阅读，我把楼主的问题贴出来：

引用

Hi folks,

I am calculating a large number of possible resulting combinations of an algortihm. To sort this combinations I rate them with a double value und store them in PriorityQueue. Currently, there are about 200k items in that queue which is pretty much memory intesive. Acutally, I only need lets say the best 1000 or 100 of all items in the list. So I just started to ask myself if there is a way to have a priority queue with a fixed size in Java. I should behave like this: Is the item better than one of the allready stored? If yes, insert it to the according position and throw the element with the least rating away.

Does anyone have an idea? Thanks very much again!

Marco

令人大跌眼镜的Best Answer居然是：

List<Double> list = new ArrayList<Double>();
...
list.add(newOutput);
Collections.sort(list);
list = list.subList(0, 1000);

这种方法没有从根本上解决内存消耗的问题，绝对是Performence Killer。

正巧，这位朋友遇到的问题我这之前在做图像搜索时也遇到类似的问题。图片识别引擎会将匹配到的每一张图片都打上分数，越高说明相似度越大；最后输出的时候可能只需要其中的前十张就可以了。

先看一下wiki上关于优先级队列的定义：

引用

A priority queue is an abstract data type in computer programming.It is exactly like a regular queue or stack data structure, but additionally, each element is associated with a "priority".

• stack: elements are pulled in last-in first-out-order (e.g. a stack of papers)
• queue: elements are pulled in first-come first-served-order (e.g. a line in a cafeteria)
• priority queue: elements are pulled highest-priority-first (e.g. cutting in line, or VIP service).

一个标准的优先级队列至少要实现以下操作：

• insertWithPriority: add an element to the queue with an associated priority
• pullHighestPriorityElement: remove the element from the queue that has the highest priority, and return it

为Priority Queue添加指定的容量限制，就是发帖这位朋友所要的Sized Priority Queue
JDK1.6将优先级队列也加入了Collection中，但是很遗憾，没有提供Sized Priority Queue，我的实现如下：

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

public class SizedPriorityQueue<T> {
	private int mSize;
	private boolean mGetLowest = true;
	private LinkedList<T> mList;
	private LinkedList<Double> mPriorities;
	private Comparator<T> mComparator;
	
	/**
	 * Creates a fixed size priority queue that only tracks N values
	 *  
	 * @param size - The maximum number of values to store
	 * @param getLowest - false means to track the highest N values, 
	 * 						true means to track the lowest N values
	 */
	public SizedPriorityQueue(int size, boolean getLowest) {
		mSize = size;
		mGetLowest = getLowest;
		mList = new LinkedList<T>();
		mPriorities = new LinkedList<Double>();
	}
	
	/**
	 * Creates a fixed size priority queue with an explicit comparator for the
	 * class that you want to track. This can be handy if the generic class you
	 * have doesn't implement {@link Comparable}
	 * 
	 * @param size - The maximum number of values to store
	 * @param getLowest - false means to track the highest N values, 
	 * 						true means to track the lowest N values
	 * @param comparator - Explicit comparator for the classyou are tracking
	 */
	public SizedPriorityQueue(int size, boolean getLowest, Comparator<T> comparator) {
		this(size,getLowest);
		mComparator = comparator;
	}
	
	/**
	 * Add a value to the current list of items, it will be inserted into the
	 * correct position in the list if it has a higher priority than the other
	 * items, otherwise it will be dropped
	 * 
	 * @param value
	 */
	public void add(T value){
		if ( mComparator == null ) throw new RuntimeException("Trying to use priority queue default add without comparator defined");
		int index = 0;
		for ( T val : mList ){
			//int comparison = val.compareTo(value);
			int comparison = mComparator.compare(val,value);
			if ( mGetLowest && comparison < 0 ) break;
			if ( !mGetLowest && comparison > 0 ) break;
			index++;
		}
		
		if ( index < mSize - 1)
			mList.add(index,value);
		
		if ( mList.size() > mSize ) mList.removeLast();
	}
	
	/**
	 * Add a value to the current list of items, it will be inserted into the
	 * correct position in the list if it has a higher priority than the other
	 * items, otherwise it will be dropped
	 * 
	 * @param value
	 */
	public void add(T value, double priority){
		int index = 0;

		for ( double val : mPriorities ){
			double comparison = priority - val;
			
			if ( mGetLowest && comparison < 0 ) break;
			if ( !mGetLowest && comparison > 0 ) break;
			index++;
		}
		
		if ( index < mSize - 1) {
			mList.add(index,value);
			mPriorities.add(index,priority);
		}
		
		if ( mList.size() > mSize ){
			mList.removeLast();
			mPriorities.removeLast();
		}
	}
	
	/**
	 * Like any ohter queue, it returns the top 
	 * @return
	 */
	public T pop(){
		if ( mPriorities.size() > 0 )
			mPriorities.pop();
		return mList.pop();
	}
	
	/**
	 * Just returns the top in the list, doesn't remove it
	 * 
	 * @return
	 */
	public T poll(){
		return mList.peek();
	}
	
	/**
	 * @return The size of current list
	 */
	public int size(){
		return mList.size();
	}
	
	/**
	 * Returns an ordered list of all of the scores currently held
	 * 
	 * @return
	 */
	public List<T> getAllScores(){
		return mList;
	}
	
	public static void main(String args[]){
		int numScores = 10;
		int numTopScores = 5;
		Random r = new Random(2);
		SizedPriorityQueue<Integer> queue = new SizedPriorityQueue<Integer>(numTopScores,false);
		for ( int i = 0; i < numScores; i++ ){
			double score = r.nextDouble();
			System.out.println("inserting score: " + score + ", number " + i);
			queue.add(i,score);
		}
		
		while ( queue.size() > 0 ){
			System.out.println(queue.pop());
		}
	}
}

我想，应该会对有如此需求的朋友带来一些帮助吧