《大话数据结构》读书笔记之二叉堆基本操作(最大堆)
/*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];
}