一个优先级队列的实现

优先级队列概念

从用户的角度看，优先级队列支持，队列元素出队列时，总是输出当前队列中的最大或者最小值。

我们要实现的接口有：

• 创建队列的接口

• 销毁队列的接口

• 把一个元素入队列的接口

• 输出队列中的最大或者是最小值的接口

优先级队列的实现，一般采用大顶堆或者小顶堆的数据结构。我们以大顶堆为例说明问题。
一个大顶堆是一个完全二叉树，这个二叉树的每个节点的子节点都比父节点小。

我们只要搞清入队和出队的逻辑，就搞清了全部逻辑。先看入队的逻辑。我们面对的问题是
现在队列已经是一个大顶堆了，如何调整数据结构，使得入队后的队列还是一个大顶堆。
我们把要入队的元素放在这个完全二叉树的最末尾，入队的元素如果比他的父节点小，那么
现在就是一个大顶堆，如果入队元素比父节点大，那么交换入队元素和父节点，在入队元素
和父节点组成的子树中，满足大顶堆的逻辑，因为入队元素如果比父节点大，那么一定大于
可能的父节点的左节点。交换后的整个树，只可能在父节点的位置(数值已经是入队元素)和
父节点的父节点处不满足大顶堆的逻辑，如果不满足，也就是父节点比他的父节点还大，迭代
一开始的逻辑即可。

    B             B             A
   / \           / \           / \
  C   O         A             B
 / \           / \           / \
O   A         O   C         O   C

     if A > C        if A > B
     ------->        ------->

如上，入队后，我们就立马把队列调整成大顶堆逻辑。出队的时候，直接取根节点就是最大值。
但是，根节点输出后，我们还要把这个队列调整成大顶堆逻辑。一般，我们把整个树最末尾
的节点填到根节点的位置，这个时候，一般整个树就不是大顶堆的结构。我们把根节点和他
比较大的一个子节点做交换，这样保证交换后的根节点和他的子节点满足大顶堆逻辑，可能
不满足大顶堆逻辑的地方是，交换数值的子节点位置和他的子节点们，同样的逻辑做迭代即可。

    A             C             B
   / \           / \           / \
  B   D         B   D         C   D
 / \           / \           / \
O   C         O             O

 A出队，C换到堆顶     if C < B 或者 C < D, 且 B > D
 --------------->     ----------------------------> 

注意如上的分析都是逻辑层面的分析。

C语言实现

实现上要注意的地方有：

• 可以用数组实现树，那么求一个节点的左节点、右节点和父节点可以是：

  #define get_left(i)		(2 * (i) + 1)
  #define get_right(i)		(2 * (i) + 2)
  #define get_father(i)		((i) % 2 ? (i) / 2 : (i) / 2 - 1)

• 树的元素可以用void *来做，这样可以支持不同的数据结构元素。

• 可以要求用户提供比较函数，一个是因为树的元素是void *，内部实现自己并不知道怎么比较，
  另一个是因为，用户可以灵活的改变比较函数，按照不同的逻辑定义元素大小的规则。

具体实现的代码在：https://github.com/wangzhou/tests/master/priority_q