【数据结构】二叉树 —— 堆的实现(顺序存储)
文章目录
- 前言
- 1. 二叉树的存储结构
-
-
- 1.1 顺序存储
- 2.2 链式存储
-
- 2. 二叉树的顺序结构及实现
-
-
- 2.1 二叉树的顺序结构
- 2.2 堆的概念及结构
-
- 3. 堆的实现:(Heap)
-
-
- 3.1 头文件(Heap.h)
- 3.2 具体函数的实现:(Heap.c)
-
- * 向上调整算法:(AdjustUp)
- * 向下调整算法:(AdjustDown)
-
- 4. 空间复杂度为〇(N)的堆排序
前言
我们知道二叉树逻辑上的存储是树状结构,那么二叉树这个数据结构在计算机中是怎样存储的呢?
本篇将带来二叉树的一种存储方式 —— 顺序存储。
1. 二叉树的存储结构
二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。
1.1 顺序存储
顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储,二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。
2.2 链式存储
二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链,后面课程学到高阶数据结构如红黑树等会用到三叉链。
2. 二叉树的顺序结构及实现
2.1 二叉树的顺序结构
普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事:
- 一个是数据结构
- 一个是操作系统中管理内存的一块区域分段
2.2 堆的概念及结构
如果有一个关键码的集合K = { , , ,…, },把它的所有元素按完全二叉树的顺序存储方式存储
在一个一维数组中,并满足: <= 且 = 且 >= ) i = 0,1,2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
堆的性质:
- 堆中某个节点的值总是不大于或不小于其父节点的值;
- 堆总是一棵完全二叉树
根据上图的结构我们很发现父亲结点和孩子结点之间的关系,通过父亲算出左右两个孩子:
- leftchild = parent * 2 + 1
- rightchild = parent * 2 + 2
因为整数除法算出来的结果会向下取整,所以通过孩子算出父亲可以总结为一个公式:
- parent = (child - 1)/ 2
3. 堆的实现:(Heap)
小堆的实现:
3.1 头文件(Heap.h)
#pragma once#include#include#include#includetypedef int HPDataType;typedef struct Heap{HPDataType* a;size_t size;size_t capacity;}HP;//堆的初始化void HeapInit(HP* php); //堆的销毁void HeapDestroy(HP* php);//堆插入数据 - 依旧保持是(大/小)堆void HeapPush(HP* php, HPDataType x);//向上调整算法void AdjustUp(HPDataType* a, size_t child);//交换void Swap(HPDataType* pa, HPDataType* pb);//堆删除堆顶的数据(最小/最大)void HeapPop(HP* php);//向下调整算法void AdjustDown(HPDataType* a, size_t size, size_t root);//堆的打印void HeapPrint(HP* php);//判断堆是否为空bool HeapEmpty(HP* php);//堆中数据的个数size_t HeapSize(HP* php);//堆顶数据HPDataType HeapTop(HP* php);
3.2 具体函数的实现:(Heap.c)
#include"Heap.h"//堆的初始化void HeapInit(HP* php){assert(php);php->a = NULL;php->size = php->capacity = 0;}//堆的销毁void HeapDestroy(HP* php){assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;}//交换void Swap(HPDataType* pa, HPDataType* pb){HPDataType tmp = *pa;*pa = *pb;*pb = tmp;}//堆的打印void HeapPrint(HP* php){assert(php);for (size_t i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");}//堆插入数据 - 依旧保持是(大/小)堆void HeapPush(HP* php, HPDataType x){assert(php);if (php->size == php->capacity){size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);if (tmp == NULL){printf("realloc failed\n");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;//向上调整,控制保持是一个小堆AdjustUp(php->a, php->size - 1);}//堆删除堆顶的数据(最小/最大)void HeapPop(HP* php){assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;//向下调整AdjustDown(php->a, php->size, 0);}//判断堆是否为空bool HeapEmpty(HP* php){assert(php);return php->size == 0;}//堆中数据的个数size_t HeapSize(HP* php){assert(php);return php->size;}//堆顶数据HPDataType HeapTop(HP* php){assert(php);assert(php->size > 0);return php->a[0];}
* 向上调整算法:(AdjustUp)
//向上调整算法void AdjustUp(HPDataType* a, size_t child){size_t 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;}}}
向上调整算法的目的是:
将后插入堆的数据进行调整,使得整个结构仍是一个堆的结构。
该算法有一个前提条件:
插入数据之前的结构必须是一个堆的结构,因为向上调整只会影响要调整结点的祖先并不会对兄弟结点和其他子树造成影响。
通过公式:
- parent = (child - 1)/ 2
时间复杂度:
假设一共有N个结点,假如是满二叉树设高度为h,则有N = 2^h - 1,h = log2(N + 1),如图所示要最坏情况要向上调整 h - 1 次,每次调整交换函数内部执行了3次代码
- 精确计算:时间复杂度:〇(3*(log2(N - 1)))
- 粗略取大头:时间复杂度:〇(log2N)
* 向下调整算法:(AdjustDown)
//向下调整算法void AdjustDown(HPDataType* a, size_t size, size_t root){size_t parent = root;size_t child = parent * 2 + 1;//左孩子while (child < size){//1.选出左右孩子中小的那一个if (child + 1 < size && a[child + 1] < a[child]){child++;} //2.如果孩子小于父亲,则交换,并继续往下调整if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}
向下调整算法的目的是:
将一个子树的根往下调整,使得整个结构仍是一个堆的结构。
该算法有一个前提条件:
根节点的左右子树是堆的前提下,因为向下调整只会影响要调整结点的子孙并不会对兄弟结点和其他子树造成影响。
时间复杂度:
假设一共有N个结点,假如是满二叉树设高度为h,则有N = 2^h - 1,h = log2(N + 1),如图所示要最坏情况要向下调整 h - 1 次,每次调整交换函数内部执行了3次代码
- 精确计算:时间复杂度:〇(3*(log2(N - 1)))
- 粗略取大头:时间复杂度:〇(log2N)
4. 空间复杂度为〇(N)的堆排序
//堆void HeapSort1(int* a, int size){HP hp;HeapInit(&hp);for (int i = 0; i < size; i++){HeapPush(&hp, a[i]);}size_t j = 0;while (!HeapEmpty(&hp)){a[j] = HeapTop(&hp);j++;HeapPop(&hp);}HeapDestroy(&hp);}int main(){int a[] = { 4,2,7,8,5,1,0,6 };HeapSort1(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); i++){printf("%d ", a[i]);}printf("\n");return 0;}
排序的时间复杂度:
每个数据入堆的时候都要一次向上调整,要入N次堆:
- log2(1)+ log2(2) + log2(3) + …… + log2(N) = log2(N!) <= log2(N^N) = N*log(N)
还有在出堆的时候将堆顶的数据给a数组,并删除堆顶数据再向下调整堆,这样重复操作N
次:
-
log2(1)+ log2(2) + log2(3) + …… + log2(N) = log2(N!) <= log2(N^N) = N*log(N)
-
精确计算:〇(2*log2(N!))
-
粗略取大头: 〇(N*log2N)
-
删除数据的时候是将堆顶的数和堆最后一个数据交换,从堆尾部将最(大/小)的数据删除,再从根节点向下调整。
-
每次的调整之后,(堆中)最(大/小)的数据将被排到堆顶。
运行结果:
时间复杂度是很优的,但是 空间复杂度是〇(N) 还需要继续优化!