优先队列学习笔记
一. 应用需求
1. 优先级队列：其中的元素接受的访问次序未必是先进先出。每次从队列中取出的是具有最高优先权的元素。
2.夜间门诊
假设某家医院在夜间只安排了一位医生值班，那么他要按照什么样的次序为到来的病人提供服务呢？如果是一般的感冒发烧，自然是采用先来先服务的次序。倘若某位病人发生了骨折，相对于一般的病人，他更应优先地接收处置和治疗。而即便是在这位骨折病人接收处置的过程中，如果又有一位心脏病发的病人到来，相对而言，骨折就显得不那么重要了。这时，医生会优先去治疗这位刚刚到来的心脏病患者，先前的先到先服务原则已不再适用。
3.处理器调度
操作系统对于多任务的调度策略与门诊医生类似。操作系统类比于医院，CPU类似于门诊医生，而同时参与调度的计算任务，则可类比于同时等候门诊的一批病人。每个任务都要一个指标，有的数值更大，有的数值略小。当然，这些指标都是动态变化的，而操作系统总会挑选指标最大的那个任务，交由CPU处理。指标数值可类比于病人的病情严重程度，指标的数值越大，则会优先接受服务。我们称之为“优先级别”，简称“优先级”。
二. 问题模式
- 服务端（server algorithm）：医生，CPU，某种算法——Huffman编码算法，以及扫描线算法
- 客户端(clients data)：病患，计算任务，数据对象
- 优先级(importance priority)：数据集中的每一个数据对象都有一个表示其重要程度的指标
- 优先级队列(priority queue)：兑现循优先级访问的数据访问方式，记录并维护所有数据项之间的相对优先级
- 调度器(scheduler)：根据优先级队列，将最高优先级的元素输送给所对应的服务端或者算法