堆（heap）简介及实现

堆（heap）简介及实现2013-05-24堆（heap）又被为优先队列（priority queue）。堆并不是队列的子集。回忆一下，在队列中，我们限定的操作是dequeue和enqueue。其中dequeue是按照进入队列的先后顺序来取出元素。在堆中，我们不是按照元素进入队列的先后顺序取出元素的，而是按照元素的优先级取出元素。

这就好像候机的时候，无论谁先到达候机厅，总是头等舱的乘客先登机，然后是商务舱的乘客，最后是经济舱的乘客。每个乘客都有头等舱、商务舱、经济舱三种个键值（key）中的一个。头等舱->商务舱->经济舱依次享有从高到低的优先级。

再比如，封建社会的等级制度，也是一个堆。在这个堆中，国王、贵族、骑士和农民是从高到低的优先级。

封建等级

Linux内核中的调度器（scheduler）会按照各个进程的优先级来安排CPU执行哪一个进程。计算机中通常有多个进程，每个进程有不同的优先级（该优先级的计算会综合多个因素，比如进程所需要耗费的时间，进程已经等待的时间，用户的优先级，用户设定的进程优先程度等等）。内核会找到优先级最高的进程，并执行。如果有优先级更高的进程被提交，那么调度器会转而安排该进程运行。优先级比较低的进程则会等待。“堆”是实现调度器的理想数据结构。

（Linux中可以使用nice命令来影响进程的优先级）