知识卡片

普通读书笔记卡 · 3613.d · 生成模型:未记录

优先队列只维护下一项优先者

理解等级:中级

当任务只需要反复找到并取出最高优先项,没有必要先让全部成员完全排序。优先队列把访问目标限定为当前最高优先项,插入/取出时只需维护足以确定这个目标的组织约束。

优先级由问题定义:调度可能选择最紧急任务,负载选择可能让最空闲服务器最高优先。它与先到先处理的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),并且不需要额外的存储空间。然而,平均情况下它比快速排序要慢一个常数因子。 内省排序 一种类似于快速排序的排序算法,只是在检测时,它会切换到堆排序,从而提高排序效率。由于这点改进,在某些情况下它会比快速排序效率略高。 桶排

    参考来源

    - 位置:《算法精解:C语言描述》第10章《第10章 堆和优先队列》(spine1308;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1275.html;u170-ch10-001)。 - 结论依据:170开篇重复排序代价、调度/负载应用全文实读;179优先队列定义与服务器例承接,限定它维护优先访问而非全局排序。 - 原始内容:快速确定最大或最小的元素。处理这种问题的方法之一,就是使用一个已排好序的数据集。通过这种方法,最大或最小的元素总是处在数据集的头部(这取决于使用升序还是降序排列)。然而,将数据集一遍又一遍地进行排序的代价是非常高的。并且很多情况下,将元素排序并不是操作的目的,最终我们可能在真正要做的工作之外做了很多 - 位置:《算法精解:C语言描述》第10章《优先队列的描述》(spine1315;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1282.html;u179-ch10-001)。 - 结论依据:179服务器例以空闲程度决定优先。若保存的负载/优先级变化,还须维护对应结构,不能把对象字段改掉就假定堆顶自动更新;本段未提供并发监测或动态更新接口。 - 原始内容:最空闲的服务器获取的优先级最高,因为它可以最好地处理服务请求。 - 位置:《算法精解:C语言描述》第10章《优先队列的实现与分析》(spine1317;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1284.html;u181-ch10-001)。 - 结论依据:181正文把有序集合插入或提取都概括O(n)过宽:有序数组插入可能移动O(n),若从合适一端提取可较便宜;有序链表维护亦有不同定位成本。表示选择应分别评估操作,不凭统一一句重排决定全部成本。 - 原始内容:局部有序的堆来实现优先队列。我们回忆一下堆的定义,位于堆顶部的结点往往优先级最高,而且插入或提取数据之后重新排列堆的复杂度仅为O(lg n)。 我们可以通过这种简单的方式typedef PQueue Heap来实现一个优先队列(见示例10-3)。这是因为优先队列与堆的操作基本相同,优先队列仅仅比堆多 - 位置:《算法精解:C语言描述》第12章《相关主题》(spine1358;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1324.html;u226-ch10-001)。 - 结论依据:226堆排序反复取极值生成顺序,常见堆序调整模型O(n log n)。是否额外空间、相对快排常数差仍看具体实现,不因本章heap每次realloc源码就套原地排序承诺;第10章已区分实际分配成本。 - 原始内容:堆排序 一种使用堆的高效排序算法(见第10章)。其时间复杂度为O(nlg n),并且不需要额外的存储空间。然而,平均情况下它比快速排序要慢一个常数因子。 内省排序 一种类似于快速排序的排序算法,只是在检测时,它会切换到堆排序,从而提高排序效率。由于这点改进,在某些情况下它会比快速排序效率略高。 桶排