服务周到的上海网站建设可以做微信游戏的网站有哪些

服务周到的上海网站建设,可以做微信游戏的网站有哪些,jsp网站开发 英文,可以做视频推广的网站有哪些内容堆与优先级队列#xff1a;从概念到手写大根堆#xff08;Java#xff09; 写算法写到后面#xff0c;会越来越频繁地遇到一种需求#xff1a;我不想按进入顺序取数据#xff08;FIFO#xff09;#xff0c;我想按“重要程度/大小”取。比如任务调度、Dijkstra、Top-K、…堆与优先级队列从概念到手写大根堆Java写算法写到后面会越来越频繁地遇到一种需求我不想按进入顺序取数据FIFO我想按“重要程度/大小”取。比如任务调度、Dijkstra、Top-K、定时器、甚至游戏里“高优先级事件先处理”。这时候普通队列就不够用了需要的是优先级队列Priority Queue支持“加入元素”和“取出最高优先级元素”。而在 Java 里PriorityQueue的底层结构就是堆。所以把堆学明白等于把一大堆“面试/工程常用场景”打通。1. 堆到底是什么堆Heap可以理解为在完全二叉树的形状约束上再加一条“父子大小关系”的约束。形状约束堆一定是一棵完全二叉树从上到下、从左到右尽量填满。大小约束二选一大根堆最大堆父节点 ≥ 子节点堆顶是最大值小根堆最小堆父节点 ≤ 子节点堆顶是最小值对大小堆的定义就是用这种父子关系不等式来描述的。这两条约束带来一个“爽点”只要维护堆性质堆顶永远是当前集合的最大/最小值。这正是优先级队列想要的。2. 为什么堆适合用数组存因为堆是完全二叉树层序存进数组不会浪费空位不像普通二叉树会有大量 null 洞。强调非完全二叉树不适合顺序存储会导致空间利用率低。数组下标和树结构的对应关系非常重要写 siftUp/siftDown 全靠它下标i的父节点(i - 1) / 2下标i的左孩子2*i 1下标i的右孩子2*i 2在TestHeap里这些公式被完整用在siftDown和siftUp中intchild2*parents1;// 左孩子intparent(child-1)/2;// 父节点手写堆代码总览如下packageDataStructure;importjava.util.Arrays;publicclassTestHeap{publicint[]elem;publicintusedSize;publicTestHeap(){this.elemnewint[10];}publicvoidinitElem(int[]array){for(inti0;iarray.length;i){this.elem[i]array[i];this.usedSize;}}publicvoidcreateHeap(){for(intparents(this.usedSize-1-1)/2;parents0;parents--){//这里解释一下this.usedSize - 1 代表最后一个子树的下标再减一除以二就是最后一个子树的——//——双亲节点的下标这里建大根堆就从下往上开始建siftDown(parents,this.usedSize);}}publicvoidsiftDown(intparents,intusedSize){//自顶向下比较intchild2*parents1;while(childusedSize){//防止数组下标越界找到左右孩子的最大值if(child1usedSizeelem[child]elem[child1]){child;}if(elem[child]elem[parents]){// int tmp elem[child];// elem[child] elem[parents];// elem[parents] tmp;swap(elem,child,parents);parentschild;child2*parents1;//这两行的意思是从parents开始向下比较比完了//child就继续向下加直到加到usedSize - 1的位置(最后一个元素)就算比完了}else{break;}}}publicvoidpush(intval){if(isFull()){elemArrays.copyOf(elem,2*elem.length);}usedSize;elem[usedSize-1]val;siftUp(usedSize-1);}publicvoidsiftUp(intchild){//自底向上比较intparent(child-1)/2;while(parent0){if(elem[child]elem[parent]){swap(elem,child,parent);childparent;parent(child-1)/2;//也是向上走}else{break;}}}publicbooleanisFull(){returnusedSizeelem.length;}publicvoidswap(int[]elem,inti,intj){inttmpelem[i];elem[i]elem[j];elem[j]tmp;}publicintpoll(){if(isEmpty())return-1;intvalelem[0];swap(elem,0,usedSize-1);usedSize--;siftDown(0,usedSize);returnval;}publicbooleanisEmpty(){returnusedSize0;}publicvoidheapSort(){intendusedSize-1;while(end0){swap(elem,0,end);siftDown(0,end);end--;}}}3. 手写堆的“骨架”elem usedSize这份实现的整体结构很典型publicint[]elem;// 数组存堆publicintusedSize;// 当前有效元素个数堆大小elem是存储区usedSize是“堆里目前有多少元素”空间不足时扩容Arrays.copyOf这和 JDK 的PriorityQueue自动扩容思想一致只是扩容倍率细节不同4. 堆的灵魂操作 ①向下调整 siftDown建堆、删除都靠它4.1 siftDown 在解决什么问题当某个节点通常是 parent可能比孩子小大根堆场景就需要把它往下“沉”直到父子关系恢复正确。对“向下调整”的描述很标准从 parent 出发比较左右孩子选择更合适的那个孩子交换继续向下。并且提醒了一个关键前提要向下调整 parent必须保证它的左右子树已经是堆。4.2 这份 siftDown 的细节大根堆版本核心逻辑非常清晰child先指向左孩子如果右孩子存在挑左右孩子中更大的那个大根堆就挑大的如果孩子比父大就交换并继续向下否则 break说明这棵子树已经满足堆性质代码对应intchild2*parents1;while(childusedSize){if(child1usedSizeelem[child]elem[child1]){child;}if(elem[child]elem[parents]){swap(elem,child,parents);parentschild;child2*parents1;}else{break;}}这个写法的好处是每次只沿着一条路径下沉最多下沉到叶子时间复杂度就是树高O(log n)5. 堆的创建 createHeap为什么从最后一个非叶子开始createHeap()这段是自底向上的建堆for(intparents(this.usedSize-1-1)/2;parents0;parents--){siftDown(parents,this.usedSize);}这里(usedSize - 2) / 2就是“最后一个非叶子节点”的下标——因为叶子节点根本没有孩子不需要下沉。自底向上建堆的关键直觉是最底层的叶子天然是堆往上一层每个 parent 的左右子树都已经是堆于是可以安全siftDown(parent)这正好吻合“向下调整的前提”。建堆复杂度也很常被问并不是n log n而是O(n)教材/课件通常会用满二叉树分层求和证明。一句话记忆建堆看起来像“很多次 log”但下层节点下沉高度很小摊还下来是 O(n)。6. 堆的灵魂操作 ②向上调整 siftUp插入靠它插入push的两步非常固定先把新元素放到底层最后再向上调整恢复堆性质。这份实现对应publicvoidpush(intval){if(isFull()){elemArrays.copyOf(elem,2*elem.length);}usedSize;elem[usedSize-1]val;siftUp(usedSize-1);}siftUp的思想是“冒泡上浮”child 找 parent如果 child 比 parent 大大根堆交换child 指向 parent继续向上intparent(child-1)/2;while(parent0){if(elem[child]elem[parent]){swap(elem,child,parent);childparent;parent(child-1)/2;}else{break;}}这里我会做一个“工程味的小提醒”更常见的循环条件是while(child 0)语义更直观现在用parent 0也能跑通因为 child0 时 parent0会立即 break只是读起来稍绕一点。插入的时间复杂度是O(log n)上浮最多走树高。7. 删除堆顶 poll堆删除永远删的是“堆顶”堆的删除非常有仪式感只能删除堆顶因为堆顶代表“最高优先级”。1堆顶与最后一个元素交换2有效元素个数减一3对堆顶做向下调整恢复堆性质这份实现一一对应publicintpoll(){if(isEmpty())return-1;intvalelem[0];swap(elem,0,usedSize-1);usedSize--;siftDown(0,usedSize);returnval;}这就是优先级队列的poll()的本质取最高优先级大根堆取最大小根堆取最小并维护结构仍然是堆。8. 堆排序 heapSort用“反复删除堆顶”来排序建堆想要升序建大堆最大值不断放到数组末尾想要降序建小堆利用删除思想排序把堆顶最大与末尾交换“堆大小”缩小 1对堆顶向下调整这份heapSort()就是标准的大根堆升序写法intendusedSize-1;while(end0){swap(elem,0,end);siftDown(0,end);// 注意end 作为“新的堆大小”右边已排序区不再参与end--;}排序完成后数组就是升序排列。整体复杂度O(n log n)额外空间O(1)原地排序。9. 和 Java PriorityQueue 对照一下默认小根堆想要大根堆要比较器对PriorityQueue的注意事项元素必须可比较否则会ClassCastException不能插入null否则NullPointerException默认是小根堆插入/删除的时间复杂度是对数级本质就是 siftUp/siftDown扩容会带来拷贝成本最好在已知规模时给个初始容量课件还给了 JDK1.8 的扩容策略示例想要“大根堆”就是提供Comparator反转比较顺序——这和最小 K 个数那题里“用大根堆维护 k 个候选”的做法完全一致。10. 堆的一个杀手级应用Top-K最小 K / 最大 K拿 Top-K 做总结数据量大时不适合直接排序堆是最佳方案之一。思路也很固定求前 K 个最小维护一个大小为 K 的大根堆堆顶是“当前最差/最大”的那个求前 K 个最大维护一个大小为 K 的小根堆遍历剩余元素与堆顶比较合格就替换堆顶。最后堆里剩下的就是答案。11. 这份手写堆实现的小结与几个“实战建议”这份TestHeap把堆的四件核心事都打通了建堆createHeap()siftDown()插入push()siftUp()删除堆顶poll()siftDown()堆排序heapSort()反复 swap 下沉如果把它当作“可复用的工程组件”我通常会额外加几条强化initElem前先确保容量足够数组长度可能 10需要扩容或直接copyOfpoll()空堆返回-1适合演示工程里更常见的是抛异常或返回OptionalInt把Stack/Vector这类老容器替换为更现代的结构这里已经用数组实现了核心不受影响最后用一句话把堆记牢堆是“完全二叉树 父子有序”用数组存真正维护它的只有两招向下调整和向上调整。把这两招写对优先级队列、堆排序、Top-K 这些题基本就不怕了。