谷歌网站的主要内容抚州网站开发

谷歌网站的主要内容,抚州网站开发,windows做网站服务器,辽宁大连直客部七部电话一、堆与优先队列的直觉 1.1 堆是什么 堆#xff08;Heap#xff09;是一种完全二叉树形状的特殊树结构#xff0c;通常用数组实现#xff0c;满足两个条件#xff1a;[1][2] 形状#xff1a;是一棵完全二叉树 除最后一层外#xff0c;每一层都要尽量填满#xff1b;最…一、堆与优先队列的直觉1.1 堆是什么堆Heap是一种完全二叉树形状的特殊树结构通常用数组实现满足两个条件[1][2]形状是一棵完全二叉树除最后一层外每一层都要尽量填满最后一层的节点必须集中在左侧不能中间有“洞”。[3][4]性质父子之间有堆序关系最小堆每个节点的值 ≤ 它所有子节点的值最大堆每个节点的值 ≥ 它所有子节点的值。注意这是“值的大小关系”和“完全二叉树”的形状是否满、是否靠左是两回事。[5]1.2 完全二叉树 vs 普通二叉树普通二叉树每个节点最多有左右两个孩子怎么“长歪”都行。完全二叉树每一层从左到右尽量填满只有最后一层可以不满最后一层的节点必须连续靠左中间不能空一格。[6][3]堆一定是完全二叉树是因为要用数组顺序存储靠这个来推导“父子下标公式”。1.3 为什么数组可以表示树如果用数组 0-based 存一棵完全二叉树根放在下标 0然后按“层序遍历从上到下、从左到右”依次放入数组就可以推导出固定关系[7]若父节点下标为i则左子节点下标left 2*i 1右子节点下标right 2*i 2若子节点下标为ii 0则父节点下标parent (i - 1) / 2整除如果你用的是 1-based 数组课本常见父i左子2*i右子2*i 1本质一样只是下标起点不同。[7]数组存堆的优势不需要指针父子关系只靠下标计算内存连续cache 友好非常适合完全二叉树这种“很紧凑”的结构。二、堆的基础操作与核心伪代码下面用 0-based 数组实现一个最小堆支持四个操作[8][1]push(x)插入元素 xpop()弹出堆顶最小值top()查看堆顶最小值内部需要两个辅助siftUp(i)/siftDown(i)上浮、下沉2.1 siftUp新元素插入后的“上浮”场景插入时总是把新元素放到数组最后一格保证完全二叉树形状不变这样可能破坏堆序性质新值可能比它父亲还小对最小堆而言解决让新元素沿着父指针“一路往上冒泡”。伪代码// 上浮新元素插入到末尾后往上调整 siftUp(i): while i 0: parent (i - 1) / 2 // 0-based 父节点下标 if heap[parent] heap[i]: // 最小堆父 子 就停止 break swap(heap[parent], heap[i]) i parent // 核心往上走一层而不是 i为什么是i parent而不是i新插入的元素只影响“从它这个位置到根”的那条唯一路径上的父子关系只需要依次检查这条路径上的每一对父子先检查自己和父亲发现自己更小就与父亲交换然后“自己的位置变成父亲的位置”接下来要和“新的父亲”比较自然是i parent兄弟节点、堂兄弟节点之间完全不需要比较堆性质只要求“父子有序”不关心“同层左右顺序”。[9][10]所以siftUp的访问路径是[i \rightarrow parent(i) \rightarrow parent(parent(i)) \rightarrow \dots \rightarrow 0]只走这一条链不会漏掉该比较的地方。2.2 siftDown删除堆顶后的“下沉”场景删除堆顶下标 0时为了不破坏完全二叉树形状用“最后一个元素”填到heap[0]删除数组最后一格pop_back()现在只有根这个位置的堆序可能被破坏下面的子树仍是合法堆。[2][11]伪代码// 下沉删除堆顶或修改某个位置后从上往下调整 siftDown(i): n heap.size while true: left 2 * i 1 right 2 * i 2 smallest i if left n and heap[left] heap[smallest]: smallest left if right n and heap[right] heap[smallest]: smallest right if smallest i: break swap(heap[i], heap[smallest]) i smallest // 往更小的那个孩子方向继续下沉为什么用“最后一个元素填 heap”完全二叉树的“最右下节点”正好对应数组最后一格删掉“最后一格”不会在中间留下空洞但我们想删除的是“堆顶”所以先用最后一个元素顶到堆顶位置填坑再删除最后一格这样数组仍然紧凑树仍是完全二叉树唯一问题是“顶上来的这个值”可能太大需要往下沉才能恢复堆序。[12][13]i smallest的含义每轮都在“当前结点 它的两个孩子”这 3 个位置里把最小值提到上面较大的那个元素逐步往下挪沿着某条子树一路下沉最终停在某个叶子或局部最小点整棵堆的父子关系就都合法了。2.3 push / pop / top 的整体伪代码push(x): heap.append(x) // 插到数组最后一格 siftUp(heap.size - 1) // 从末尾往上调整 pop(): // 弹出堆顶最小值 res heap[0] // 先记下当前堆顶 heap[0] heap.back() // 用最后一个元素填到堆顶 heap.pop_back() // 删除最后一格 siftDown(0) // 从根往下调整 return res top(): return heap[0] // 查看堆顶不删除复杂度pushsiftUp走一条从叶到根的路径长度是树高 (O(\log n))。popsiftDown从根到叶长度也是 (O(\log n))。top(O(1))。[1][8]三、几个典型堆题模板堆题本质上都是**有一个不断变化的候选集合需要随时取出“当前最小/最大”的元素。**关键设计是堆里存什么、什么时候 push / pop。3.1 模板一维护前 k 大或前 k 小问题类型求数组中第 k 大元素求“出现频率最高的前 k 个元素”等。[14]思路第 k 大用一个容量为 k 的最小堆堆中总是存“当前最大的 k 个数”堆顶就是这 k 个中的最小也就是整体的第 k 大。伪代码k_largest(nums, k): heap empty min-heap for x in nums: if heap.size k: push(heap, x) else if x top(heap): // 只比堆顶小的前 k 大中的“最小那个” pop(heap) // 舍弃旧的最小 push(heap, x) // 遍历结束时heap 中是前 k 大元素top(heap) 是第 k 大 return heap前 k 小类似可以用容量为 k 的最大堆或者在比较时反过来。3.2 模板二合并 k 个有序链表问题LEETCODE 23给你 k 条升序链表把它们合并成一条升序链表。[15][16]直觉有 k 条各自有序的“队伍”每次只需要从这 k 个“队头”中选出当前最小的一个接到结果链表后面选完某条队伍的队头后再把这条队伍的下一个元素加入候选候选集合大小始终 ≤ k用最小堆即可。伪代码伪语言// lists长度为 k 的数组lists[i] 是第 i 条有序链表的头结点 merge_k_sorted_lists(lists): // 堆里存(当前节点的值, 来自第几条链表, 指向该节点的指针) heap empty min-heap of (val, list_id, node_pointer) // 1. 初始化每条非空链表的头结点入堆 for i from 0 to lists.length - 1: if lists[i] ! null: push(heap, (lists[i].val, i, lists[i])) // 2. 结果链表用 dummy 头节点简化操作 dummy new ListNode(0) tail dummy // 3. 不断从堆中取出当前最小的节点接到结果链表 while heap 非空: (v, id, node) pop(heap) // 当前所有“队头”中最小的那个 tail.next node // 把它接到结果尾部 tail node // 尾指针后移 // 4. 把这个节点所在链表的下一个节点入堆 if node.next ! null: push(heap, (node.next.val, id, node.next)) return dummy.next关键堆中结构是(val, list_id, node_pointer)val参与比较list_id和node_pointer帮助找到“这个人后面谁要进堆”。堆大小始终 ≤ k每次弹出最小值接到结果即可。[17][15]3.3 模板三Dijkstra 最短路堆 贪心问题单源最短路边权非负。给一个图graph和起点src求从src到其他所有点的最短距离。[18][19]关键变量含义dist[v]当前已知的“从 src 到 v 的最短距离估计值”初始化为 INFdist[src] 0。[20]堆元素(d, u)d当前已知从 src 到 u 的距离估计u节点编号。堆是最小堆每次从中拿出当前“最小 d 的 u”。[18]伪代码dijkstra(graph, src): n graph.vertex_count dist array[0..n-1] filled with INF dist[src] 0 // 堆元素(当前已知最短距离估计, 节点编号) heap empty min-heap push(heap, (0, src)) while heap 非空: (d, u) pop(heap) // 如果堆里这个状态比 dist[u] 大说明它是“过期版本”丢弃 if d dist[u]: continue // 用 u 去更新所有邻居 v for 每条从 u 出发的边 (u, v, w): if dist[v] dist[u] w: dist[v] dist[u] w push(heap, (dist[v], v)) // v 有了更好的估计再入堆 return dist为什么正确直觉版[19][20]在所有“还没处理完的点”里堆总是挑出当前距离最小的点 u边权非负 ⇒ 想得到比dist[u]更短的路径必须先走到比 u 还近的点这样的点应该更早从堆里弹出所以当 u 以当前最小的 d 被弹出并不“过期”d dist[u]时可以认定dist[u]就是最终最短路然后用它去尝试缩短所有邻居的距离松弛不断重复最终得到所有点的最短距离。3.4 模板四滑动窗口最小值堆版本问题给定数组nums和窗口大小w对每个长度为 w 的连续子数组求其中的最小值返回结果数组。[21][22]窗口定义当遍历到 i 时窗口是[i-w1, i]当i w-1时才是完整窗口。伪代码sliding_window_min(nums, w): heap empty min-heap of (value, index) res empty list for i from 0 to nums.length - 1: push(heap, (nums[i], i)) // 新元素进堆 // 窗口第一次完整是 i w-1 之后 if i w - 1: left i - w 1 // 当前窗口左边界 // 把堆顶中“已经滑出窗口左边界”的元素弹掉 while heap 非空 and heap.top().index left: pop(heap) // 此时堆顶就是当前窗口内的最小值 res.append(heap.top().value) return res思想说明堆里存所有“曾经进入过当前或将来某个窗口”的元素(value, index)窗口向右滑动时新元素入堆通过while heap.top().index left不断弹出“早已不在当前窗口里的旧元素”[23]清理完后堆顶的index一定在[left, i]内是当前窗口内的合法元素且堆顶按value最小 ⇒ 它就是当前窗口的最小值。应用场景很多例如时间序列中“最近 w 个时间点的最低温度/最低价格”等分析。[24][25]四、常见疑问汇总4.1 为什么删除堆顶要用“最后一个元素”填 0 号位因为要保证树仍然是完全二叉树最右下的叶子正好对应数组最后一个元素删除这个叶子不会让中间出现“洞”想删的是堆顶就把最后一个元素搬到根再删掉最后一格然后自上而下siftDown恢复堆性。[11][12]4.2 siftUp 会不会漏比较一些该比较的节点不会。原因新值插在最后只可能影响路径[i \rightarrow parent(i) \rightarrow parent(parent(i)) \rightarrow \dots \rightarrow 0]这是一条唯一从插入点到根的路径每级都与父节点比较并必要时交换一路检查上去不在这条路径上的节点原本就是合法的堆子树没有被新值“越过”无需重新比较。[26][9]4.3 数组 vs struct指针 的二叉树表示struct Node { val, left*, right* }适用于任意形状的二叉树BST、线段树等指针灵活但内存分散访问不如数组紧凑。数组 下标公式仅适用于接近完全二叉树的结构例如堆、完全二叉树空间利用率高没有中间洞父子关系通过简单算式得出。[7]堆正好满足“完全二叉树 父子堆序”二合一自然用数组做存储最划算。五、做堆题时的思考框架写在最后总结一个通用 checklist面对堆题可以先自问三件事[27][28]这道题是不是“动态维护一堆候选里的极值”前 k 大/小、数据流中位数、滑动窗口最值、最短路等基本都是。堆里存什么结构比较依据是什么是值本身频率距离时间戳是否需要额外字段如下标、链表指针、来源 id来支持后续操作堆大小是否有限制典型是 k什么时候 push / pop固定容量 k 时要设计清楚push 之后是否需要立即 pop 掉多余的元素对于“窗口 / 有效区间”什么时候元素算“过期”应如何从堆顶清理把这几点想清楚再结合上面这几套siftUp / siftDown与模板伪代码绝大多数堆相关题目都能按套路拆解出来。