概念和性质

1. 优先队列是允许至少下列两种操作的数据结构：插入（Insert）和删除最小者（DeleteMin）
2. 实现优先队列的数据结构叫二叉堆，他有两个性质，结构性和堆序性，堆的操作必须要到堆的所有性质都被满足才能终止
3. 堆是一颗被完全填满的二叉树，在树的底层上的元素从左到右填入的，这样的树叫完全二叉树。可以证明一颗高为\(h\)的完全二叉树有\(2^h\)到\(2^{h + 1} - 1\)个节点，他的高为\(?log N?\)
4. 可以用一个数组来表示一个完全二叉树，对于数组中任意位置\(i\)上的元素，其左儿子在位置\(2i\)处，右儿子在位置\(2i + 1\)处，它的父亲在位置\(?i / 2?\)处，

• 它的数据结构为

struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;

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

基本操作

插入

void Insert(ElementType X, PriorityQueue H)
{
    int i;
    if (IsFull(H))
    {
        Error("Priority queue is Full");
        return;
    }
    for (i = ++H->Size; H->Element[i / 2] > X; i /= 2) H->Element[i] = H->Element[i / 2];
    H->Element[i] = X;
}

优先队列

原文：https://www.cnblogs.com/Anthony-ling/p/11366180.html