前言:
大家好,我是良辰丫💞💞⛽,我们又见面了,前面我们讲了用链表实现的二叉树,今天我们来接触堆
的概念,堆是一种特殊的二叉树,只不过咱们的对底层原理是数组,堆也是我们在做题中经常见到的,那么,接下来我们就慢慢的去接触堆,认识堆,理解堆,掌握堆。有疑惑可以和我一起讨论交流哦,期待大家的来访。🍬🍬🍬
🧑个人主页:良辰针不戳
📖所属专栏:java数据结构
🍎励志语句:生活也许会让我们遍体鳞伤,但最终这些伤口会成为我们一辈子的财富。
💦期待大家三连,关注,点赞,收藏。
💌作者能力有限,可能也会出错,欢迎大家指正。
💞愿与君为伴,共探Java汪洋大海。
1、堆
1.1 堆的概念
堆
在逻辑上是一种完全二叉树,以顺序结构存储的方式存储的数据,堆的模拟一般用数组,其底层原理往往也是数组。堆分为大根堆和小根堆。
- 大根堆(最大堆):父亲节点比所有孩子节点都大。
- 小根堆(最小堆):父亲节点比所有孩子节点都小。
如下图就是一个板板正正的大根堆,每个父亲节点都比所有孩子节点都大,如果去掉下标为6的节点,还可称为大根堆,但是去掉了4号下标的节点就不是堆了,因为堆的概念是完全二叉树,那么为啥这么定义呢?因为在建堆的过程中需要一个个调整,如果不是完全二叉树,就不会调整成唯一的一个序列。
总结:
- 堆的父亲节点总是大于或者小于所有孩子节点。
- 堆总是一棵完全二叉树。
1.2 堆的基本性质
通过上面我们了解到
堆
是一种顺序存储的完全二叉树,对于非完全二叉树,不适合使用顺序方式进行存储,因为为了能够还原二叉树,空间中必须要存储空节点,就会导致空间利用率比较低。
下图为一个小根堆图,研究性质可以参考下图。
i表示节点的下标
- 如果i为0,则i表示的节点为根节点,否则i节点的双亲节点为 (i - 1)/2
- 如果2 * i + 1 小于节点个数,则节点i的左孩子下标为2 * i + 1,否则没有左孩子
- 如果2 * i + 2 小于节点个数,则节点i的右孩子下标为2 * i + 2,否则没有右孩子
1.3 堆的创建
堆的创建,顾名思义就是把一个个的数据插入到数组中,然后调整即可,一个个传数据太麻烦了,我们直接传入一个数组。调整的时候我们采用向下调整。
- 让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子)
- 如果parent的左孩子存在,即:child < size, 进行以下操作,直到parent的左孩子不存在
parent右孩子是否存在,存在找到左右孩子中最小的孩子,让child进行标
将parent与较小的孩子child比较,如果:
parent小于较小的孩子child,调整结束
否则:交换parent与较小的孩子child,交换完成之后,parent中大的元素向下移动,可能导致子
树不满足对的性质,因此需要继续向下调整,即parent = child;child = parent*2+1; 然后继续2。
下面以创建大根堆为例子。
public void createHeap() {
//usedSize记录堆中元素个数
for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
shiftDown(parent,usedSize);
}
}
//向下调整
private void shiftDown(int parent,int len) {
//知道父亲节点,然后扎到左孩子
int child = 2*parent + 1;
//要有左孩子
while (child < len) {
//一定是有右孩子的情况下
if(child+1 < len && elem[child] < elem[child+1]) {
child++;
}
//child下标 一定是左右孩子 最大值的下标
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
parent = child;
child = 2*parent+1;
//左右孩子都比父亲小时跳出循环
}else {
break;
}
}
}
- 在调整以parent为根的二叉树时,必须要满足parent的左子树和右子树已经是堆了才可以向下调整。
- 调整情况下,最坏的时候,从根一路比较到叶子,比较的次数为完全二叉树的高度。
那么,问题又来了,一颗普通的完全二叉树怎么调整成堆呢?
找倒数第一个非叶子节点,从该节点位置开始往前一直到根节点,遇到一个节点,应用向下调整
public static void createHeap(int[] array) {
int root = ((array.length-2)>>1);
for (; root >= 0; root--) {
shiftDown(array, root);
}
}
注意:
建堆的时间复杂度为O(N)。
1.4 堆插入数据
- 先将待插入元素放到下标为usedSize的位置。(空间不够时需要扩容)
- 进行向上调整,直到成为堆。
有的伙伴可能会疑惑了,刚刚学习了向下调整,下载插入数据操作为什么又要向上调整呢?
private void shiftUp(int child) {
int parent = (child-1)/2;
while (child > 0) {
if(elem[child] > elem[parent]) {
int tmp = elem[child];
elem[child] = elem[parent];
elem[parent] = tmp;
child = parent;
parent = (child-1)/2;
}else {
break;
}
}
}
//向上调整建堆的时间复杂度:N*logN
public void offer(int val) {
if(isFull()) {
//扩容
elem = Arrays.copyOf(elem,2*elem.length);
}
elem[usedSize++] = val;
//向上调整
shiftUp(usedSize-1);
}
1.5 堆删除数据
- 将堆顶元素对堆中最后一个元素交换
- 将堆中有效数据个数减少一个
- 对堆顶元素进行向下调整
public void pop() {
if(isEmpty()) {
return;
}
swap(elem,0,usedSize-1);
usedSize--;
shiftDown(0,usedSize);
}
public boolean isEmpty() {
return usedSize == 0;
}
private void swap(int[] array,int i,int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
2、优先级队列
说起对列,大家肯定不陌生,因为咱们前面的文章中学习过对列,对列是一种先进先出的数据结构,那么这里的
优先级队列
又是什么呢?下面我们简单通过一个代码对优先级队列做一个认识。
2.1 初识优先级队列
public static void main(String[] args) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue();
priorityQueue.offer(3);
priorityQueue.offer(4);
priorityQueue.offer(1);
priorityQueue.offer(2);
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());
}
咿呀,奇迹出现了,通过上面的运行截图,大家可以发现,优先级队列并不遵守先进先出,而是最小的数据先出来,由此呢?我们可以把它当成一种小根堆。
看到这里,大家又产生疑惑,默认为小根堆,那么如果我们想要使用优先队列作为大根堆呢?
办法当然是有的呀,这里我们引入了比较器。那么究竟如何实现呢?我们慢慢往下看。
2.2 比较器Comparator实现优先队列大根堆
看到这里,可能大家会感到疑惑,什么是
比较器
呢?
java中的对象提供的方法只能比较对象是否相等,而不能比较大小,java提供了一些接口,可以指定对象的属性进行比较,比如,根据学生信息的年龄进行排序。
呜呜呜,看了上面的解释还不明白,没关系,在我上一篇文章中详细介绍了比较器,如果大家对比较器有疑惑,请去具体学习比较器。
对象的比较,点击跳转文章
import java.util.Comparator;
import java.util.PriorityQueue;
class IntCmp implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
}
public class Test02 {
public static void main(String[] args) {
PriorityQueue priorityQueue = new PriorityQueue<>(new IntCmp());
priorityQueue.offer(3);
priorityQueue.offer(4);
priorityQueue.offer(1);
priorityQueue.offer(2);
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());
System.out.println(priorityQueue.poll());
}
}
奇迹出现了优先队列通过比较器Comparator修改成了大根堆。
注意:
上面的IntCmp类中有自动装包拆包的过程,这里不做详细说明,简单提及一下,Comparator的类型参数不能为基本数据类型,所以只能用包装类Integer,如果想了解更多装包拆包大家可以去自主学习,或者我以后的文章也会更新的。文章来源:https://www.toymoban.com/news/detail-431381.html
后序:
堆与优先级队列的学习愉快的结束了,大家肯定受益颇深🐥🐥🐥,知识点全都不难,所谓难的东西也是一个个小小的知识点汇集而成的,不要着急,学习是一个不断探索的过程,心若向阳,路便花开,继续加油🍗🍗🍗!!!文章来源地址https://www.toymoban.com/news/detail-431381.html
到了这里,关于【堆的认识及其优先级队列】java代码实现,保姆级教程学习堆和优先级队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!