《大话数据结构》读书笔记之二叉堆基本操作（最大堆）
/*Name: 二叉堆基本操作（最大堆）
Copyright:
Author: 巧若拙
Date: 24-09-14 20:26
Description:
实现的最大堆的基本操作，包括向上，或向下调整二叉堆的第pos个元素，使其满足最大堆的特征；
构造最大堆，利用最大堆进行堆排序和找第k大的数。
如果要构造最小堆，则只需改变一下调整二叉堆时判断的条件即可。
*/
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>
#define MAXSIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int ElemType;
typedef int Status; //函数类型，其值是函数结果状态代码，如OK等
void MaxHeapSiftDown(ElemType a[], int n, int pos);//向下调整二叉堆的第pos个元素，使其满足最大堆的特征
void MaxHeapSiftUp(ElemType a[], int n, int pos);//向上调整二叉堆的第pos个元素，使其满足最大堆的特征
void CreateMaxHeap_1(ElemType a[], int n);//构造最大堆（较优）
void CreateMaxHeap_2(ElemType a[], int n);//构造最大堆（较差）
void HeapSort(ElemType a[], int n);//堆排序，得到非递减序列
int FindKthMin(ElemType a[], int n, int k);//寻找第k大的数（当k=1时，即找最小值）
int FindKthMax(ElemType a[], int n, int k);//寻找第k大的数（当k=1时，即找最大值）
int main(void)
{
int i, k, n = MAXSIZE;
ElemType a[MAXSIZE] = {2,4,7,5,1,6,8,9,3,3};
puts("原数组:");
for (i=0; i<n; i++)
printf("%d ", a[i]);
printf("\n");
CreateMaxHeap_2(a, n); //先构造一个最大堆
puts("最大堆:");
for (i=0; i<n; i++)
printf("%d ", a[i]);
printf("\n");
HeapSort(a, n);//堆排序，得到非递减序列
puts("堆排序:");
for (i=0; i<n; i++)
printf("%d ", a[i]);
printf("\n");
k = 4;
printf("第%d大的数为%d\n", k, FindKthMin(a, n, k));//寻找第k大的数（当k=1时，即找最小值）
k = 4;
printf("第%d大的数为%d\n", k, FindKthMax(a, n, k));//寻找第k大的数（当k=1时，即找最大值）
return 0;
}
/*
函数功能：向下调整二叉堆的第pos个元素，使其满足最大堆的特征
初始条件：二叉堆a[]已经存在
操作结果：定位第pos个元素的孩子结点中较大的一个，当孩子结点比双亲结点大时，通过向上移动孩子结点值的方式，确保双亲结点大于孩子结点，以满足最大堆的特征。
采用类似插入排序的方法，向上移动数据，腾出插入位置，将原堆中第pos个元素向下调整到适当的位置。
注意：因C语言的数组下标从0开始，故第pos个元素在数组中表示为a[pos-1]。
若要删除二叉堆的第一个元素，则将最后一个元素放到根部，然后对根结点做向下调整操作，得到新的最大堆。
*/
void MaxHeapSiftDown(ElemType a[], int n, int pos)
{
ElemType temp = a[pos-1];
int child = pos * 2; //指向左孩子
while (child <= n)
{
if (child < n && a[child-1] < a[child]) //有右孩子，且右孩子更大些，定位其右孩子
child += 1;
if (a[child-1] > temp) //通过向上移动孩子结点值的方式，确保双亲大于孩子
{
a[pos-1] = a[child-1];
pos = child;
child = pos * 2;
}
else
break;
}
a[pos-1] = temp; //将temp向下调整到适当位置
}
/*
函数功能：向上调整二叉堆的第pos个元素，使其满足最大堆的特征
初始条件：二叉堆a[]已经存在
操作结果：定位第pos个元素的双亲结点，当孩子结点比双亲结点大时，通过向下移动双亲结点值的方式，确保双亲结点大于孩子结点，以满足最大堆的特征。
采用类似插入排序的方法，向下移动数据，腾出插入位置，将原堆中第pos个元素向上调整到适当的位置。
注意：因C语言的数组下标从0开始，故第pos个元素在数组中表示为a[pos-1]。
若要插入新元素，则将新元素插入到堆的最末位置，然后对新元素做向上调整操作，得到新的最大堆。
*/
void MaxHeapSiftUp(ElemType a[], int n, int pos)
{
ElemType temp = a[pos-1];
int parents = pos / 2; //指向双亲结点
if (pos > n) //不满足条件的元素下标
return;
while (parents > 0)
{
if (a[parents-1] < temp) //通过向下移动双亲结点值的方式，确保双亲大于孩子
{
a[pos-1] = a[parents-1];
pos = parents;
parents = pos / 2;
}
else
break;
}
a[pos-1] = temp; //将temp向上调整到适当位置
}
/*
函数功能：构造最大堆（较好）
初始条件：数组a[]已经存在
操作结果：通过逆序向下调整非叶子结点，将一个普通数组改造成最大堆。
*/
void CreateMaxHeap_1(ElemType a[], int n)
{
int i;
for (i=n/2; i>0; i--)
{
MaxHeapSiftDown(a, n, i);
}
}
/*
函数功能：构造最大堆（较差）
初始条件：数组a[]已经存在
操作结果：通过不断插入新元素，对新元素做向上调整操作，得到新的最大堆。
*/
void CreateMaxHeap_2(ElemType a[], int n)
{
int i;
for (i=1; i<=n; i++)
{
MaxHeapSiftUp(a, n, i);
}
}
/*
函数功能：堆排序，得到非递减序列
初始条件：数组a[]已经存在
操作结果：先构造一个最大堆，然后依次把根元素交换到适当的位置，重新调整得到新的最大堆。
逐次减小堆的长度，直到长度为1。
*/
void HeapSort(ElemType a[], int n)
{
int i;
ElemType temp;
CreateMaxHeap_1(a, n); //先构造一个最大堆
for (i=n-1; i>0; i--) //删除二叉堆的第一个元素，将其与第i个元素交换，然后向下调整得到新的最大堆。
{
temp = a[0];
a[0] = a[i];
a[i] = temp;
MaxHeapSiftDown(a, i, 1); //对根结点做向下调整操作，得到长度为i的新最大堆
}
}
/*
函数功能：寻找第k大的数（当k=1时，即找最小值）
初始条件：数组a[]已经存在
操作结果：先构造一个最大堆，然后遍历数组元素[k..n-1]，若元素不小于a[0]，不做任何操作；
否则替换a[0]，确保a[0]是第k大的数，再对根结点做向下调整操作，维持最大堆的特性
*/
int FindKthMin(ElemType a[], int n, int k)
{
int i;
CreateMaxHeap_2(a, k); //先构造一个长度为k的最大堆
for (i=k; i<n; i++)
{
if (a[i] < a[0]) //确保a[0]是第k大的数
{
a[0] = a[i];
MaxHeapSiftDown(a, k, 1); //对根结点做向下调整操作
}
}
return a[0];
}
/*
函数功能：寻找第k大的数（当k=1时，即找最大值）
初始条件：数组a[]已经存在
操作结果：利用堆排序的方法，先构造一个最大堆，然后依次把根元素交换到适当的位置，重新调整得到新的最大堆。
做k趟排序，就可以找到第k大的数。
*/
int FindKthMax(ElemType a[], int n, int k)
{
int i;
ElemType temp;
CreateMaxHeap_1(a, n); //先构造一个长度为n的最大堆
for (i=n-1; i>n-k; i--) //做k趟排序，找到第k大的数
{
temp = a[0]; //将第一个元素和第i个元素交换
a[0] = a[i];
a[i] = temp;
MaxHeapSiftDown(a, i, 1); //对根结点做向下调整操作，得到长度为i的新最大堆
}
return a[0];
}
