最小优先队列基本操作
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);
}
}
