首页 / 算法 / 算法-10-优先队列
算法-10-优先队列
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法-10-优先队列，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3959字，纯文字阅读大概需要6分钟。
内容图文
目录
1、背景
考虑以下问题:输入 N 个int值，从中找出最大的(或是最小的)M 个int值。这中情景可以出现在：比如每个月的账单有很多记录，我只需要消费最大的5笔记录。那么我们的实现方法是什么呢？
方法一：将这N个int值排序，然后依次输出最大的M个。（如果数据量庞大，你得每次等到排序完之后才能拿到你想要的值，无法立即得到）
方法二：每次有新的消费记录插入的时候，都和那M（5）笔最大的记录进行比较。（除非M很小，否则代价很大）
方法三：优先队列（插入的时候就最大元素已经放在了合适的位置，等待获取）
2、优先队列
优先队列是一种抽象数据类型，和栈和队列类似，只是职能不一样。
它的主要职能是：1、删除（获取）最大的元素；
2、插入元素
插入和删除元素实现方式有三种：
第一种是插入的时候就排序好，这样取的时候直接拿就好了。（有序数组）
第二种是插入的时候不管，取的时候遍历拿到最大的元素。（无序数组）
第三种就是二叉堆。下面是这三种的时间复杂度。
3、二叉堆
二叉堆是一种特殊的堆，二叉堆是完全二元树（二叉树）或者是近似完全二元树（二叉树）。二叉堆有两种：最大堆和最小堆。最大堆：父结点的键值总是大于或等于任何一个子节点的键值；最小堆：父结点的键值总是小于或等于任何一个子节点的键值。
二叉堆一般用数组来表示。如果根节点在数组中的位置是1，第n个位置的子节点分别在2n和 2n+1。因此，第1个位置的子节点在2和3，第2个位置的子节点在4和5。以此类推。这种基于1的数组存储方式便于寻找父节点和子节点。
下图中a[1]的子结点就是a[2]和a[3].
4、插入函数-insert()
插入一个元素，我们会先把它放在数组的尾端，然后根据k/2找到它的父结点的下标，并和其比较，如果比a[k/2]大，那么就把父节点替换下来。这样我们就可以保证根结点a[1] （a[0]没有使用）永远是最大的元素。
5、删除最大元素- delMax()
我们从数组顶端删去最大 的元素并将数组的最后一个元素放到顶端，减 小堆的大小并让这个元素下沉到合适的位置。
6、完整代码
public class MaxPQ {
private static double[] a;
private static int N = 0;
private MaxPQ(int lenght) {
a = new double[lenght + 1];
}
public void insert(double item) {
a[++N] = item;
swim(N);
}
/**
* 删除堆中最大的元素
*/
public double delMax() {
double maxItem = a[1];
a[1] = a[N--];// 先拿到a[N]元素之后，N才会减一
a[N+1] = 0; // 如果这里是对象的话，可以用来置空释放对象的引用，防止对象游离
sink(1);// 将新的根结点，下沉到合适位置，堆的重新排序
return maxItem;
}
/**
* 上浮
*/
private void swim(int k) {
while (k > 1) {
if (a[k] > a[k / 2]) {
exch(k, k / 2);// k/2获取到它的父结点
k = k / 2;
} else {
break;
}
}
}
/**
* 下沉
*/
private void sink(int k) {
while (2 * k <= N) {
int j=2*k;
if (j<N&&a[j]<a[j+1]) j++; //保证每次和a[k]比较的是它的两个子结点中较大的那个
if (a[k]>a[j])break;
exch(k,j);
k=j;
}
}
private void exch(int i, int j) {
double temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static double[] getA() {
return a;
}
private static void show(double[] a) {
System.out.println("\n");
for (double item : a) {
System.out.print((int) item + ",");
}
}
public static void main(String[] args) {
double[] a = { 55, 43, 23, 12, 13, 11, 7, 8, 88, 6, 3, 2, 4, 1, 9, 8, 7, 11, 56, 45, 22, 23,
45, 66 };
MaxPQ maxPQ = new MaxPQ(a.length);
for (double item : a) {
maxPQ.insert(item);
}
show(getA());
for (int i=0;i<a.length;i++){
maxPQ.delMax();
show(getA());
}
}
}
7、三叉树
我们上面的优先队列代码是利用完全二叉树的形式实现的，那么我们能不能用三叉树或者更多树来实现优先队列呢？
三叉树的父节点位于(k+1)/3 的位置，子结点位于 3k-1、3k、3k+1的位置。我们主要改动的代码就是上浮和下沉的代码。改后的代码如下：（根据下面代码的实现，我们可以实现多叉树的形式，不够性能的优劣得自己去实验）
/**
* 上浮
*/
private void swim(int k) {
while (k > 1) {
if (a[k] > a[(k+1) / 3]) {
exch(k, (k+1) / 3);// k/2获取到它的父结点
k = (k+1) / 3;
} else {
break;
}
}
}
/**
* 下沉
*/
private void sink(int k) {
int max;
while ( (3*k-1) <= N) {
int j=3*k-1;
max=j;
while (j<3*k+1&&j<N) {//保证每次和a[k]比较的是它的两个子结点中较大的那个
if (a[j] < a[j+1]) max=j+1;
j++;
}
if (a[k]>a[max])break;
exch(k,max);
k=max;
}
}
我要看一下山顶的风景 发布了82 篇原创文章 · 获赞 16 · 访问量 26万+ 私信 关注
内容总结
以上是互联网集市为您收集整理的算法-10-优先队列全部内容，希望文章能够帮你解决算法-10-优先队列所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。