本篇文章主要基于算法algorithm第四版
背景：处理有序元素时，不一定要求所有数据有序，只要求处理当前最大（优先级最高）的元素 优先级队列：支持 删除最大元素 和 插入元素 两种操作的一种数据结构
优先级队列的基本实现可以使用 有序 或 无序 的 数组 和 链表
无序数组或链表：删除最大元素时需要将数组遍历一遍造出最大元素，插入则无需额外操作有序数组或链表：删除元素时只需直接删除第一个，插入元素需要保持数据的有序（类似于插入排序） 特点：这类实现的插入元素或删除最大元素在最坏情况下需要线性时间来完成基于数组或链表的操作最坏情况下需线性时间完成，而用堆来实现优先级队列可以使两种操作更快执行
因为二叉堆是完全二叉树，所以只用数组就可以表示，在二叉堆中位置为k的父结点的位置为ceil（k/2），而子结点为2k和2k+1，这样方便的表示也使其能通过数组索引方便地上下移动元素
在插入或删除堆中元素时，会打破堆的状态，所有需要对堆进行遍历来恢复堆的状态（堆有序 以及 完全二叉树），这个过程称为堆的有序化。有序化过程主要分为两类：
某个结点的优先级上升（或是在堆底加入新元素时），需要由下至上恢复堆的顺序，且形象地称之为上浮某结点优先级下降（如将根节点替换为更小的元素时），需要由上至下恢复堆的顺序，称之为下沉通过有序化的两个过程我们便可实现插入元素以及删除最大元素的操作 插入元素：将新元素加到数组末尾，增加堆的大小并让这个新元素 上浮 到合适的位置 删除最大元素：从数组删去最大的元素并将最后一个元素放到堆顶，减小堆的大小，并让该元素 下沉 到合适的位置 
优先队列可以变成一种排序方法，将所有元素插入一个查找最小元素 的优先队列，然后再重复调用删除最小元素的操作来将他们按顺序删去。以此方法来实现排序。 在进行堆排序时，首先要将一组无序数据建立起堆，然后再重复删去最大（或小）元素
这一阶段完成排序工作。从堆中删除最大元素，然后放入堆缩小后数组中空出的位置，将堆尾元素放到堆顶，进行下沉操作。以此方法重复，则一个最大堆可以得到一个升序序列。
本人学识尚浅，有什么不对的欢迎指出，一起交流交流^ ^
新闻热点
疑难解答
