网站建设张家港,专业网架公司,做本地网站要服务器吗,网页制作流程图模板概念
优先级队列是啥#xff1f; 队列是一种先进先出 (FIFO) 的数据结构 #xff0c;但有些情况下#xff0c; 操作的数据可能带有优先级#xff0c;一般出队 列时#xff0c;可能需要优先级高的元素先出队列。 在这种情况下#xff0c; 数据结构应该提供两个最基本的…概念
优先级队列是啥 队列是一种先进先出 (FIFO) 的数据结构 但有些情况下 操作的数据可能带有优先级一般出队 列时可能需要优先级高的元素先出队列。 在这种情况下 数据结构应该提供两个最基本的操作一个是返回最高优先级对象一个是添加新的对象 。这种数据结构就是优先级队列 (Priority Queue) 。 堆是啥
优先级队列的底层运用到堆这种数据结构
堆的特点总是一棵完全二叉树
大根堆
每一棵树的根结点总是比左右子节点大 小根堆
每一棵树的根结点的值总是比左右子节点小不考虑左右子节点谁大谁小 堆的存储
存储方式采用层序遍历的方式把二叉树的元素一一放到数组里面 那数组可不可以存储非完全二叉树呢答案是可以的但是会有空间浪费的情况 像上面右边图4的位置没有存储元素这就是一种空间浪费
来手搓一个堆
回顾一下二叉树里面性质的第五点 如何将普通数组转换成堆
把下面数组的元素画成堆 先画成一棵普通的二叉树 画成大根堆
2837互换。最左边子树492518把49变成该树的根结点最右边的树653419也进行交换 调整第二层的树49153749作为根而151825下方的树得把25变成根 最上面一层的树65492765做根结点而2734所以34还得作为该子树的根结点
这就是一个大根堆了
总结
1.从最后一棵子树开始调整
2.在要变换的树里面从左右孩子里面找到最大的与根结点比较大了就进行互换
3.如果能够知道子树根结点下标那么下一棵子树就是当前根结点下标-1
4.一直调整到0下标这个树为止
先写个初步的代码
public class TestHeap {private int[] elem;public int usedSize;//记录当前堆当中有效的数据个数public TestHeap(){this.elem new int[10];}//存储数组public void initElem(int[] array){for (int i 0; i array.length; i) {elem[i] array[i];usedSize;}}
问题
1.最后一棵子树根结点下标是多少
因为i len-1所以根结点index (i-1)/2 public void createHeap(){//usedSize-1相当于最后一棵树孩子结点的下标i再-1是为了求父结点for (int parent (usedSize-1-1)/2; parent 0; parent--) {siftDown(parent,usedSize);}}2.每棵子树调整完之后结束的位置怎么定也就是我要从哪里开始调整下一棵子树
我们采用向下调整的方法注意虽然我们是从最后一颗树往根结点方向调整但是每一棵树的处理我们还是采用从父结点到子节点的调整方法。为什么用不向上调整后面我会说到。
找到最后一个元素置为c其根结点为p 调整完后不知道下面还有没有元素要调整所以c还得往下走 此时c的坐标是19 10了所以可以停止了 private void siftDown(int parent, int len){int child 2 * parent 1;while(child len){//左右孩子比较大小if(elem[child] elem[child 1]){child child 1;}//走完上面的if证明child下标一定是左右两个孩子最大值的下标}}
现在问题来了写到这里会发生数组越界如果我的child移到9下标这里那这个if判断elem[child] elem[child1] 这里的child1 10 usedSize而这棵树根本就没有10这个下标造成了越界
修改一下代码 if(child1len elem[child] elem[child 1]){child child 1;}
后面就是比较孩子和父结点的代码了 /*** 向下调整* param parent* param len*/private void siftDown(int parent, int len){int child 2 * parent 1;while(child len){//左右孩子比较大小if(child1len elem[child] elem[child 1]){child child 1;}//走完上面的if证明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;//不用比不用调了}}}
测试一下没有问题 怎么计算这个堆的时间复杂度
考虑最坏情况就是满二叉树的情况 首先明确一点最后一层结点时不进行调整的一般是从倒数第二层结点开始调整的
设树的高度是h T(N) (h-1)*2^0(h-2)*2^1(h-3)*2^2......2*2^(h-3)1*2^(h-2)
怎么求这个等式采用错位相减 根据等比求和公式 T(n) 2 ^ h - 1 - h
因为n2^h-1 -- h log(n1)
代进去T(n) n - log(n1)
因为log(n1)的图长这样n越大越趋于一个常数 所以整个等式占支配地位的还得是n所以T(N) ≈ n --时间复杂度O(N) 堆的插入
如果插入的数值比较小 如果插入的数值比较大那就得一层一层进行调整 这种调整叫做向上调整 public void swap(int i, int j){int tmp elem[i];elem[i] elem[j];elem[j] tmp;}public void push(int val){if(isFull()){elem Arrays.copyOf(elem, 2*elem.length);}elem[usedSize] val;//向上调整siftUp(usedSize);usedSize;}//判断满不满public boolean isFull(){return usedSize elem.length;}public void siftUp(int child){int parent (child - 1) / 2;while(child0){if(elem[child] elem[parent]){swap(child,parent);child parent;parent (child - 1) / 2;}else{break;}}}
在测试里面把80push进去没有问题 堆的插入的时间复杂度
因为最坏情况插入的元素是最大的那这个元素最多也就向上调整到根节点的位置也就是h
复杂度就是O(logN
欸那为什么不用向上调整来建堆呢
我们分析一下拿这棵满二叉树来说最底层有8个元素已经占了一半了网上建堆得每个元素都遍历一遍时间复杂度太大了 堆的删除
因为堆的删除一定是删除优先级最高的值所以一定是删除大根堆的根结点
比如这个我们要做的就是删除65
第一步把650下标与28最后一个元素进行交换 第二步向下调整0下标 public int pop(){if(empty()){throw new EmptyException(数组空了);}int oldVal elem[0];swap(0,usedSize-1);usedSize--;siftDown(0,usedSize);return oldVal;}public boolean empty(){return usedSize 0;}
测试一下没有问题 习题 选A可以自己画图反正就是层序遍历画树 选C 总共比较3次左边那个15的原本就是小根堆所以就不用比较 选C PriorityQueue
Java集合框架提供了PriorityQueue的优先级队列 注意事项 PriorityQueueStudent priorityQueue1 new PriorityQueue();priorityQueue1.offer(new Student(zhangsan,10));priorityQueue1.offer(new Student(lisi,12)); 1.PriorityQueue放入的元素必须能比较大小否则会报出下面的错误 2.不能插入null对象否则会报出下面的错误 PriorityQueueStudent priorityQueue1 new PriorityQueue();priorityQueue1.offer(null); 3.没有容量限制可以插入任意多个元素内部会自动扩容
4.插入和删除都是O(logn)
5.使用了最小堆的数据结构所以每次获取的元素都是最小的元素
oj练习
面试题 17.14. 最小K个数 - 力扣LeetCode 设计一个算法找出数组中最小的k个数。以任意顺序返回这k个数均可。 示例 输入 arr [1,3,5,7,2,4,6,8], k 4
输出 [1,2,3,4]提示 0 len(arr) 1000000 k min(100000, len(arr)) 方法一
建立最小堆把堆顶k个元素输出出来就行了
代码 public int[] smallestK(int[] arr, int k) {PriorityQueueInteger priorityQueue new PriorityQueue();//向上调整 O(logN)for (int i 0; i array.length; i) {priorityQueue.offer(array[i]);}int[] ret new int[k];//k*logNfor (int i 0; i k; i) {ret[i] priorityQueue.poll();}return ret;} 虽然通过了但是时间复杂度有点大
方法二 1.建立大根堆大小为k比如我们可以拿前三个元素来建一个大根堆 2.从第k1个元素开始比较如果比堆顶元素小则入堆。当前的堆顶元素(较大的)就舍弃掉因为已经不符合我对前k个最小的元素的要求了
遍历完整个大根堆长这样 问题来了PriorityQueue是默认采用小根堆的底层那我们要怎么让它采用大根堆呢
PriorityQueue源码里面的有一个compare函数 这个函数外层是compareTo函数 这两个函数结合一下把小的放在前面大的放在后面所以实现了小根堆的底层
我们可以重写PriorityQueue里面的compare函数把大的放在前面
class Imp implements ComparatorInteger{Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
}
整个的代码上面的重写可以扔到匿名内部类里面 public static int[] smallestK(int[] array, int k) {int[] ret new int[k];if(array null || k 0) {return ret;}//匿名内部类PriorityQueueInteger priorityQueue new PriorityQueue(new ComparatorInteger() {Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}});//1、建立大小为k的大根堆 O(K*logK)for (int i 0; i k; i) {priorityQueue.offer(array[i]);}//2、遍历剩下的元素 (N-K)*logK// (K*logK) N*logK - K*logK N*logK --时间复杂度for (int i k; i array.length; i) {int top priorityQueue.peek();//27if(array[i] top) {priorityQueue.poll();priorityQueue.offer(array[i]);}}//下面这个不能算topK的复杂度 这个地方是整理数据//k*logKfor (int i 0; i k; i) {ret[i] priorityQueue.poll();}return ret;} 别看力扣上面的通过时间我们要自行分析时间复杂度 堆排序 把这个数组从小到大排序需要建立大根堆 再把这棵树放到堆底这样最大的元素就有序了 再按照大根堆进行排序已经有序的元素就不管了把最大元素49放到堆顶然后再和堆第的15交换 以此类推设置一个堆底end每次拿0下标的元素和它交换交换完end-- public void heapSort(){int end usedSize-1;while(end0){swap(0,end);siftDown(0,end);end--;}}
时间复杂度O(N*logN)
