優先隊列的的重載

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {

	public static void main(String[] args) {
		Queue<Integer> qi = new PriorityQueue<Integer>();

		qi.add(5);
		qi.add(2);
		qi.add(1);
		qi.add(10);
		qi.add(3);

		while (!qi.isEmpty()) {
			System.out.print(qi.poll() + ",");
		}
		System.out.println();
		System.out.println("-----------------------------");
              // 自定義的比較器,可以讓我們自由定義比較的順序 Comparator<Integer> cmp;
		cmp = new Comparator<Integer>() { 
			public int compare(Integer e1, Integer e2) {
				return e2 - e1;
			}
		};
		Queue<Integer> q2 = new PriorityQueue<Integer>(5, cmp);
		q2.add(2);
		q2.add(8);
		q2.add(9);
		q2.add(1);
		while (!q2.isEmpty()) {
			System.out.print(q2.poll() + ",");
		}

	}

}

 

轉載來自:https://my.oschina.net/leejun2005/blog/135085

1,2,3,5,10,
-----------------------------
9,8,2,1,

 

此隊列的頭是按指定排序方式的最小元素。如果多個元素都是最小值,則頭是其中一個元素——選擇方法是任意的。

隊列檢索操作 poll、remove、peek 和 element 訪問處於隊列頭的元素。
優先級隊列是無界的,但是有一個內部容量,控制着用於存儲隊列元素的數組的大小。
它總是至少與隊列的大小相同。隨着不斷向優先級隊列添加元素,其容量會自動增加。無需指定容量增加策略的細節。
注意1:該隊列是用數組實現,但是數組大小可以動態增加,容量無限。
注意2:此實現不是同步的。不是線程安全的。如果多個線程中的任意線程從結構上修改了列表, 則這些線程不應同時訪問 PriorityQueue 實例,這時請使用線程安全的PriorityBlockingQueue 類。
注意3:不允許使用 null 元素。
注意4:此實現為插入方法(offer、poll、remove() 和 add 方法)提供 O(log(n)) 時間;
為 remove(Object) 和 contains(Object) 方法提供線性時間;
為檢索方法(peek、element 和 size)提供固定時間。
注意5:方法iterator()中提供的迭代器並不保證以有序的方式遍歷優先級隊列中的元素。
至於原因可參考下面關於PriorityQueue的內部實現
如果需要按順序遍歷,請考慮使用 Arrays.sort(pq.toArray())。
注意6:可以在構造函數中指定如何排序。如:
PriorityQueue()
使用默認的初始容量(11)創建一個 PriorityQueue,並根據其自然順序來排序其元素(使用 Comparable)。
PriorityQueue(int initialCapacity)
使用指定的初始容量創建一個 PriorityQueue,並根據其自然順序來排序其元素(使用 Comparable)。
PriorityQueue(int initialCapacity, Comparator comparator)
使用指定的初始容量創建一個 PriorityQueue,並根據指定的比較器comparator來排序其元素。
注意7:此類及其迭代器實現了 Collection 和 Iterator 接口的所有可選 方法。
PriorityQueue的內部實現
PriorityQueue對元素採用的是堆排序,頭是按指定排序方式的最小元素。堆排序只能保證根是最大(最小),整個堆並不是有序的。
方法iterator()中提供的迭代器可能只是對整個數組的依次遍歷。也就只能保證數組的第一個元素是最小的。
實例1的結果也正好與此相符。

 

2、應用:求 Top K 大/小 的元素

瞭解了優先隊列之後,我們再來看它的一個應用:

在面試的時候,問到算法,Top k 的問題是經常被問到的,網上已有很多種方法可以解決,今天來看看如何使用 PriorityQueue 構造固定容量的優先隊列,模擬大頂堆,來解決 top K 小的問題。

package com.test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;

//固定容量的優先隊列,模擬大頂堆,用於解決求topN小的問題
public class FixSizedPriorityQueue<E extends Comparable> {
	private PriorityQueue<E> queue;
	private int maxSize; // 堆的最大容量

