赞
踩
目录
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点总是小于或者大于它的父节点
想要用堆,先要实现堆的功能函数
初始化、释放、打印、入堆、出堆、返回堆顶元素、返回堆中有多少元素、判空、向上调整法、向下调整法
- //初始化
- void HeapInit(HP* hp);
-
- //释放
- void HeapDestory(HP* hp);
-
- //打印
- void HeapPrint(HP* hp);
-
- //入堆
- void HeapPush(HP* hp, HeaDataType x);
-
- //出堆 从堆顶出
- void HeapPop(HP* hp);
-
- //返回堆顶元素
- HeaDataType HeapTop(HP* hp);
-
- //返回堆中多少元素
- size_t HeapSize(HP* hp);
-
- //判空
- bool HeapEmpty(HP* hp);
实现堆排序所需要头文件
- #include<stdio.h>
- #include<stdlib.h>
- #include<assert.h>
- #include<stdbool.h>
堆它的结构是树形结构(逻辑结构上)但是它的物理结构是用顺序表来实现,所以我们构建的结构体跟顺序表是一样的,然后我们再对类型进行重命名
- typedef int HeaDataType;
-
- typedef struct Heap
- {
- HeaDataType* a;
- int size;
- int capacity;
- }HP;
1.初始化
因为它物理结构上是顺序表。那么初始化,只需要对指针置空,并对size和capacity置0。
- //初始化
- void HeapInit(HP* hp)
- {
- assert(hp);
- hp->a = NULL;
- hp->size = hp->capacity = 0;
- }
2.释放(这些必备的函数,先实现,到后面我们就可以直接调用)
把a的数据释放,并把指针置空,再把size和capacity置为0
- //释放
- void HeapDestory(HP* hp)
- {
- free(hp->a);
- hp->a = NULL;
- hp->size = hp->capacity = 0;
- }
3.打印
直接对数组里的数据依次打印
- //打印
- void HeapPrint(HP* hp)
- {
- for (size_t i=0; i < hp->size; i++)
- {
- printf("%d ", hp->a[i]);
- }
- }
4.入堆
要入堆,需要判断空间是否满,然后再看是否要进行扩容操作,(这不是重点,因为扩容操作太简单,这里主要讲解向上调整法)
因为堆的要求是子节点是必须大于或小于父节点的,那么要插入节点的值是不能确定的,并且无法保证它一定是有序的,所以我们要对插入的子节点进行操作,如果插入的数是小于父节点的,那么我们就要让它向上移动,并且不让它破坏结构,就要用到向上调整法
向上调整法思路
1.我们先用下标找到插入节点的父节点
传值我们用下标去找,找到它的父节点的下标位置。
2.让孩子节点和父亲节点的值交换
这里要交换他们的值,那么用他们的类型指针,去指向他们的值,然后进行值交换,如果用HP->a[child/parent]那么交换的只是他们的下标
这里再加上一个Swap交换函数
3.然后让父亲节点变为孩子节点
4.再利用孩子节点去找到它的父亲节点
稍微的小总结(交换后,让孩子节点变成它的父亲节点,再利用这个父亲节点去找它的父亲(套娃)
情况不全是这样,这次是0 它是最小的,所以是到堆顶,如果它比其中一个数小,就成为它的子节点
- void Swap(HeaDataType* hp, HeaDataType* hb)
- {
- HeaDataType* tmp = *hp;
- *hp = *hb;
- *hb = tmp;
- }
-
-
- void ADjustUP(HeaDataType* a, size_t child/*孩子节点下标*/)
- {
- size_t prent = (child - 1) / 2;//父亲节点下标
- while (child > 0)
- {
- if (a[child/*孩子节点的值*/] < a[prent/*父亲节点的值*/])
- //这里用的是HeaDataType* a 它是指针 找的是child的值 而不是下标
- {
- Swap(&a[child], &a[prent]);
- child = prent;
- prent = (child - 1) / 2;
- }
- else
- {
- break;
- }
- }
- }
-
- //入堆
- void HeapPush(HP* hp, HeaDataType x)
- {
- if (hp->size == hp->capacity)
- {
- size_t newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
- HeaDataType* tmp = (HeaDataType*)realloc(hp->a, sizeof(HeaDataType)*newcapacity);
- if (tmp == NULL)
- {
- printf("realloc fail\n");
- exit(-1);
- }
- hp->a = tmp;
- hp->capacity = newcapacity;
- }
- hp->a[hp->size] = x;
- hp->size++;
-
- //向上调整法
- ADjustUP(hp->a, hp->size - 1);
- }
5.出堆
出堆则是把堆顶的数据给去除,并且堆的结构不能被破坏
出堆是直接用到向下调整法。
向下调整法的思路:
1.让堆顶的数据和最后一个节点的数据交换
最后一个数就是size-1。
2.再删除最后一个节点
删除最后一个数让size直接--(有效数据--)
3.再把堆顶往下调整
让堆顶的下标去找子节点,(分为左孩子、右孩子)
先判断左孩子小还是右孩子小,再向下调整(这里有一个极端情况,它可能没有右孩子,又因为左孩子下标+1就是右孩子,我们判断左孩子+1是否到了size的有效数据)
再接下来,判断孩子节点是否比父亲节点小,是否要进行交换操作
6.返回堆顶元素、返回堆中有多少元素、判空
这三个功能实现简单,所以合起来讲
返回堆顶元素直接返回数组的下标为0的元素
返回堆中有多少元素 返回size就可以 size记录的就是有效数据
判空 返回size是否为0
- //返回堆顶元素
- HeaDataType HeapTop(HP* hp)
- {
- assert(hp);
- assert(hp->size > 0);
-
- return hp->a[0];
- }
-
- //返回堆中多少元素
- size_t HeapSize(HP* hp)
- {
- assert(hp);
-
- return hp->size;
- }
-
- //判空
- bool HeapEmpty(HP* hp)
- {
- assert(hp);
-
- return hp->size == 0;
- }
左孩子=父节点*2+1 leftchild=parent*2+1
右孩子=父节点*2+2 rightchild=parent*2+2
父节点=(孩子节点-1)/2 parent=(child-1)/2
功能实现后,就可以实现一个堆排序了
例:假设我要排序 12,64,7,9,35,67,53,100
先计算好数组元素的大小,再让他们分别压入堆里,再让他们依次从小到打压出数组,最后打印
如:
- void HeapSort(int* a, int size)
- {
- HP hp;
- HeapInit(&hp);
- int i, j=0;
- for (i = 0; i < size; i++)
- {
- HeapPush(&hp, a[i]);
- }
-
- while (!HeapEmpty(&hp))
- {
- a[j++]= HeapTop(&hp);
- HeapPop(&hp);
- }
- HeapDestory(&hp);
- }
-
- int main()
- {
- //test();
- int i;
- int a[] = { 12,64,7,9,35,67,53,100 };
- HeapSort(a, sizeof(a) / sizeof(int));
- printf("堆排序后:");
- for (i = 0; i < sizeof(a) / sizeof(int); i++)
- {
- printf("%d ", a[i]);
- }
-
- return 0;
- }
1.这里我们先建一个大堆先找到最后一个父节点(利用公式)
2.找到堆的最后一个节点即数组里最后一个数字
3.这时大堆的堆顶一定为堆中最大的数,那么我们把最大的数与最后一个数交换(即最大的数移动到了最后),然后我们在继续建大堆(最后一个数不参与建队)建好后,让end指向倒数第二的位置 口诉比较乱,这里再次用图讲解
- //初始化
- void HeapInit(HP* hp)
- {
- assert(hp);
- hp->a = NULL;
- hp->size = hp->capacity = 0;
- }
-
- //释放
- void HeapDestory(HP* hp)
- {
- free(hp->a);
- hp->a = NULL;
- hp->size = hp->capacity = 0;
- }
-
- //打印
- void HeapPrint(HP* hp)
- {
- for (size_t i=0; i < hp->size; i++)
- {
- printf("%d ", hp->a[i]);
- }
- }
-
- void Swap(HeaDataType* hp, HeaDataType* hb)
- {
- HeaDataType* tmp = *hp;
- *hp = *hb;
- *hb = tmp;
- }
-
-
- void ADjustUP(HeaDataType* a, size_t child/*孩子节点下标*/)
- {
- size_t prent = (child - 1) / 2;//父亲节点下标
- while (child > 0)
- {
- if (a[child/*孩子节点的值*/] < a[prent/*父亲节点的值*/])
- //这里用的是HeaDataType* a 它是指针 找的是child的值 而不是下标
- {
- Swap(&a[child], &a[prent]);
- child = prent;
- prent = (child - 1) / 2;
- }
- else
- {
- break;
- }
- }
- }
-
- //入堆
- void HeapPush(HP* hp, HeaDataType x)
- {
- if (hp->size == hp->capacity)
- {
- size_t newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
- HeaDataType* tmp = (HeaDataType*)realloc(hp->a, sizeof(HeaDataType)*newcapacity);
- if (tmp == NULL)
- {
- printf("realloc fail\n");
- exit(-1);
- }
- hp->a = tmp;
- hp->capacity = newcapacity;
- }
- hp->a[hp->size] = x;
- hp->size++;
-
- //向上调整法
- ADjustUP(hp->a, hp->size - 1);
- }
-
- void ADjustDown(HeaDataType* a, size_t size, size_t root)
- {
- size_t prent = root;
- size_t child = prent * 2 + 1;
- while (child < size)
- {
- if (child + 1 < size/*判断树是否只有左孩子*/&& a[child + 1] < a[child])
- {
- ++child;
- }
-
- if (a[child] < a[prent])
- {
- Swap(&a[child], &a[prent]);
- prent = child;
- child=prent * 2 + 1;
- }
- else
- {
- break;
- }
- }
- }
-
- //出堆
- void HeapPop(HP* hp)
- {
- //交换第一个数和最后一个数 去掉最后一个数
- //然后向下调整法
-
- assert(hp);
- assert(hp->size > 0);
-
- Swap(&hp->a[0], &hp->a[hp->size - 1]);
- --hp->size;
-
- ADjustDown(hp->a, hp->size, 0);
- }
-
- //返回堆顶元素
- HeaDataType HeapTop(HP* hp)
- {
- assert(hp);
- assert(hp->size > 0);
-
- return hp->a[0];
- }
-
- //返回堆中多少元素
- size_t HeapSize(HP* hp)
- {
- assert(hp);
-
- return hp->size;
- }
-
- //判空
- bool HeapEmpty(HP* hp)
- {
- assert(hp);
-
- return hp->size == 0;
- }
- void HeapSort(int* a, int size)
- {
- for (int i =(size-1-1)/2; i>=0; i--)//先找到最后一个父节点 然后建大堆
- {
- ADjustDown(a, size, i);//先建大堆
- }
- int end = size - 1;//这时堆是大堆 然后找最后一个节点
- while (end >0)
- {
- Swap(&a[0], &a[end]);//让第一个和最后一个节点交换 (最大的节点被换到最后)
- ADjustDown(a, end, 0);//让最后一个节点的前面全部节点建队 让最大的节点换到堆顶
- --end; //然后让第一个节点与倒数第二个节点交换 (次大的节点被换到的倒数第二个)
- }
- }
如果本篇对您有帮助,希望能获得您的赞!感谢!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。