Java优先队列

优先队列应用场景：

  在一堆杂乱无序的数据里，尤其是当数据量特别大时，要选出最大（最小）的几个元素，那么就不必将所有数据都排序后再选择。这时需要一种合适的数据结构，能够删除最小元素和插入元素。

例如在一个有100万个数字的文件中选出最大的10个，百万整数文档链接

public static void main(String[] args) {
		//创建一个MinPQ实例，可以存放输入的最大的10个整数
        //MinPQ类的代码在下方会有介绍
        MinPQ pq = new MinPQ(10);

        //读取文件里的整数放入数组
		int[] a = In.readInts(args[0]);
		
        
        for(int i =0;i10)
				pq.delMin();
		}

        //将pq中存放的最大的10个数字放入一个栈中
		Stack stack = new Stack();
		while(!pq.isEmpty()) {
			stack.push(pq.delMin());
		}
        
        //输出栈中的数字
		for(Integer i:stack) {
			System.out.print(i+" ");
		}
	}

MinPQ的API

insert 方法

 //插入元素
	public void insert(Key key) {
        //当元素个数等于pq数组末尾索引时，将pq数组长度翻倍（通过resize方法）
		if(n==pq.length-1) resize(2*pq.length);
		
        //将插入的元素放在数组末尾，然后通过上浮实现堆有序化
        pq[++n] = key;
		swim(n);
	}

什么​​​​​​是堆，

堆可以通过上浮和下沉实现堆的有序化。

堆上浮swim的代码

   //上浮指定位点，实现堆有序化
	public void swim(int k) {
		while(k>1&&less(k,k/2)) {
			exch(k,k/2);
			k/=2;
		}	
	}

堆下沉sink的代码

	public void sink(int k) {
		while(2*k<=n) {
			int j = 2*k;
			if(j 
 
min返回最小值方法
 
    //返回最小值
	public Key min() {
		return pq[1];
	}
 
delMin删除最小值方法 
 
//删除最小值并返回
	public Key delMin() {
		Key min = pq[1];

        //交换堆顶与末尾的元素位置，然后将置换后的堆顶元素下沉
		exch(1,n--);
		pq[n+1] = null; //防止元素游离
		sink(1);       //下沉元素
		if(n<=(pq.length-1)/4) resize(pq.length/2); //当删除最小元素pq数组元素数量远小于数组长度时，将数组长度减半
		return min;
	}
 
isEmpty、size方法 
 
	public int size() {return n;}
	public boolean isEmpty() {return n==0;}
 
全源代码如下 
 

public class MinPQ>{
	private Key[] pq;
	private int n;
	
    //初始化
	MinPQ(){}
	
	MinPQ(int max){
		pq = (Key[]) new Comparable[max+1];
		n = 0;
	}

    //插入元素
	public void insert(Key key) {
        //当元素个数等于pq数组末尾索引时，将pq数组长度翻倍（通过resize方法）
		if(n==pq.length-1) resize(2*pq.length);
		
        //将插入的元素放在数组末尾，然后通过上浮实现堆有序化
        pq[++n] = key;
		swim(n);
	}
    
    //resize函数，改变数组长度
	private void resize(int max) {
		Key[] temp = (Key[]) new Comparable[max];
		for(int i =1;i<=n;i++) {
			temp[i] = pq[i];
		}
		pq = temp;
	}

    //返回最小值
	public Key min() {
		return pq[1];
	}

    //删除最小值并返回
	public Key delMin() {
		Key min = pq[1];

        //交换堆顶与末尾的元素位置，然后将置换后的堆顶元素下沉
		exch(1,n--);
		pq[n+1] = null; //防止元素游离
		sink(1);       //下沉元素
		if(n<=(pq.length-1)/4) resize(pq.length/2); //当删除最小元素pq数组元素数量远小于数组长度时，将数组长度减半
		return min;
	}

    //上浮指定位点，实现堆有序化
	public void swim(int k) {
		while(k>1&&less(k,k/2)) {
			exch(k,k/2);
			k/=2;
		}
		
	}

    //下沉元素实现堆有序
	public void sink(int k) {
		while(2*k<=n) {
			int j = 2*k;
			if(j