数据结构之堆

堆：n个元素的序列{k1,k2,…,kn}，当且仅当满足下列关系时，成为堆：

image.png
如果将序列看成一个完全二叉树，非终端结点的值均小于或大于左右子结点的值。
利用树的结构特征来描述堆，所以树只是作为堆的描述工具，堆实际是存放在线形空间中的。
(09,17,65,23,45,78,87,53,31)--------------------(87,78,53,45,65,09,31,17,23)
image.png
层次遍历
最小堆a[]={09,17,65,23,45,78,87,53,31}
最大堆b[]={87,78,53,45,65,09,31,17,23}

Heaps(priority queues)

堆，这个数据结构的诞生主要是因为queue需要priority。

也就是队列里面的数据不遵循队列先进先出的规则而是有特定的优先级要求。这方面的一个应用是，操作系统对进程的处理。有些任务需要较长的时间处理，有些则很短时间就可以处理完，如果都按照进队的顺序处理显然是不合理的。堆这个数据就能很好地实现这些功能。

堆的实现

堆可以用简单的链表（linked list)实现。这样的话，Insert操作的时间复杂度是O(1)(直接插入），DeleteMins的操作就要耗费多一点的时间，为O(N)。当然另外一种实现可以用排好序的链表，这样删除操作的时间复杂度就为O(1)，而插入操作要达到O(N)。但是通常情况下，插入操作要更频繁一些。

如果用二叉搜索树就未免有点大才小用了。毕竟，堆只需要插入和删除操作，而二叉搜索树提供了很多其他的操作。另外一个问题是，二叉搜索树的Delete操作会使树越来越不平衡（极端情况下左子树为空，右子树满）不过这样对于二叉搜索树的操作也只是时间复杂度也只是增加常数级的时间。log（2N）- log（N）= 1.

综合上面的考虑，堆的数据结构的实现最为常用的是binary heaps。

Binary Heaps

二叉堆的实现用数组实现。二叉堆需要满足以下两个条件。(当然这些条件这样设置都是有原因的）

structure property 结构原则：

二叉堆是一棵完全二叉树。

heap order property 堆的排序原则：

堆的根元素应该是最小的。而且这个定义对堆中的任意子树都适用。

就这样的堆来说，插入和删除操作都是log（N）的，不过我们知道时间复杂度的考虑都是以最坏的时间来考虑的。平均来说，插入和删除操作都将比log（N）要好。

堆的数据结构的定义：

struct HeapStruct
{
    int Capacity;
    int Size;
    ElementType *Element;
}