	public FixSizedPriorityQueue(int maxSize) {
		if (maxSize <= 0)
			throw new IllegalArgumentException();
		this.maxSize = maxSize;
		this.queue = new PriorityQueue(maxSize, new Comparator<E>() {
			public int compare(E o1, E o2) {
				// 生成最大堆使用o2-o1,生成最小堆使用o1-o2, 並修改 e.compareTo(peek) 比較規則
				return (o2.compareTo(o1));
			}
		});
	}

	public void add(E e) {
		if (queue.size() < maxSize) { // 未達到最大容量,直接添加
			queue.add(e);
		} else { // 隊列已滿
			E peek = queue.peek();
			if (e.compareTo(peek) < 0) { // 將新元素與當前堆頂元素比較,保留較小的元素
				queue.poll();
				queue.add(e);
			}
		}
	}

	public List<E> sortedList() {
		List<E> list = new ArrayList<E>(queue);
		Collections.sort(list); // PriorityQueue本身的遍歷是無序的,最終需要對隊列中的元素進行排序
		return list;
	}

	public static void main(String[] args) {
		final FixSizedPriorityQueue pq = new FixSizedPriorityQueue(10);
		Random random = new Random();
		int rNum = 0;
		System.out.println("100 個 0~999 之間的隨機數:-----------------------------------");
		for (int i = 1; i <= 100; i++) {
			rNum = random.nextInt(1000);
			System.out.println(rNum);
			pq.add(rNum);
		}
		System.out.println("PriorityQueue 本身的遍歷是無序的:-----------------------------------");
		Iterable<Integer> iter = new Iterable<Integer>() {
			public Iterator<Integer> iterator() {
				return pq.queue.iterator();
			}
		};
		for (Integer item : iter) {
			System.out.print(item + ", ");
		}
		System.out.println();
		System.out.println("PriorityQueue 排序後的遍歷:-----------------------------------");
		/*
		 * for (Integer item : pq.sortedList()) { System.out.println(item); }
		 */
		// 或者直接用內置的 poll() 方法,每次取隊首元素(堆頂的最大值)
		while (!pq.queue.isEmpty()) {
			System.out.print(pq.queue.poll() + ", ");
		}
	}
}

還有LA寫的代碼:

 

package util;
import java.util.*;
public class _Comparator {
	
	static Scanner sc = new Scanner(System.in);
	static class Student{
		String name;
		int age;
		public Student(String name, int age) {
			this.name = name; this.age = age;
		}
	}
	static Student[] stu = new Student[100];
	
	
	static Comparator cmp = new Comparator<Student>() {  
		@Override
		public int compare(Student o1, Student o2) {
			return o1.age - o2.age; // 按age從小到大排序
		} 
	};
	
	
	
	public static void main(String[] args) {
		
		int n = sc.nextInt();
		
		for(int i=1; i<=n; i++) {
			stu[i] = new Student(sc.next(),sc.nextInt());
		}
		
		Arrays.sort(stu,1,n+1,cmp); //按照cmp將stu[] 從1-n排序
		
		
		for(int i=1; i<=n; i++)
			System.out.println(stu[i].name+" : "+stu[i].age);
		
	}

}

嗯還有...........

package util;
import java.util.*;
public class _Comparable {
	static Scanner sc = new Scanner(System.in); 
	static class Student implements Comparable<Student>{
		String name;
		int age;
		public Student(String name,int age) {
			this.name = name;
			this.age = age;
		}
	
		@Override
		public int compareTo(Student o) {
			return this.age - o.age;
		}
	}
	
	static List<Student> list = new LinkedList<Student>();
	public void main(String[] args) {
		int n =sc.nextInt();
		while(n-- > 0) {
			list.add(new Student(sc.next(),sc.nextInt()));
		}
		Collections.sort(list);
		
		for(Student s: list) {
			System.out.println(s.name + ":" + s.age);
		}
	}	
}