下载文档原格式
纸上谈兵：堆（heap）堆(heap)⼜被为优先队列(priority queue)。
尽管名为优先队列，但堆并不是队列。
回忆⼀下，在中，我们可以进⾏的限定操作是dequeue和enqueue。
dequeue是按照进⼊队列的先后顺序来取出元素。
⽽在堆中，我们不是按照元素进⼊队列的先后顺序取出元素的，⽽是按照元素的优先级取出元素。
这就好像候机的时候，⽆论谁先到达候机厅，总是头等舱的乘客先登机，然后是商务舱的乘客，最后是经济舱的乘客。
每个乘客都有头等舱、商务舱、经济舱三种个键值(key)中的⼀个。
头等舱->商务舱->经济舱依次享有从⾼到低的优先级。
再⽐如，封建社会的等级制度，也是⼀个堆。
在这个堆中，国王、贵族、骑⼠和农民是从⾼到低的优先级。
封建等级Linux内核中的调度器(scheduler)会按照各个进程的优先级来安排CPU执⾏哪⼀个进程。
计算机中通常有多个进程，每个进程有不同的优先级(该优先级的计算会综合多个因素，⽐如进程所需要耗费的时间，进程已经等待的时间，⽤户的优先级，⽤户设定的进程优先程度等等)。
内核会找到优先级最⾼的进程，并执⾏。
如果有优先级更⾼的进程被提交，那么调度器会转⽽安排该进程运⾏。
优先级⽐较低的进程则会等待。
“堆”是实现调度器的理想数据结构。
(Linux中可以使⽤nice命令来影响进程的优先级)堆的实现堆的⼀个经典的实现是完全⼆叉树(complete binary tree)。
这样实现的堆成为⼆叉堆(binary heap)。
完全⼆叉树是增加了限定条件的⼆叉树。
假设⼀个⼆叉树的深度为n。
为了满⾜完全⼆叉树的要求，该⼆叉树的前n-1层必须填满，第n层也必须按照从左到右的顺序被填满，⽐如下图:为了实现堆的操作，我们额外增加⼀个要求: 任意节点的优先级不⼩于它的⼦节点。
如果在上图中，设定⼩的元素值享有⾼的优先级，那么上图就符合该要求。
这类似于“叠罗汉”。
叠罗汉最重要的⼀点，就是让体重⼤的参与者站在最下⾯，让体重⼩的参与者站在上⾯ (体重⼩，优先级⾼)。
堆排序的筛选方法堆排序是一种常见的排序算法，它利用完全二叉树的性质来进行排序。
堆其实就是一个满足特定条件的完全二叉树，它分为最大堆和最小堆两种类型。
在堆排序中，我们需要先构建一个堆，然后逐步将堆顶元素与末尾元素交换，并对剩余的部分重新调整成一个堆，直到整个数组有序。
堆排序的筛选方法是指在构建和调整堆的过程中所采用的方法，它包括构建堆的过程和调整堆的过程。
堆排序的筛选方法主要包括两个部分：构建堆和调整堆。
一、构建堆1. 自底向上构建堆：首先从最后一个非叶子节点开始，依次对每个非叶子节点进行调整，使得以该节点为根的子树成为一个堆。
这样可以保证每个子树都是堆，最终整个数组就构成了一个堆。
2. 自顶向下构建堆：从根节点开始，依次对每个节点进行调整，使得以该节点为根的子树成为一个堆。
这种方法比较直观，但效率较低，因为需要对每个节点进行逐个调整。
二、调整堆1. 自顶向下调整堆：当堆顶元素发生变化时，需要对整个堆进行调整，保证堆的性质。
自顶向下调整堆的方法是将根节点与其子节点进行比较，并根据需要进行交换，然后递归地对子节点进行调整。
2. 自底向上调整堆：当堆的某个非叶子节点发生变化时，需要对堆进行调整。
自底向上调整堆的方法是将父节点与其子节点进行比较，并根据需要进行交换，然后递归地对父节点进行调整。
在实际应用中，通常采用自底向上构建堆和自顶向下调整堆的方法，这样可以保证效率和性能的平衡。
堆排序的筛选方法是堆排序算法中非常重要的一部分，它直接影响了算法的效率和性能。
在实现堆排序算法时，需要充分考虑筛选方法的选择，以达到最佳的排序效果。
堆排序的筛选方法是构建和调整堆的关键步骤，它包括构建堆和调整堆两个部分。
在实际应用中，需要根据具体情况选择合适的筛选方法，以确保排序算法的效率和性能。
