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

最小优先队列基本操作