优先队列应用场景：
在一堆杂乱无序的数据里，尤其是当数据量特别大时，要选出最大（最小）的几个元素，那么就不必将所有数据都排序后再选择。这时需要一种合适的数据结构，能够删除最小元素和插入元素。
例如在一个有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
MinPQ() MinPQ(int max)
类初始化
返回优先队列中元素个数
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
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）