Categories

Java中的PriorityQueue

前几天还预测说“大概不会再下雪了吧”,今天却又开始新一轮的大雪纷飞。正所谓“天有不测风云”啊。

看到Robin用Java交了HOJ 1062 数列极差问题 ,我正好看图形界面无聊得很,也写了一下,顺便了解了Java中的PriorityQueue。

PriorityQueue是从JDK1.5开始提供的新的数据结构接口。
如果不提供Comparator的话,优先队列中元素默认按自然顺序排列,也就是数字默认是小的在队列头,字符串则按字典序排列。

方法摘要
boolean add(E e)
将指定的元素插入此优先级队列。
void clear()
从此优先级队列中移除所有元素。
Comparator<? super E> comparator()
返回用来对此队列中的元素进行排序的比较器;如果此队列根据其元素的自然顺序进行排序,则返回 null
boolean contains(Object o)
如果此队列包含指定的元素,则返回 true
Iterator<E> iterator()
返回在此队列中的元素上进行迭代的迭代器。
boolean offer(E e)
将指定的元素插入此优先级队列。
E peek()
获取但不移除此队列的头;如果此队列为空,则返回 null
E poll()
获取并移除此队列的头,如果此队列为空,则返回 null
boolean remove(Object o)
从此队列中移除指定元素的单个实例(如果存在)。
int size()
返回此 collection 中的元素数。
Object[] toArray()
返回一个包含此队列所有元素的数组。

<T> T[]

toArray(T[] a)
返回一个包含此队列所有元素的数组;返回数组的运行时类型是指定数组的类型。

附:HOJ 1062 数列极差问题 源代码 by icycandy

358721 1062 2009-03-18 13:55:11 Accepted 0.09 s 12556 K Java 833 B Robin学Java
358729 1062 2009-03-18 14:46:25 Accepted 0.10 s 12556 K Java 999 B Joshua

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
 
public class Main
{
	public static void main(String[] args)
	{
		Scanner in = new Scanner(System.in);
 
		while (in.hasNextInt())
		{
			int n = in.nextInt();
			if (n == 0) break;
 
			PriorityQueue<integer> q1 = new PriorityQueue<integer>(n); // 小数在队列头
			PriorityQueue<integer> q2 = new PriorityQueue<integer>(n, new Comparator<integer>()// 大数在队列头
					{
						public int compare(Integer o1, Integer o2)
						{
							return o2 - o1;
						}
					});
 
			for (int i = 0; i != n; ++i)
			{
				int tmp = in.nextInt();
				q1.offer(tmp);
				q2.offer(tmp);
			}
 
			for (int i = 0; i != n - 1; ++i)
			{
				int a = q1.poll();
				int b = q1.poll();
 
				q1.offer(a * b + 1);
				a = q2.poll();
				b = q2.poll();
				q2.offer(a * b + 1);
			}
 
			System.out.println(q1.peek() - q2.peek());
		}
	}
}

3 comments to Java中的PriorityQueue

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

  

  

  

*