最小优先队列基本操作

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int ElemType;
typedef int Status; //函数类型，其值是函数结果状态代码，如OK等

typedef struct MinPriorityQueue{
    ElemType vec[MAXSIZE] ;//存储队列各元素关键字的数组
    int size;//队列实际长度
} MinPQue; //最小优先队列结构体

void MinHeapSiftDown(ElemType S[], int n, int pos);
void MinHeapSiftUp(ElemType S[], int n, int pos);
void CreateMinPQue(MinPQue *q, int n); //随机构造一个长度为n的最小优先队列
void PrintMinPQue(MinPQue q);//输出最小优先队列的各个元素
void Insert(MinPQue *q, ElemType x);//把元素x插入队列S中
ElemType MinKeyword(MinPQue q);//返回队列S中具有最小关键字的元素（即vec[0]）
ElemType ExtractMin(MinPQue *q);//删除并返回队列S中具有最小关键字的元素（即vec[0]）
void ChangeKey(MinPQue *q, int pos, ElemType k);//将第pos个元素的关键字值改为k

int main(void)
{
    MinPQue a;
    int n = 8;
    int pos = 3;
    int k = 66;
   
    CreateMinPQue(&a, n); //随机构造一个长度为n的最小优先队列
    PrintMinPQue(a);//输出最小优先队列的各个元素
   
    printf("最小值：%d\n", MinKeyword(a));
    printf("删除最小值：%d\n", ExtractMin(&a));
    PrintMinPQue(a);//输出最小优先队列的各个元素
   
    printf("将第%d个元素的关键字值改为%d\n", pos, k);
    ChangeKey(&a, pos, k);//将第pos个元素的关键字值改为k
    PrintMinPQue(a);//输出最小优先队列的各个元素
   
    return 0;
}

/*
函数功能：向下调整二叉堆的第pos个元素，使其满足最小堆的特征
初始条件：二叉堆S[]已经存在
操作结果：定位第pos个元素的孩子结点中较小的一个，当孩子结点比双亲结点小时，通过向上移动孩子结点值的方式，确保双亲结点小于孩子结点，以满足最小堆的特征。
采用类似插入排序的方法，向上移动数据，腾出插入位置，将原堆中第pos个元素向下调整到适当的位置。
注意：因C语言的数组下标从0开始，故第pos个元素在数组中表示为S[pos-1]。
若要删除二叉堆的第一个元素，则将最后一个元素放到根部，然后对根结点做向下调整操作，得到新的最小堆。
*/   
void MinHeapSiftDown(ElemType S[], int n, int pos)
{
    ElemType temp = S[pos-1];
    int child = pos * 2; //指向左孩子
   
    while (child <= n)
    {
        if (child < n && S[child-1] > S[child]) //有右孩子，且右孩子更小些，定位其右孩子
            child += 1;
        
        if (S[child-1] < temp) //通过向上移动孩子结点值的方式，确保双亲小于孩子
        {
            S[pos-1] = S[child-1];
            pos = child;
            child = pos * 2;
        }
        else
            break;
    }
   
    S[pos-1] = temp; //将temp向下调整到适当位置
}

/*
函数功能：向上调整二叉堆的第pos个元素，使其满足最小堆的特征
初始条件：二叉堆S[]已经存在
操作结果：定位第pos个元素的双亲结点，当孩子结点比双亲结点小时，通过向下移动双亲结点值的方式，确保双亲结点小于孩子结点，以满足最小堆的特征。
采用类似插入排序的方法，向下移动数据，腾出插入位置，将原堆中第pos个元素向上调整到适当的位置。
注意：因C语言的数组下标从0开始，故第pos个元素在数组中表示为S[pos-1]。
若要插入新元素，则将新元素插入到堆的最末位置，然后对新元素做向上调整操作，得到新的最小堆。
*/   
void MinHeapSiftUp(ElemType S[], int n, int pos)
{
    ElemType temp = S[pos-1];
    int parent = pos / 2; //指向双亲结点
   
    if (pos > n) //不满足条件的元素下标
        return;
   
    while (parent > 0)
    {
        if (S[parent-1] > temp) //通过向下移动双亲结点值的方式，确保双亲小于孩子
        {
            S[pos-1] = S[parent-1];
            pos = parent;
            parent = pos / 2;      
        }
        else
            break;
    }
    S[pos-1] = temp; //将temp向上调整到适当位置
}

void CreateMinPQue(MinPQue *q, int n) //随机构造一个长度为n的最小优先队列
{
    int i;
   
    q->size = 0;
    for (i=0; i<n; i++)
    {
        Insert(q, rand()%51);
    }
}

void PrintMinPQue(MinPQue q)//输出最小优先队列的各个元素
{
    int i;
    for (i=0; i<q.size; i++)
        printf("%4d", q.vec[i]);
    printf("\n");
}

void Insert(MinPQue *q, ElemType x)//把元素x插入队列S中
{
    q->vec[q->size++] = x;
    MinHeapSiftUp(q->vec, q->size, q->size);
}

ElemType MinKeyword(MinPQue q)//返回队列S中具有最小关键字的元素（即vec[0]）
{
    return q.vec[0];
}

ElemType ExtractMin(MinPQue *q)//删除并返回队列S中具有最小关键字的元素（即vec[0]）
{
    ElemType x = q->vec[0];
    q->vec[0] = q->vec[--q->size];
    MinHeapSiftDown(q->vec, q->size, 1);
   
    return x;
}

void ChangeKey(MinPQue *q, int pos, ElemType k)//将第pos个元素的关键字值改为k
{
    if (k < q->vec[pos-1]) //关键字值变小，向上调整最小堆
    {
        q->vec[pos-1] = k;
        MinHeapSiftUp(q->vec, q->size, pos);   
    }
    else if (k > q->vec[pos-1])  //关键字值变大，向下调整最小堆
    {
        q->vec[pos-1] = k;
        MinHeapSiftDown(q->vec, q->size, pos);   
    }   
}