Name: 最小优先队列
    Copyright:
    Author: 巧若拙
    Date: 24-11-14 21:13
    Description:
    最小优先队列基本操作：
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

#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);    
    }    
}

增加一个还算实用的函数：

int SearchKey(MinPQue q, int pos, ElemType k)//查找以第pos个元素为根节点的最小堆中关键字值为k的元素下标，未找到则返回-1 （递归） 
{
    int flag;
    
    if (pos > q.size || q.vec[pos-1] > k)
        return -1;
    if (q.vec[pos-1] == k)
        return pos-1;
        
    flag = SearchKey(q, pos*2, k);//在左子树中递归查找 
    if (flag == -1)//不在左子树中 ，则继续在右子树中递归查找  
        flag = SearchKey(q, pos*2+1, k);
    
    return flag;
}

int SearchKey_2(MinPQue q, int pos, ElemType k)//查找以第pos个元素为根节点的最小堆中关键字值为k的元素下标，未找到则返回-1（非递归） 
{
    int Stack[MAXSIZE] = {0};
    int top = -1;
    
    while ((pos <= q.size && q.vec[pos-1] <= k) || top >= 0)//类似先序遍历二叉树的方式查找 
    {
        if (pos <= q.size && q.vec[pos-1] <= k)
        {
            if (q.vec[pos-1] == k)
                return pos-1;
            Stack[++top] = pos;//该结点入栈 
            pos *= 2; //搜索左孩子 
        }
        else
        {
            pos = Stack[top--] * 2 + 1; //结点退栈并搜索右孩子 
        }
    }
    
    return -1;
}