知识卡片
优先队列只维护下一项优先者
当任务只需要反复找到并取出最高优先项,没有必要先让全部成员完全排序。优先队列把访问目标限定为当前最高优先项,插入/取出时只需维护足以确定这个目标的组织约束。
优先级由问题定义:调度可能选择最紧急任务,负载选择可能让最空闲服务器最高优先。它与先到先处理的FIFO队列不同,同优先级项是否保持到达顺序还需另定规则,本章堆实现不自动提供稳定顺序。
179服务器例以空闲程度决定优先。若保存的负载/优先级变化,还须维护对应结构,不能把对象字段改掉就假定堆顶自动更新;本段未提供并发监测或动态更新接口。
181正文把有序集合插入或提取都概括O(n)过宽:有序数组插入可能移动O(n),若从合适一端提取可较便宜;有序链表维护亦有不同定位成本。表示选择应分别评估操作,不凭统一一句重排决定全部成本。
226堆排序反复取极值生成顺序,常见堆序调整模型O(n log n)。是否额外空间、相对快排常数差仍看具体实现,不因本章heap每次realloc源码就套原地排序承诺;第10章已区分实际分配成本。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 优先队列只维护下一项优先者
- · 优先队列的描述
- · 优先队列的实现与分析
- · 相关主题
原书出处 · 4 处
- · 查看原书依据
快速确定最大或最小的元素。处理这种问题的方法之一,就是使用一个已排好序的数据集。通过这种方法,最大或最小的元素总是处在数据集的头部(这取决于使用升序还是降序排列)。然而,将数据集一遍又一遍地进行排序的代价是非常高的。并且很多情况下,将元素排序并不是操作的目的,最终我们可能在真正要做的工作之外做了很多
- · 查看原书依据
最空闲的服务器获取的优先级最高,因为它可以最好地处理服务请求。
- · 查看原书依据
局部有序的堆来实现优先队列。我们回忆一下堆的定义,位于堆顶部的结点往往优先级最高,而且插入或提取数据之后重新排列堆的复杂度仅为O(lg n)。 我们可以通过这种简单的方式typedef PQueue Heap来实现一个优先队列(见示例10-3)。这是因为优先队列与堆的操作基本相同,优先队列仅仅比堆多
- · 查看原书依据
堆排序 一种使用堆的高效排序算法(见第10章)。其时间复杂度为O(nlg n),并且不需要额外的存储空间。然而,平均情况下它比快速排序要慢一个常数因子。 内省排序 一种类似于快速排序的排序算法,只是在检测时,它会切换到堆排序,从而提高排序效率。由于这点改进,在某些情况下它会比快速排序效率略高。 桶排