【数据结构|【数据结构初阶】(堆的接口实现和堆排序)】
文章目录
- 堆的实现
-
- 一、堆的概念及结构
- 二、堆的实现思路
- 三、堆的各种接口:
-
- 1.堆的初始化和销毁
- 2.堆的插入
- 3.堆的删除
- 4.打印堆的数据和获取堆顶的元素
- 5.获取堆的元素个数和判空
- 堆排序
-
- 1.向上调整建堆
- 2.向下调整建堆
- 3.建堆后的堆排序
- 4.建堆的时间复杂度证明
堆的实现 一、堆的概念及结构 堆(heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。
堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆。
( k i k_{i} ki? <=k 2 i + 1 k_{2i+1} k2i+1? 且k i k_{i} ki? <=k 2 i + 2 k_{2i+2} k2i+2?)或者( k i k_{i} ki? >=k 2 i + 1 k_{2i+1} k2i+1? 且k i k_{i} ki? >=k 2 i + 2 k_{2i+2} k2i+2?)
若将和此次序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值。由此,若序列{k1,k2,…,kn}是堆,则堆顶元素(或完全二叉树的根)必为序列中n个元素的最小值(或最大值)。
并且将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
堆总是满足下列性质:
1.堆中某个结点的值总是不大于或不小于其父结点的值;
2.堆总是一棵完全二叉树。
文章图片
二、堆的实现思路
文章图片
堆的实现物理结构上还是用数组来存放数据,所以我们动态开辟内存来实现
创建堆类型如下:
typedef int HPDataType;
struct Heap
{
HPDataType* a;
int size;
int capacity;
};
typedef struct Heap Heap;
这样我们就可以在主函数main()中创建一个堆结构体类型的变量,然后我们对数据进行处理,实现堆的各种接口函数,就是对这个变量进行操作即可。
三、堆的各种接口: 1.堆的初始化和销毁
//初始化堆
void HeapInit(Heap* hp)
{
assert(hp);
hp->a = NULL;
hp->capacity = 0;
hp->size = 0;
}//销毁堆,释放内存
void HeapDestroy(Heap* hp)
{
assert(hp);
free(hp->a);
hp->capacity = 0;
hp->size = 0;
}
2.堆的插入
//交换函数
void Swap(HPDataType* x, HPDataType* y)
{
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}void AdjustUp(HPDataType* a, int pos)
{
int child = pos;
int parent = (child - 1) / 2;
while (child > 0)
{
//建大堆就用大于号,小堆就用小于号,这样好区别是大堆还是小堆
//当孩子大于父亲就交换
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}//插入函数
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
//先在数组里加一个数据
if (hp->size == hp->capacity)
{
hp->capacity = hp->capacity > 0 ? hp->capacity * 2 : 2;
HPDataType* tmp =
(HPDataType*)realloc(hp->a, sizeof(HPDataType) * hp->capacity);
if (tmp == NULL)
{
perror("erron ");
exit(-1);
}
hp->a = tmp;
}
hp->a[hp->size] = x;
hp->size++;
//向上调整算法
AdjustUp(hp->a, hp->size - 1);
}
3.堆的删除
注意: 堆的输出并不是简单的把数据往前面挪动,而是数组的第一个元素和最后一个元素进行交换,然后数组的大小自减1,然后再调整堆,这样时间复杂度为树的高度次。
如果只是简单的把数据往前面挪动,这样会破坏堆的整个结构,就要重新进行建堆,这样时间复杂度会大大增加,不合适。
代码实现如下:
void AdjustDowm(HPDataType* a, int sz,int parent)
{
//不管建大堆还是小堆,都要先找出两个孩子的最大或者最小值
//默认孩子是左孩子
int child = (parent * 2) + 1;
while (child < sz)
{
//建大堆,如果右孩子大于左孩子1,就child++就把左孩子变成右孩子了
if (child + 1 < sz && a[child + 1] > a[child])
{
child++;
}
//如果孩子大于父亲就交换
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = (parent * 2) + 1;
}
else
{
break;
}
}
}void HeapPop(Heap* hp)
{
assert(hp);
assert(hp->size > 0);
//先把第一个元素和最后一个元素进行交换
Swap(&hp->a[0], &hp->a[hp->size - 1]);
hp->size--;
//调整堆,时间复杂度为 树的高度次
AdjustDowm(hp->a, hp->size, 0);
}
4.打印堆的数据和获取堆顶的元素
//打印堆的数据
void HeapPrint(Heap* hp)
{
int i = 0;
for (i = 0;
i < hp->size;
i++)
{
printf("%d ", hp->a[i]);
}
printf("\n");
}//获取堆顶的元素
HPDataType HeapTop(Heap* hp)
{
assert(hp);
assert(hp->size > 0);
return hp->a[hp->size - 1];
}
5.获取堆的元素个数和判空
//获取堆的元素个数
int HeapSize(Heap* hp)
{
assert(hp);
return hp->size;
}//判断堆是否为空
bool HeapEmpty(Heap* hp)
{
assert(hp);
return hp->size == 0;
}
堆排序 堆排序要求的是要在原本数组的基础上排序,而不是像我们上面那样动态内存开辟实现并且还要浪费额外的空间。
那怎么样在原来的数组上建堆并且排序呢?
我们有两种建堆的方法,分别如下:
1.向上调整建堆 这种方法就像我们上面写堆的插入那样,先把数组的第一个元素看成堆,然后把后面的元素看成不断往数组里面插入建堆。
文章图片
代码实现如下:
#define _CRT_SECURE_NO_WARNINGS 1
#include
//打印函数
void Print(int* a,int n)
{
int i = 0;
for (i = 0;
i < n;
i++)
{
printf("%d ", a[i]);
}
printf("\n");
}//交换函数
void Swap(int* px, int* py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}//自下而上方式插入建堆
void AdjustUp(int* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
//孩子大于父亲就交换,建的是大堆
//孩子小于父亲就交换,建的是小堆,下面建的是小堆
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}//堆排序
void HeapSort(int* a,int n)
{
int i = 0;
//建堆有两种方式
//1.自下而上方式插入建堆
//2.自上而下方式分治思想建堆,从最小的堆开始调整
//方式1建堆
for (i = 1;
i < n;
i++)
{
AdjustUp(a, i);
}
printf("建堆的结果为:\n");
Print(a, n);
}int main()
{ int arr[] = { 4,8,2,7,1,9,3,6,5 };
int sz = sizeof(arr) / sizeof(arr[0]);
HeapSort(arr, sz);
return 0;
}
文章图片
2.向下调整建堆 这种建堆的思想和求斐波那契数类似,求第n给斐波那契数可以用迭代法,从第一项开始迭代到第n个即可;而建堆也类似,从数组中最后一个堆的父亲开始调整,调整到父亲为第一个元素,堆就建成功了。
文章图片
代码实现如下:
#define _CRT_SECURE_NO_WARNINGS 1
#include void Print(int* a,int n)
{
int i = 0;
for (i = 0;
i < n;
i++)
{
printf("%d ", a[i]);
}
printf("\n");
}void Swap(int* px, int* py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}//向下调整建堆
void AdjustDowm(int* a, int n, int parent)
{
//默认孩子是左孩子
int child = (parent * 2) + 1;
while (child < n)
{
//先找出两个孩子最大的那个或者最小的那个
//这里建的是小堆,找出小的那个
if (child + 1 < n && a[child + 1] < a[child])
{
child++;
}
//如果孩子小于父亲就交换
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}//堆排序
void HeapSort(int* a,int n)
{
int i = 0;
//建堆有两种方式
//1.自下而上方式插入建堆
//2.自上而下方式分治思想建堆,从最小的堆开始调整 //方式2建堆
for (i = (n - 1 - 1) / 2;
i >= 0;
i--)
{
AdjustDowm(a, n, i);
}
printf("建堆的结果为:\n")
Print(a, n);
}int main()
{ int arr[] = { 4,8,2,7,1,9,3,6,5 };
int sz = sizeof(arr) / sizeof(arr[0]);
HeapSort(arr, sz);
return 0;
}
文章图片
3.建堆后的堆排序 堆排序是要建堆和排序,我们已经建好堆了那么怎么进行排序呢?
如果排升序,要建大堆还是小堆呢?
确实,堆可以建成大堆和小堆;但是如果排升序我们建的是大堆,排降序建的是小堆
理由如下:
文章图片
代码如下:
#define _CRT_SECURE_NO_WARNINGS 1
#include void Print(int* a,int n)
{
int i = 0;
for (i = 0;
i < n;
i++)
{
printf("%d ", a[i]);
}
printf("\n");
}void Swap(int* px, int* py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}//向下调整建堆
void AdjustDowm(int* a, int n, int parent)
{
//默认孩子是左孩子
int child = (parent * 2) + 1;
while (child < n)
{
//先找出两个孩子最大的那个或者最小的那个
//这里建的是小堆,找出小的那个
if (child + 1 < n && a[child + 1] < a[child])
{
child++;
}
//如果孩子小于父亲就交换
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}//堆排序
void HeapSort(int* a,int n)
{
int i = 0;
//建堆有两种方式
//1.自下而上方式插入建堆
//2.自上而下方式分治思想建堆,从最小的堆开始调整 //方式2建堆
for (i = (n - 1 - 1) / 2;
i >= 0;
i--)
{
AdjustDowm(a, n, i);
}
printf("建堆的结果为:\n")
Print(a, n);
//堆排序,自上而下
int end = 0;
for (end = n - 1;
end > 0;
end--)
{
//最大或者最小的数交换到后面去
Swap(&a[0], &a[end]);
AdjustDowm(a, end, 0);
}
printf("堆排序的结果为:\n");
Print(a, n);
}int main()
{
int arr[] = { 4,8,2,7,1,9,3,6,5 };
int sz = sizeof(arr) / sizeof(arr[0]);
HeapSort(arr, sz);
return 0;
}
文章图片
4.建堆的时间复杂度证明
文章图片
推荐阅读
- 数据结构|【初阶数据结构】完全二叉树实现堆排序
- c语言|《校招大厂中等难度笔试题》纯C语言求解迷宫问题——进来测测你数据结构初阶学的怎么样()
- 初阶数据结构与算法|【初阶数据结构与算法】第七篇(二叉树和堆的基本概念+以及堆的实现)
- 数据结构|二叉树初阶1、
- 蓝桥杯|2018年第九届C/C++ A组蓝桥杯省赛真题部分题解(C语言/C++)
- 蓝桥杯题解|蓝桥杯“字串排序“题解
- #|<<算法很美>>——(七)——DFS典题(二):数独游戏
- 数据结构|几种常见的排序方法整理
- 数据结构|Java实现常见的排序算法