数据结构|【数据结构初阶】(堆的接口实现和堆排序)

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

  • 堆的实现
    • 一、堆的概念及结构
    • 二、堆的实现思路
    • 三、堆的各种接口:
      • 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.建堆的时间复杂度证明 数据结构|【数据结构初阶】(堆的接口实现和堆排序)
文章图片

    推荐阅读