优先队列

特殊的队列，取出元素的顺序是依照元素的优先权(关键字)大小，而不是元素进入队列的先后顺序。

主要操作

• 插入
• 删除
  然后从这个集合中挑最大，或是最小

数组实现

• 插入
  • 元素总是插入到尾部 O(1)
• 删除
  • 查找最大(或最小)的元素关键字 O(n)
  • 删除以后，需要移动元素，后面的往前移动 O(n)

链表实现

• 插入
  • 元素总是插入到尾部 O(1)
• 删除
  • 查找最大(或最小)的元素关键字 O(n)
  • 删去节点 O(1)

有序数组

• 插入

  • 找到合适的位置 ~O(n) 或是O(log2(n))
  • 移动元素并插入 O(n)

• 删除

  • 删去最后一个元素 ~O(1)

有序链表  

• 插入

  • 找到合适的位置 O(n)
  • 插入 O(1)

• 删除

  • 删除首元素或是尾元素 O(1)

是否使用二叉树存储结构？

二叉搜索树

可能会变成斜树。（因为右节点是最大，删除一直是右节点）
如果变成了斜树，最后其实和链表差不多了。

堆

结构性：用数组表示的完全二叉树
有序性：任一节点的关键字是其子树所有节点的最大值（或最小值）

• “最大堆”，“大顶堆”：最大值
• “最小堆”，“小顶堆”：最小值

Paste_Image.png

堆的主要操作集

• Heap Create(int MaxSize)
  创建一个堆

• boolean IsFull(Heap H)
  判断是否已经满了

• boolean IsEmpty(Heap H)
  判断堆是否为空

• Insert(Heap H,ElementType item)
  将元素item插入最大堆H

• DeleteMax(Heap H)
  返回H中最大的元素

以最大堆为例

#结构
struct HeapStruct{
  ElementType *element;/*存储堆得数组*/
  int Size;/*堆得当前元素个数*/
  int /*堆得最大容量*/
 }

#创建
Create(int MaxSize){
    MaxHeap H = malloc(sizeof(struct HeapStruct));
    H->elemnts = malloc( (MaxSize + 1)* sizeof(ElementType));
    H->size= 0;
    H->element[0]=MaxData ;/*无穷大*/
    return H;
}

插入

插入图例：

Paste_Image.png

#插入
void insert(MaxHeap H ,ElementType item){
 int i;
 if(IsFull(H)){
    printf("堆已经满了")；
    return;
  }
  i =  ++H->Size;/*堆增大一个，而且将这个值赋给i*/
  for(;item>H->element[i/2]  && i >1;){
    H->element[i] = H->element[i/2];
    i=i/2;
  }
  H->Element[i]=item;
}




void insert(MaxHeap H ,ElementType item){
 int i;
 if(IsFull(H)){
    printf("堆已经满了")；
    return;
  }
  i =  ++H->Size;/*堆增大一个，而且将这个值赋给i*/
  for(;item>H->element[i/2] ;){
/*这里，没有比较i是否大于1 ,因为在设计存储结构的时候，将H->element[0]中存储了一个 无穷大，这样没有值会大于这个无穷大，所以节省每一轮的一个比较操作*/
    H->element[i] = H->element[i/2];
    i=i/2;
  }
  H->Element[i]=item;
}

删除

删除图例：

Paste_Image.png

tips:
必须要注意,最后一个节点，并不一定是最小的节点。

#删除
ElementType DeleteMax(MaxHeap H){
    if(IsEmpty(H)){
        printf("空堆");
        return;
    }
    
    ElementType last = H->element[H->size--];
    ElementType max = H->element[0];
    
    int Child;
    /*这是一棵完全二叉树，所以parent*2<=H->Size 说明有左儿子*/
    for(int Parent =1;parent*2 <=H->Size;Praent=Child){
        child=parent*2;
        //如果child！=H->Size ，说明右儿子存在
        if((Child!=H->Size) && (H->element[Child]) < H->element[Child+1]){
            Child++;//指向右儿子
        }

        if(temp>H->element[Child]) break;
        else{
            H->element[Parent] = H->element[Child];
        }
    }
    H->element[Parent] =last;
     return max;
}

#建立堆

将已经存在的N个元素按最大堆得要求存放在一个一维数组中

方法1：通过插入操作，将N个元素一个个相继插入到一个初始为空的堆中。
时间代价O(NlogN)

方法2：在线性时间复杂度下建立最大堆
1.将所有的元素按照输入顺序存入，满足完全二叉树的结构特性
2.调整位置，满足最大堆的有序要求

#如何调整

图例：
从第一个有子节点的位置开始：

Paste_Image.png

时间复杂度：
O(n)