【数据结构与算法】第九章：优先队列（最大、最小、索引）
得到 items 队列中的最小元素：items[pq[1]]得到 items 队列中的最 k 个元素：items[pq[k]]
- 存储元素的数组
*/
private T[] items;
/**
- 元素个数
*/
private int n;
/**
-
构造器
-
@param capacity
*/
public MaxPriorityQueue(int capacity) {
this.items = (T[]) new Comparable[capacity + 1];
this.n = 0;
}
/**
-
元素个数
-
@return
*/
public int size() {
return n;
}
/**
-
是否为空
-
@return
*/
public boolean isEmpty() {
return n < 1;
}
/**
-
插入元素
-
@param t
*/
public void insert(T t) {
// 在结尾插入
items[++n] = t;
// 让新元素上浮，找到合适的位置
swim(n);
}
/**
-
删除最大元素并返回
-
@return
*/
public T delMax() {
// 最大元素
T max = items[1];
// 交换索引1处 和 最大索引处的元素，让完全二叉树中最右的元素成为临时根结点
exch(1, n);
// 删除交换后最大索引处的元素，即原根结点（最大元素）
items[n] = null;
// 元素数量减1
n–;
// 让新根结点下沉，找到合适位置
sink(1);
return max;
}
/**
-
比较索引i处元素是否小于j处元素
-
@param i
-
@param j
-
@return
*/
private boolean less(int i, int j) {
return items[i].compareTo(items[j]) < 0;
}
/**
-
交换索引i处和j处元素
-
@param i
-
@param j
*/
private void exch(int i, int j) {
T temp = items[i];
items[i] = items[j];
items[j] = temp;
}
/**
-
让索引k处元素上浮到合适的位置
-
@param k
*/
private void swim(int k) {
// 循环比较索引k处元素和它父结点元素，如果父结点小，就交换位置
while (k > 1) {
// 比较当前结点与父结点
if (less(k / 2, k)) {
// 父比子小，交换位置
exch(k / 2, k);
}
k = k / 2;
}
}
/**
-
让索引k处元素下沉到合适的位置
-
@param k
*/
private void sink(int k) {
// 循环比较当前结点k 和 max(左子结点2k，右子结点2k+1)的值，如果当前结点k小，就交换位置
// 循环条件 2*k <= n ：表示存在 左子结点
while (2 * k <= n) {
// 获取当前结点中的较大 子结点
// 记录较大 子结点索引：默认为 左子结点
int max = 2 * k;
// 如果右结点存在，且左小于右，改变max
if (2 * k + 1 <= n && less(2 * k, 2 * k + 1)) {
max = 2 * k + 1;
}
if (!less(k, max)) {
// 当前结点不小于子结点，退出循环
break;
}
// 当前结点小于子结点，交换位置
exch(k, max);
// 交换k值，继续循环
k = max;
}
}
}
@Test
public void testMaxPriorityQueue() {
String[] arr = {“E”, “B”, “A”, “C”, “D”};
MaxPriorityQueue maxpq = new MaxPriorityQueue<>(20);
for (String s : arr) {
maxpq.insert(s);
}
System.out.println(maxpq.size());
String del;
while (!maxpq.isEmpty()) {
del = maxpq.delMax();
System.out.print(del + " ");
}
}
5
E D C B A
符合优先队列的要求：
插入时：在一端（尾部）
弹出时：在另一端（首部），并且首部都是最大的，即优先级最高的
最小优先队列实现起来也比较简单，同样也可以基于堆来完成最小优先队列
最大堆
前面的堆中存放数据元素的数组要满足如下特性：
- 最大的元素放在数组的索引1处
- 每个结点的数据总是大于等于它的两个子结点的数据
最小堆
让堆中存放数据元素的数组满足如下特性：
- 最小的元素放在数组的索引1处
- 每个结点的数据总是小于等于它的两个子结点的数据
1）API设计
2）代码实现
package chapter07;
/**
-
@author 土味儿
-
Date 2021/9/9
-
@version 1.0
-
最小优先队列
-
以最小堆的方式实现
*/
public class MinPriorityQueue<T extends Comparable> {
/**
- 存储元素的数组
*/
private T[] items;
/**
- 元素个数
*/
private int n;
/**
-
构造器
-
@param capacity
*/
public MinPriorityQueue(int capacity) {
this.items = (T[]) new Comparable[capacity + 1];
this.n = 0;
}
/**
-
元素个数
-
@return
*/
public int size() {
return n;
}
/**
-
是否为空
-
@return
*/
public boolean isEmpty() {
return n < 1;
}
/**
-
插入元素
-
@param t
*/
public void insert(T t) {
// 在结尾插入
items[++n] = t;
// 让新元素上浮，找到合适的位置
swim(n);
}
/**
-
删除最小元素并返回
-
@return
*/
public T delMin() {
// 最小元素
T min = items[1];
// 交换索引1处 和 最大索引处的元素，让完全二叉树中最右的元素成为临时根结点
exch(1, n);
// 删除交换后最大索引处的元素，即原根结点（最小元素）
items[n] = null;
// 元素数量减1
n–;
// 让新根结点下沉，找到合适位置
sink(1);
return min;
}
/**
-
比较索引i处元素是否小于j处元素
-
@param i
-
@param j
-
@return
*/
private boolean less(int i, int j) {
return items[i].compareTo(items[j]) < 0;
}
/**
-
交换索引i处和j处元素
-
@param i
-
@param j
*/
private void exch(int i, int j) {
T temp = items[i];
items[i] = items[j];
items[j] = temp;
}
/**
-
让索引k处元素上浮到合适的位置
-
@param k
*/
private void swim(int k) {
// 循环比较索引k处元素和它父结点元素，如果父结点大，就交换位置
while (k > 1) {
// 比较当前结点与父结点
if (less(k, k/2)) {
// 父比子大，交换位置
exch(k, k/2);
}
k = k / 2;
}
}
/**
-
让索引k处元素下沉到合适的位置
-
@param k
*/
private void sink(int k) {
// 循环比较当前结点k 和 min(左子结点2k，右子结点2k+1)的值，如果当前结点大，就交换位置
// 循环条件 2*k <= n ：表示存在 左子结点
while (2 * k <= n) {
// 获取当前结点中的较小 子结点
// 记录较小 子结点索引：默认为 左子结点
int min = 2 * k;
// 如果右结点存在，且左大于右，改变min
if (2 * k + 1 <= n && less(2 * k +1, 2 * k)) {
min = 2 * k + 1;
}
if (!less(min, k)) {
// 当前结点不大于子结点，退出循环
break;
}
// 当前结点大于子结点，交换位置
exch(k, min);
// 交换k值，继续循环
k = min;
}
}
}
@Test
public void testMaxPriorityQueue() {
String[] arr = {“E”, “B”, “A”, “C”, “D”};
//MaxPriorityQueue queue = new MaxPriorityQueue<>(20);
MinPriorityQueue queue = new MinPriorityQueue<>(20);
for (String s : arr) {
queue.insert(s);
}
System.out.println(queue.size());
String del;
while (!queue.isEmpty()) {
//del = queue.delMax();
del = queue.delMin();
System.out.print(del + " ");
}
}
5
A B C D E
在最大优先队列和最小优先队列中，可以分别快速访问到队列中最大元素和最小元素
但是有一个 缺点：就是没有办法通过索引访问已存在于优先队列中的对象，并更新它们
为了实现这个目的，在优先队列的基础上，学习一种新的数据结构，索引优先队列
以最小索引优先队列实现
1）实现思路
-
步骤一
-
存储数据时，给每一个数据元素关联一个整数
例如：insert(int k,T t)，可以看做 k 是 t 关联的整数，那么实现需要通过 k 这个值，快速获取到队列中 t 这个元素，此时 k 这个值需要具有唯一性
最直观的想法就是可以用一个T[] items 数组来保存数据元素，在 insert(int k,T t) 完成插入时，可以把 k 看做是 items 数组的索引，把 t 元素放到 items 数组的索引 k 处，这样再根据 k 获取元素 t 时就很方便了，直接就可以拿到 items[k] 即可
-
步骤二
-
步骤一完成后的结果，虽然给每个元素关联了一个整数，并且可以使用这个整数快速的获取到该元素，但是 items 数组中的元素 顺序是随机的，并不是堆有序的
-
增加一个数组 int[] pq，来 保存每个元素在 items 数组中的索引，pq 数组需要 堆有序
例如：pq[1] 对应的数据元素 items[pq[1]] 要小于等于 pq[2] 和 pq[3] 对应的数据元素 items[pq[2]] 和 items[pq[3]]
-
步骤三
-
通过步骤二的分析，可以发现，其实通过上浮和下沉做堆调整的时候，调整的是 pq 数组
如果需要对 items 中的元素进行修改，比如让 items[0]=“H”，那么很显然，需要对 pq 中的数据做堆调整，而且是调整 pq[9] 中元素的位置。但现在就会遇到一个问题，修改的是 items 数组中 0 索引处的值，如何才能快速的知道需要挑中 pq[9] 中元素的位置呢？
-
最直观的想法就是遍历 pq 数组，拿出每一个元素和 0 做比较，如果当前元素是0，那么调整该索引处的元素即可，但是效率很低
-
可以 另外增加一个数组 int[] qp，用来存储 pq 的 逆序
例如：
在pq数组中：pq[1] = 6；那么在qp数组中，把6作为索引，1作为值，结果是：qp[6]=1;
- 当有了 qp 数组后，如果修改 items[0]=“H”，那么就可以先通过索引 0，在 qp 数组中找到 qp 的索引：qp[0]=9, 那么直接调整 pq[9] 即可
-
总结
-
得到 items 队列中的最小元素：items[pq[1]]
-
得到 items 队列中的最 k 个元素：items[pq[k]]
- 修改 items 数组中的最 k 个元素为 t ：
1、items[k] = t
2、通过 qp 逆序数组，找到 pq 对应位置：pq[qp[k]]，并调整 pq 堆
3、更新 qp 逆序数组
2）API设计
3）代码实现
package chapter07;
/**
-
@author 土味儿
-
Date 2021/9/9
-
@version 1.0
-
索引优先队列
-
以最小堆方式实现
*/
public class IndexMinPriorityQueue<T extends Comparable> {
/**
- 存储元素的数组
*/
private T[] items;
/**
- 保存 items 中元素的索引
*/
private int[] pq;
/**
-
pq数组 的逆序
-
pq中的值为qp的索引，pq的索引为qp的值
*/
private int[] qp;
/**
- 元素的数量
*/
private int n;
/**
-
构造器
-
@param capacity
*/
public IndexMinPriorityQueue(int capacity) {
this.items = (T[]) new Comparable[capacity + 1];
this.pq = new int[capacity + 1];
this.qp = new int[capacity + 1];
this.n = 0;
// 初始化qp为-1
for (int i = 0; i < qp.length; i++) {
qp[i] = -1;
}
}
/**
-
元素数量
-
@return
*/
public int size() {
return n;
}
/**
-
队列是否为空
-
@return
*/
public boolean isEmpty() {
return n < 1;
}
/**
-
获取队列 pq 中索引i对应元素的值
-
@param i
-
@return
*/
public T get(int i) {
if (i < 0 || i > pq.length) {
return null;
}
return items[pq[i]];
}
/**
-
判断堆中索引i处元素是否小于j处
-
@param i
-
@param j
-
@return
*/
private boolean less(int i, int j) {
// 实际比较的是items中元素的值，而堆中存的是items元素的索引
return items[pq[i]].compareTo(items[pq[j]]) < 0;
}
/**
-
交换堆中索引i处与j处的值
-
@param i
-
@param j
*/
private void exch(int i, int j) {
// i = 1; j = 3;
// 交换前
// pq[1] = 5 —> qp[5] = 1
// pq[3] = 7 —> qp[7] = 3
// 交换后
// pq[1] = 7 —> qp[7] = 1 => qp[pq[1]] = 1 => qp[pq[i]] = i
// pq[3] = 5 —> qp[5] = 3 => qp[pq[3]] = 3 => qp[pq[j]] = j
// 交换pq
int temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
// 交换qp
qp[pq[i]] = i;
qp[pq[j]] = j;
}
自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。
深知大多数Java工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！
因此收集整理了一份《2024年Java开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。
既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Java开发知识点，真正体系化！
由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且会持续更新！
如果你觉得这些内容对你有帮助，可以扫码获取！！（备注Java获取）
Kafka实战笔记
关于这份笔记，为了不影响大家的阅读体验，我只能在文章中展示部分的章节内容和核心截图
- Kafka入门
- 为什么选择Kafka
- Karka的安装、管理和配置
- Kafka的集群
- 第一个Kafka程序
afka的生产者
- Kafka的消费者
- 深入理解Kafka
- 可靠的数据传递
- Spring和Kalka的整合
- Sprinboot和Kafka的整合
- Kafka实战之削峰填谷
- 数据管道和流式处理(了解即可)
- Kafka实战之削峰填谷
《互联网大厂面试真题解析、进阶开发核心学习笔记、全套讲解视频、实战项目源码讲义》点击传送门即可获取！
qqZ4qZ-1713421354705)]
[外链图片转存中…(img-7QAKNaPn-1713421354705)]
既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Java开发知识点，真正体系化！
由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且会持续更新！
如果你觉得这些内容对你有帮助，可以扫码获取！！（备注Java获取）
Kafka实战笔记
关于这份笔记，为了不影响大家的阅读体验，我只能在文章中展示部分的章节内容和核心截图
[外链图片转存中…(img-td3sVZCh-1713421354706)]
- Kafka入门
- 为什么选择Kafka
- Karka的安装、管理和配置
[外链图片转存中…(img-n0fSXFgd-1713421354706)]
- Kafka的集群
- 第一个Kafka程序
- [外链图片转存中…(img-b9YLOtZa-1713421354706)]
afka的生产者
[外链图片转存中…(img-9mhskg3n-1713421354706)]
- Kafka的消费者
- 深入理解Kafka
- 可靠的数据传递
[外链图片转存中…(img-PpMo9Eed-1713421354706)]
[外链图片转存中…(img-IxPaLqlV-1713421354706)]
- Spring和Kalka的整合
- Sprinboot和Kafka的整合
- Kafka实战之削峰填谷
- 数据管道和流式处理(了解即可)
[外链图片转存中…(img-cNWtsp1r-1713421354707)]
- Kafka实战之削峰填谷
[外链图片转存中…(img-nU2dsK6K-1713421354707)]
《互联网大厂面试真题解析、进阶开发核心学习笔记、全套讲解视频、实战项目源码讲义》点击传送门即可获取！
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
3
0- 0
已为社区贡献4条内容
所有评论(0)