睢宁网站建设xzqjwl,服装营销型网站建设,国内网如何看国外网站,中企动力唐山网站建设#x1f308;个人主页#xff1a;努力学编程’ ⛅个人推荐#xff1a;基于java提供的ArrayList实现的扑克牌游戏 |C贪吃蛇详解 ⚡学好数据结构#xff0c;刷题刻不容缓#xff1a;点击一起刷题 #x1f319;心灵鸡汤#xff1a;总有人要赢#xff0c;为什么不能是我呢 …
个人主页努力学编程’ ⛅个人推荐基于java提供的ArrayList实现的扑克牌游戏 |C贪吃蛇详解 ⚡学好数据结构刷题刻不容缓点击一起刷题 心灵鸡汤总有人要赢为什么不能是我呢 相信大家对于队列的理解是比较熟悉的队列是一种先进先出的数据结构但是我们在日常项目的开发中往往需要对于一些数据的处理是要求所使用的数据结构处理数据时必须有一定的优先级的比如你在打游戏的时候字节给你打入职电话那么手机一定会优先处理电话的业务或者在你的学生时代一定经历过老师让学习好的同学先挑座位类似与这种情况我们引出一个新的数据结构优先级队列-堆 堆的定义
堆是一种特殊的树形数据结构它满足堆属性对于堆中任意节点 i父节点的值小于等于或大于等于其子节点的值。根据这个属性可以将堆分为最大堆和最小堆。在最大堆中父节点的值大于等于其子节点的值在最小堆中父节点的值小于等于其子节点的值。
堆通常用于实现优先级队列因为堆能够快速找到具有最高或最低优先级的元素。常见的堆有二叉堆和斐波那契堆它们在插入和删除操作的时间复杂度上有所不同但都能保持堆属性。
大根堆
顾名思义根节点其实是整个完全二叉树的最大值的节点他的左孩子结点和右孩子节点都比他要小同时要保证整棵树是大根堆那么每棵子树也必须得是大根堆这样才可以构成一个完整的大根堆结构。 小根堆
有了大根堆理解我们去学习小根堆就轻松多了每棵子树的根节点都是这棵子树中的值最小的这样所有的子树就构成了整个小根堆。 有了小根堆和大根堆的概念我们后面可以尝试自己实现一个小根堆和大根堆后面会给大家实现。请大家牢记这些基本知识。
堆的创建
讲了堆的一些基本知识相信大家都和我一样手痒难耐非常想自己手搓一个堆但是在这之前我们必须要先了解一个知识点向下调整这是我们实现队列的基本要求。
向下调整 1. 让parent标记需要调整的节点child标记parent的左孩子(注意parent如果有孩子一定先是有左孩子)
2. 如果parent的左孩子存在即:child size 进行以下操作直到parent的左孩子不存在parent右孩子是否存在存在找到左右孩子中最小的孩子让child进行标将parent与较小的孩子child比较如果 parent小于较小的孩子child调整结束 否则交换parent与较小的孩子child交换完成之后parent中大的元素向下移动可能导致子树不满足对的性质因此需要继续向下调整即parent childchild parent*21; 然后继续2。
具体的过程建议大家在纸上先自己实现一下这里把整个过程也给大家
public void shiftDown(int[]array,int parent){int child2*parent1;int size array.length;while(childsize){if(child1sizearray[child1]array[child]){child1;}if(array[parent]array[child]){break;}else{int tarray[parent];array[parent]array[child];array[child]t;}parentchild;childparent*21;}}好了掌握了向下调整的知识点我们就可以自己手搓一个堆了我们实现的代码是比较简单的。针对每个节点我们都使用向下调整的逻辑就可以实现大根堆或者小根堆
public static void createHeap(int[] array) {
// 找倒数第一个非叶子节点从该节点位置开始往前一直到根节点遇到一个节点应用向下调整
int root ((array.length-2)1);
for (; root 0; root--) {
shiftDown(array, root);
}
public void shiftDown(int[]array,int parent){int child2*parent1;int size array.length;while(childsize){if(child1sizearray[child1]array[child]){child1;}if(array[parent]array[child]){break;}else{int tarray[parent];array[parent]array[child];array[child]t;}parentchild;childparent*21;}}
}堆的时间复杂度
因为初始化堆是每个数据向下冒泡每一层冒泡的次数不同最高层冒泡的次数最多为logn,最底层为1次设共有h层hlogn) , 时间复杂度的计算为1h2(h-1)4(h-2)…2^(h-1)1
即【节点数所在层数】的累加如2h-1即第二层有两个节点因为在第二层所以会冒泡h-1次
可以转化为通项 k从0到h-1的累加 用错项相减法求 可以得到O()即O即On) 关于调整堆/删除堆
因为在调整的时候每调整/删除一次树的节点就会少一个跑到有序堆去了然鹅每次调整的时候是从下往上冒泡的所以调整的次数即当前树的层数那怎么确定当前树的层数呢直接对当前节点取对数就好了每一个节点都要进行这样的操作所以操作的次数是log(n-1)log(n-2)…log2log1log(n-1)!nlogn
故时间复杂度为Onlogn)
故整个堆排序 时间复杂度取大的Onlogn)
⛅堆的插入和删除
插入
大家有没有想过在堆里面如何添加节点呢整个过程大致分为两个步骤
将待插入的节点放到二叉树的最后一个叶子节点从待插入的节点开始依次进行shiftUp向上调整 具体向上调整代码如何实现这里也给大家一段代码
public void shiftUp(int[] array,int child){//这里模拟的是大根堆的情况int parent(child-1)/2;while(child0){if(array[parent]array[child]){break;}else {int tarray[child];array[parent]array[child];array[child]t;childparent;parent(child-1)/2;}}}删除
对于堆的删除是十分重要的想想我们在文章开始的时候是不是说过堆的底层逻辑是一种线性结构本质上我们可以使用数组实现那么如果把他转化为数组的时候我们知道数组的元素其实是不能删除掉的只能对数据进行覆盖来完成元素的删除。堆在这里也是一样。
堆删除的具体步骤如下
将待删除的元素与二叉树的最后一个叶子结点进行交换将堆的底层数组内的有效数据个数减一把整个二叉树进行向下调整重新调整二叉树的结构实现大根堆或者小根堆 public int poll() {if(isEmpty()) {return -1;}int old elem[0];swap(0,usedSize-1);usedSize--;siftDown(0,usedSize);return old;}
有关堆的一些常见接口介绍
在java中我们并不需要自己去实现堆java是一门高级语言我们只需要知道每种重要的数据结构底层是如何实现的然后我们直接使用系统为我们提供的结构就好了。
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列PriorityQueue是线程不安全的PriorityBlockingQueue是线程安全的这里主要介绍PriorityQueue。 关于PriorityQueue的使用要注意
使用时必须导入PriorityQueue所在的包即
java import java.util.PriorityQueue;PriorityQueue中放置的元素必须要能够比较大小不能插入无法比较 大小的对 象否则会抛出ClassCastException异常不能插入null对象否则会抛出NullPointerException没有容量限制可以插入任意多个元素其内部可以自动扩容插入和删除元素的时间复杂度为O( l o g n logn logn)PriorityQueue底层使用了堆数据结构PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素
当然我们也要熟悉对于堆的一些基础操作 static void TestPriorityQueue2(){
int[] arr {4,1,9,2,8,0,7,3,6,5};
// 一般在创建优先级队列对象时如果知道元素个数建议就直接将底层容量给好
// 否则在插入时需要不多的扩容
// 扩容机制开辟更大的空间拷贝元素这样效率会比较低
PriorityQueueInteger q new PriorityQueue(arr.length);
for (int e: arr) {
q.offer(e);
}
System.out.println(q.size()); // 打印优先级队列中有效元素个数
System.out.println(q.peek()); // 获取优先级最高的元素
// 从优先级队列中删除两个元素之和再次获取优先级最高的元素
q.poll();
q.poll();
System.out.println(q.size()); // 打印优先级队列中有效元素个数
System.out.println(q.peek()); // 获取优先级最高的元素
q.offer(0);
System.out.println(q.peek()); // 获取优先级最高的元素
// 将优先级队列中的有效元素删除掉检测其是否为空
q.clear();
if(q.isEmpty()){
System.out.println(优先级队列已经为空!!!);
}
else{
System.out.println(优先级队列不为空);
}
}优先级队列的扩容说明
如果容量小于64时是按照oldCapacity的2倍方式扩容的如果容量大于等于64是按照oldCapacity的1.5倍方式扩容的如果容量超过MAX_ARRAY_SIZE按照MAX_ARRAY_SIZE来进行扩容
堆的应用-TopK问题
对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都 不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下
我们最先想到的就是创建一个小根堆把前k个元素放进去然后接着遍历数组将较小的元素换进去最后将堆的元素放到一个数组中返回这个数组就好。
class IntCmp implements ComparatorInteger {Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
}
public class Test {/*虽然 通过了 但是 不是非常好的解决方案*/public static int[] smallestK1(int[] arr, int k) {PriorityQueueInteger minHeap new PriorityQueue();for (int i 0; i arr.length; i) {minHeap.offer(arr[i]);}int[] tmp new int[k];for (int i 0; i k; i) {int val minHeap.poll();tmp[i] val;}return tmp;}
这段代码虽然可以提交成功但是并非是最优的解法最规范的解法是这样的 用数据集合中前K个元素来建堆 前k个最大的元素则建小堆 前k个最小的元素则建大堆 用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素 将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
class IntCmp implements ComparatorInteger {Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
}
class Solution {public static int[] smallestK(int[] arr, int k) {int[] tmp new int[k];if(k 0) {return tmp;}PriorityQueueInteger maxHeap new PriorityQueue(new IntCmp());//1.把前K个元素放进堆中for (int i 0; i k; i) {maxHeap.offer(arr[i]);}//2.遍历剩下的N-K个元素for (int i k; i arr.length; i) {int val maxHeap.peek();if(val arr[i]) {maxHeap.poll();maxHeap.offer(arr[i]);}}for (int i 0; i k; i) {tmp[i] maxHeap.poll();}return tmp;}
}好了今天就分享到这里期待大家的一键三连
