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

若采用数组或链表实现优先队列
数组:
插入一元素总是插入尾部 ~Θ(1)
删除一查找最大(或最小)关键字 ~Θ(n)
从数组中删去需要移动元素 ~O(n)
链表:
插入一元素总是插入链表的头部 ~Θ(1)
删除一查找最大(或最小)关键字 ~Θ(n)
删去结点 ~Θ(1)
有序数组:
插入 - 找到合适的位置 ~ O(n)或O(log₂N)
移动元素并插入 ~O(n)
删除 - 删去最后一个元素 ~Θ(1)
有序链表:
插入- 找到合适的位置 ~O(n)
插入元素 ~Θ(1)
删除- 删除首元素或最后元素 ~Θ(1)

• 我们用优先队列的完全二叉树表示

堆的两个特性：

• 结构性：用数组表示的完全二叉树；
• 有序性：任意结点的关键字是其子树所有节点的最大值（或最小值）
     “最大堆(MaxHeap)”,也称“大顶堆”：最大值
     “最小堆(MinHeap)”,也称“小顶堆”：最小值

最大堆：

typedef int ElementType;
typedef struct HeapStruct{
    ElementType *elements;
    int size; //堆的当前元素个数
    int capacity; //堆的最大容量
} *MaxHeap;
#define MaxData 10000
//创建最大堆
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;
    return h;
}
//判断堆满
bool isFull(MaxHeap h)
{
    return h->size == h->capacity;
}
//判空
bool isEmpty(MaxHeap h)
{
    return h->size == 0;
}

最大堆插入

//往堆里插入元素 T=O(logN)
void insert(MaxHeap h, ElementType item)
{
    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;
}

以上可见插入操作时间复杂度为T = O(logN)

最大堆删除

//删除最大值
ElementType deleteMax(MaxHeap h)
{
    if(isEmpty(h)){
        printf("最大堆已为空");
        return -1;
    }
    ElementType maxItem = h->elements[1];
    ElementType item = h->elements[h->size--];
    int parent = 1, child;
    for (; 2*parent <= h->size; parent = child) {
        child = 2*parent ;
        
        if(child != h->size && h->elements[child + 1] > h->elements[child])
            child++; //child指向左右子结点较大者
        if(h->elements[child] <= item)
            break;
        else{
            h->elements[parent] = h->elements[child];
        }
    }
    h->elements[parent] = item;
    return maxItem;
}

以上可见删除操作时间复杂度为T = O(logN)

最大堆的构建

如果我们用最大堆插入的方式构建最大堆，其时间复杂度为T = O(NlogN)。
我们可以先将数据输入到数组，然后再调整。其时间复杂度为T = O(N/2logN)。

void MaxHeapAdjust(MaxHeap h, int p);
//构建堆
MaxHeap buildMaxHeap()
{
    MaxHeap h = create(10);
    int arr[] = {49,38,65,97,76,13,34,27,49,11};
    for (int i = 1; i <= h->capacity; i++) {
        h->elements[i] = arr[i - 1];
        h->size++;
    }
    /**
     调整堆
     思路跟删除堆相同
     从 h->size/2 的位置往前依次调整堆
     */
    for(int i = h->size/2; i > 0; i--)
    {
        MaxHeapAdjust(h, i);
    }
    return h;
}
//调整堆
void MaxHeapAdjust(MaxHeap h, int p)
{
    int parent = p, child;
    int item = h->elements[p];
    for (; parent * 2 <= h->size; parent = child) {
        child = 2 * parent;
        if(child != h->size && h->elements[child + 1] > h->elements[child])
            child++;
        
        if(item >= h->elements[child])
            break;
        else
            h->elements[parent] = h->elements[child];
    }
    
    h->elements[parent] = item;
}

最大堆堆排序

我们直接调用删除堆，返回最大值的方式，就可以获取从大到小的排序。

//堆排序
void MaxHeapSort(MaxHeap h)
{
    printf("堆排序：");
    for (int i = 1; i <= h->capacity; i++) {
        ElementType item = deleteMax(h);
        printf("%d ",item);
    }
}

调用堆排序

 MaxHeap h = buildMaxHeap();
 MaxHeapSort(h);
执行结果：堆排序：97 76 65 49 49 38 34 27 13 11