插队:来了个更急的
四个任务排着队的时候,又来了一个优先级 6 的「回滚」。 补全后输出第一个被处理的任务。
一个够用的堆至少要有哪几样
手写一个够用的大顶堆,至少要有【0】。
插入和弹出为什么是 O(log n)
堆的插入和弹出都是 O(log n),因为【0】。
这个堆里有几个元素
运行下面这段程序: def push(h, x): h.append(x) i = len(h) - 1 while i > 0 and h[(i - 1) // 2] < h[i]: p
第一步:数组和上浮插入
最终作品第一步:用一个列表当堆,写出 push(追加到末尾 + 上浮)。 五个数插完之后输出堆顶。
第二步:下沉和弹出
加上 sift_down 和 pop。把两次弹出的结果拼起来输出(用 / 隔开)。
第三步:从乱序数组直接建堆
加上 heapify:不用一个个 push,从最后一个有孩子的节点倒着下沉。 建好之后把整个数组拼起来输出。
第四步:拿它去求 Top-K
用前面写好的堆求前 3 大,把结果拼起来输出(用 / 隔开)。
交付:堆 + Top-K + 优先队列
这是这条路线的最终作品。把 push、sift_down、pop、heapify、top_k 全写出来,再写一个按优先级出队的 pop_max,然后一次验完五条: 五个数插完,堆顶是 24,一共 5 个 连弹两次,拿到 24 和 23 he
图里的那些点叫什么
来回 单程 一张图里,那些被连起来的点叫【0】。