189 8069 5689
先说什么是堆呢，堆是一种完全二叉树，它分为大堆和小堆，堆的表示最好用数组表示，因为它是完全二叉树，不存在分支为空
做堆之前，要熟练掌握两个公式 parent=（child-1）/2；
child=parent*2+1;
这里我们拿升序的代码举例，记住，升序就要大堆，降序就要小堆，具体为何看代码注释
这里建议先看代码，代码看不懂再看图解
AdjustUp的图解---这个图解的过程得配合HeapPush这个函数看，插入一个，就调整一次，这里的child永远是数组最后一个元素
以此类推，只要记住child永远是数组最后一个，然后插入一次调整一次就行了
AdjustDown图解--建议这个函数的图解配合Heapsort函数的第一个循环看更好，我写的可能跟那个函数的意思不一样，不过都大同小异，理解了我的图解，再想一下就好了
以此类推
Heapsort图解
#include#include#include
typedef int HPDataType;
//先创建一个堆的结构体
typedef struct Heap
{
HPDataType* a;
int size;//元素的个数
int capacity;//这块空间的大承受元素的限度，说到这里有的小伙伴可能还是不懂，那么我就来举个例子吧
//比如你创建了一块空间，可以容下10个元素，这时候有一个数组里面有5个元素，那么相对于这个结构体来说，size就是5，capacity就是10
}HP;
//对堆进行初始化，这个大家应该都能理解，我也不解释了
void HeapInit(HP* hp)
{
assert(hp);
hp->a = NULL;
hp->size = 0;
hp->capacity = 0;
}
//交换函数，下面会用到多次交换，所以我就写了一个交换函数，交换函数大家应该都能理解，我也不多解释了
void Swap(HPDataType* x, HPDataType* y)
{
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
//这个函数是向上调整
void AdjustUp(int* a, int child)
{
//child就是最后一个元素的下标，然后用公式把他的parent求出来
int parent = (child - 1) / 2;
while (child >0)
//这里有人会问了，为什么不能是parent>=0,而是child>0呢
//你想，由大括号里面的这两个公式
// child = parent;
//parent = (child - 1) / 2;
//到最后，parent=0的时候，把parent赋值给child，然后这时候child就是0了
//然后parent = (child - 1) / 2的时候，child是0，（0-1）/2还是0；
//所以只要控制child>0就好了
{
if (a[child] >a[parent])//记住，大堆这里就改成>，小堆就是<，a[child]和a[parent]的顺序最好不要变（可以变），容易给自己搞懵！！
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//这个函数是往数组堆的结构体里面的那个HPDataType* a里面一个一个放进去main()函数里的数组arr中的元素
void HeapPush(HP* hp, int x)
{
if (hp->size == hp->capacity)//如果这个时候size跟capacity（这块空间的元素的个数跟这块空间所能承受的元素的大限度相等了）
{
//就需要扩容了，如果空间所能承受的元素的大限度是0，那么就扩容四个空间
//如果空间所能承受的元素的大限度不是0，那么就在原来空间所能承受大限度的基础上再扩容一倍
int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
//下面这个语句的意思就是增容
//为什么tmp的类型是 HPDataType*呢？？我们接着往下看，realloc的意思就是把一个空间，在它原有的基础上
//增容到realloc的括号里面的逗号后面那个对象的大小，这里也就是sizeof(HPDataType) * newcapacity
//增容到sizeof(HPDataType) * newcapacity这么大
//回到刚才那个问题，这里结构体的int* a你可以认为是一个数组
//[(HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity)]的意思要把数组里面的元素增容到这么大，然后将这个赋值给tmp,
// 这时候tmp就可以认为成一个数组了，这个数组里面的元素的大容量比a数组里面的大
//并且tmp在下一步要赋值给a
//有的人想问了，为什么不直接写(hp->a,newcapacity)呢，我自己的理解是，我们创建的堆的结构体里面
//a数组里面的数据类型都是HPDataType，这里我把int给typedef成HPDataType，也就是说HPDataType也占四个字节
//你的一个数组里面就算是有int类型的元素，但是他们每个元素都是4个字节，比如你有一个10个元素的数组，它里面是40个字节，同样
//你增容后的数组也要按照字节来算，计算机里面是按照字节的，不是按照元素个数的
HPDataType* tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
if (tmp == NULL)//判断一下tmp是否增容成功了
{
printf("realloc failed\n");
exit (-1);
}
hp->a = tmp;//相当于把tmp数组的容量大小赋值给a数组了
hp->capacity = newcapacity;//然后把newcapacity的值赋给capacity
}
hp->a[hp->size] = x;//hp->size就是数组最后一个元素的后面紧挨着的那个空间
hp->size++;//插入了之后，元素的个数+1
//下面这个向上调整可以加上可以不加上
// hp->a就是把a这个数组传过去，hp->size-1就是最后一个元素的下标
//AdjustUp(hp->a,hp->size-1);
}
//打印函数，把元素一个个打印出来，验证你的代码是否正确
void Print(HP* hp, int sz)
{
for (int i = 0; i< sz; i++)
{
printf("%d ", hp->a[i]);
}
printf("\n");
}//这个是向下调整
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
//这里child没分左右孩子，默认为左孩子
while (child< n)
{
//child+1肯定是右孩子
if (child + 1< n && a[child + 1] >a[child])//还是一样，大堆就是a[child + 1] >a[child]，小堆就是<，顺序最好别变，否则易懵
{
child++;
}
if (a[child] >a[parent])//大堆就是a[child] >a[parent]，小堆就是<
{
Swap(&a[child], &a[parent]);
parent = child;//相应的顺序大家看AdjustUp,思想都差不多
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void Heapsort(HP* hp, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
//(n - 1 - 1)的意思就是，最后一个孩子的父亲，n-1是最后一个孩子，把它看成N
//然后（N）-1/2不就是我说的公式嘛
//这个时候arr数组中的元素都已经相应的插入到a里面去了，但是还是乱序，不知道它是大堆还是小堆，这里我们要把它调成大堆，因为是升序
//i= (n - 1 - 1) / 2意味着我们只需要从倒数第一个非叶子结点调整，如果我们从叶子结点调整的话，叶子结点也没有孩子呀，码农们想一下
//这时候i--的意思就是调整完倒数第一个非叶子结点之后，就开始调整倒数第二个非叶子结点
{
//hp->a表示传数组，n表示传元素的个数，i表示开始调整大堆的位置
AdjustDown(hp->a, n, i);
}
//上一行代码---也就是}这个大括号的右半部分结束之后，我们的大堆就调好了
//下一行代码就是要开始排序了
for (int end = n - 1; end >0; end--)
{
//你想，hp->a[0]肯定是这个堆里面的大的一个，然后把这个大的一个跟堆里面最后一个进行交换
Swap(&hp->a[0], &hp->a[end]);
//换完了之后，最后一个换到了第一个，这个时候乱序了，肯定不是大堆了，这个时候就开始把第一个向下调整
//hp->a表示传数组，end表示传元素的个数，0表示开始调整大堆的位置
AdjustDown(hp->a, end, 0);
//调整完了之后又是一个大堆了，这个时候数组最后一个元素大，所以end--，这个时候相当于不要数组最后一个元素了，大的已经找到了
//然后，这个不要最后一个元素之后，第一个元素就是大的了，然后再进行循环
//为什么end不是>=0呢，你想，假如有5个数字，大的4个数字都找出来了，最后一个肯定是最小的呀
}
}
int main()
{
HP hp;
HeapInit(&hp);
int arr[] = { 50,20,90,100,1,65,88 };
int sz = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i< sz; i++)//把这个数组里面的元素一个个插入到HPDataType* a里面去
{
HeapPush(&hp,arr[i]);
}
Print(&hp, sz);
Heapsort(&hp, sz);
Print(&hp, sz);
return 0;
}
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