数据结构|【数据结构初阶】（堆的接口实现和堆排序）算法|c语言|数据结构

【数据结构|【数据结构初阶】（堆的接口实现和堆排序）】
文章目录

堆的实现
- 一、堆的概念及结构
- 二、堆的实现思路
- 三、堆的各种接口：
- - 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; }