什么是堆

什么是优先队列

优先队列（Priority Queue）：一种特殊的队列，取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序

经验出发，我们可以用数组实现、也可以用链表实现，下面我们通过一张图看看它们的实现效果

通过对比可以看出来，要么时间复杂度过高，要么就只是在某一种操作上很突出，其他操作又相对难受了，整体都是不太尽人意。那么是否可以采用二叉树存储结构？假如二叉树的结点数是n，那么一棵完全二叉树的树高就是logN。利用这一性质，确实可以实现高速的管理数据

优先队列的重要性

优先队列和堆的暧昧关系

优先队列

能够完成下列操作的数据结构叫做优先队列

1. 插入一个数组
2. 取出最值（能获得数值，能实现删除）

堆

能够使用二叉树高效解决上述问题的数据结构被称为堆

回忆完全二叉树

没有满二叉树那么完美，最后可能会缺一些子树，但是一定一定要保证子树是按照层序编号排列的二叉树

二叉堆

如果一棵完全二叉树各结点的键值与一个数组的各元素具备如图所示的对应关系，那么这个完全二叉树就是二叉堆。

二叉堆的逻辑结构是完全二叉树，但是实际却是一个用1作为起点的一维数组来表示的。

若将表示二叉堆的数组命名为A,二叉堆的元素大小(元素个数)为H,那么二叉堆的元素就存储在A[1,…,H]中，其中根的下标为1.当给定一个结点的下标i时，就可以通过i/2、2 * i 、 2 * i +1轻松的算出来其父结点parent(i)、左子结点left(i)、右子结点right(i)。

举点栗子

二叉堆的特性

1. 结构性：用数组表示的完全二叉树；
2. 有序性：任一结点的关键字是其子树所有结点的最大值(或最小值)

“最大堆(MaxHeap)”,也称“大顶堆”：最大值

“最小堆(MinHeap)”,也称“小顶堆” ：最小值

最大堆的根中存储着最大元素，回看二叉堆的图，可以看出来它就是一个最大堆

堆的抽象数据类型描述(最大堆演示带入)

堆的主要操作

最大堆 MaxHeap H，元素ElementType item

1. MaxHeap Create( int MaxSize )：创建一个空的最大堆。
2. Boolean IsFull( MaxHeap H )：判断最大堆H是否已满。
3. Insert( MaxHeap H, ElementType item )：将元素item插入最大堆H。
4. Boolean IsEmpty( MaxHeap H )：判断最大堆H是否为空。
5. ElementType DeleteMax( MaxHeap H )：返回H中最大元素(高优先级)。

最大堆的创建

struct HeapStruct{
  int Capacity;//堆的最大容量 
  int Size;//堆的当前元素个数 
  ElementType *Elements;//存储堆元素的数组 
};
MaxHeap Create( int MaxSize )
{
  //创建一个容量为MaxSize的空的最大堆
  MaxHeap H = malloc(sizeof(struct HeapStruct));
  H->Elements = malloc((MaxSize + 1) * sizeof (ElementType));
  H->Size = 0;
  H->Capacity = MaxSize;
  H->Elements[0] = MaxData;//在数组没有用到0号索引处放置一个哨兵。待会再理解为什么要放置它 
  return H;
} 

最大堆的插入

操作流程:

1. 将这个新的元素插入到堆的最后一个元素，因为是用数组实现的堆，在数组的末尾直接修改数组的长度就可以实现插入或者删除操作。
2. 将其和它的父结点作比较，倘若它的数值比根节点的大，它就往上走，再比较，直到调整为符合二叉堆的性质为止。

void Insert(MaxHeap H, ElementType item) //将元素item插入最大堆H，其中H->Elements[0]已经定义为哨兵
{
  int i;
  if(IsFull(H))  
  {
    printf("堆已满");
    return ;
  }
  i = ++H->Size;//i指向插入后堆中的最后一个元素的位置
  for(; H->Elements[i/2] < item;i /= 2) H->Elements[i] = H->Elements[i/2];//向上调整。将这个插入的数据调整到合适它的位置
  H->Elements[i]  = item;//将item插入 
} 

H->Element[ 0 ] 是哨兵元素，它不小于堆中的最大元素，控制顺环结束。在加了哨兵来控制循环的结束以后，我们要考虑的内容就减少到怎么实现逻辑，不用多花时间去想循环要执行多少次

最大堆的删除

删除思路和插入是类似的，因为二叉堆的本质是用数组模拟的，删除数组的最后一位是很容易的，直接数组长度长度就可以了，所以这里的思路是用数组的最后一个元素替代要删除的元素，再调整

ElementType DeleteMax(MaxHeap H) 
{
  int Parent ,Child;//代表两个指针，分别指向父结点和子结点 
  ElementType MaxItem,temp;
  if(IsEmpty(H)) 
  {
    printf("最大堆为空");
    return ;
  }
  MaxItem = H->Elements[1];//取出根节点的最大值
  temp = H->Elements[H->Size--] ;//获取最大堆的最后一个元素从根节点Parent开始过滤 
  for(Parent = 1;Parent * 2 <= H->Size;Parent = Child)
  {
    Child = Parent * 2;
    if((Child != H->Size) && (H->Elements[Child] < H->Elements[Child+1])) Child ++;//Child指向左右子结点的较大者
    if(temp >= H->Elements[Child]) break;//满足最大堆的要求了，调整结束 
    else H->Elements[Parent] = H->Elements[Child];
  }
  H->Elements[Parent] = temp;
  return MaxItem;
}