博罗营销网站制作,网站怎么添加管理员,骏域网站建设,中国制造网平台【数据结构】二叉树的顺序结构-堆
普通的二叉树是不适合用数组来存储的#xff0c;因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储#xff0c;需要注意的是这里的堆和操作系统虚拟进程地址空间…【数据结构】二叉树的顺序结构-堆
普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。 1.堆的概念及结构
小堆将根结点最小的堆叫做小堆也叫最小堆或小根堆。
大堆将根结点最大的堆叫做大堆也叫最大堆或大根堆。
堆的性质
堆中某个结点的值总是不大于或不小于其父结点的值。堆总是一棵完全二叉树。 2.堆的实现
堆的向下调整算法
现在我们给出一个数组逻辑上看作一棵完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。 但是使用向下调整算法需要满足一个前提
若想将其调整为小堆那么根结点的左右子树必须都为小堆。若想将其调整为大堆那么根结点的左右子树必须都为大堆。 向下调整算法的基本思想以建小堆为例
从根结点处开始选出左右孩子中值较小的孩子。让小的孩子与其父亲进行比较。 若小的孩子比父亲还小则该孩子与其父亲的位置进行交换。并将原来小的孩子的位置当成父亲继续向下进行调整直到调整到叶子结点为止。若小的孩子比父亲大则不需处理了调整完成整个树已经是小堆了。
代码如下
//交换函数
void Swap(int* x, int* y){int tmp *x;*x *y;*y tmp;
}//堆的向下调整小堆
void AdjustDown(int *a, int n, int parent) {//child记录左右孩子中值较小的孩子的下标int child 2 * parent 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 2 * parent 1;} else{//已成堆break;}}
}使用堆的向下调整算法最坏的情况下即一直需要交换结点需要循环的次数为h - 1次h为树的高度。而h log2(N1)N为树的总结点数。所以堆的向下调整算法的时间复杂度为O(logN) 。
上面说到使用堆的向下调整算法需要满足其根结点的左右子树均为大堆或是小堆才行那么如何才能将一个任意树调整为堆 答案很简单我们只需要从倒数第一个非叶子结点开始从后往前按下标依次作为根去向下调整即可。 代码
for (int i (n - 1 - 1) / 2; i 0; i--) {AdjustDown(php-a, n, i);
}那么建堆的时间复杂度又是多少呢 当结点数无穷大时完全二叉树与其层数相同的满二叉树相比较来说它们相差的结点数可以忽略不计所以计算时间复杂度的时候我们可以将完全二叉树看作与其层数相同的满二叉树来进行计算。 总结一下
堆的向下调整算法的时间复杂度T(n) O (log N)建堆的时间复杂度T(n) O(N)
堆的向上调整算法
当我们在一个堆的末尾插入一个数据后需要对堆进行调整使其仍然是一个堆这时需要用到堆的向上调整算法。 向上调整算法的基本思想以建小堆为例
将目标结点与其父结点比较。若目标结点的值比其父结点的值小则交换目标结点与其父结点的位置并将原目标结点的父结点当作新的目标结点继续进行向上调整。若目标结点的值比其父结点的值大则停止向上调整此时该树已经是小堆了。 代码如下
//交换函数
void Swap(HPDataType *x, HPDataType *y) {HPDataType tmp *x;*x *y;*y tmp;
}//堆的向上调整小堆
void AdjustUp(HPDataType *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;}}
}初始化堆
首先必须创建一个堆类型该类型中需包含堆的基本信息存储数据的数组、堆中元素的个数以及当前堆的最大容量。
typedef int HPDataType;
// 堆的结构 - 顺序表
typedef struct Heap {HPDataType *a;int size;int capacity;
} Heap;建堆
然后我们需要一个建堆函数对刚创建的堆进行初始化注意在初始化期间要将传入数据建堆。
// 堆的创建 - 建堆算法
void HeapCreate(Heap *php, HPDataType *a, int n) {assert(php);php-a (HPDataType *) realloc(php-a, sizeof(HPDataType) * n);if (php-a NULL) {perror(realloc fail);exit(-1);}// 内存复制 数组复制到php-a中memcpy(php-a, a, sizeof(HPDataType) * n);php-size php-capacity n;// 建堆算法 - 从最后一个叶子节点的父亲节点开始向下调整然后从父亲节点的前所有节点都向下调整一次// 最后节点的父亲的坐标是(n-1-1)/2 n-1因为n是节点个数坐标从0开始for (int i (n - 1 - 1) / 2; i 0; i--) {AdjustDown(php-a, n, i);}
}销毁堆
为了避免内存泄漏使用完动态开辟的内存空间后都要及时释放该空间所以一个用于释放内存空间的函数是必不可少的。
// 堆的销毁
void HeapDestroy(Heap *php) {assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}打印堆
// 堆的打印
void HeapPrint(Heap *php) {assert(php);for (int i 0; i php-size; i) {printf(%d , php-a[i]);}printf(\n);
}堆的插入
数据插入时是插入到数组的末尾即树形结构的最后一层的最后一个结点所以插入数据后我们需要运用堆的向上调整算法对堆进行调整使其在插入数据后仍然保持堆的结构。
// 堆的插入
void HeapPush(Heap *php, HPDataType x) {assert(php);// 内存满了扩容if (php-size php-capacity) {int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType *tmp (HPDataType *) realloc(php-a, sizeof(HPDataType) * newcapacity);if (tmp NULL) {perror(realloc fail);exit(-1);}php-a tmp;php-capacity newcapacity;}// 插入php-a[php-size] x;php-size;// 插入完开始向上调整建堆// 将数组和child的位置传过去AdjustUp(php-a, php-size - 1);
}堆的删除
堆的删除删除的是堆顶的元素但是这个删除过程可并不是直接删除堆顶的数据而是先将堆顶的数据与最后一个结点的位置交换然后再删除最后一个结点再对堆进行一次向下调整。
原因我们若是直接删除堆顶的数据那么原堆后面数据的父子关系就全部打乱了需要全体重新建堆时间复杂度为O(N) 。若是用上述方法那么只需要对堆进行一次向下调整即可因为此时根结点的左右子树都是小堆我们只需要在根结点处进行一次向下调整即可时间复杂度为O(log N)
// 堆的删除
void HeapPop(Heap *php) {assert(php);assert(php-size 0);// 堆的删除因为不能破坏堆的结构所以将堆顶和堆底最后一个数据交换然后删除堆底堆顶再向下调整保持堆的结构// 1.交换堆顶和堆底Swap(php-a[0], php-a[php-size - 1]);// 2.删除堆底php-size--;// 3.向下调整AdjustDown(php-a, php-size, 0);
}获取堆顶的数据
获取堆顶的数据即返回数组下标为0的数据。
// 取堆顶
HPDataType HeapTop(Heap *php) {assert(php);assert(php-size 0);return php-a[0];
}获取堆的长度
获取堆的长度即返回堆结构体中的size变量。
// 求堆的长度
size_t HeapSize(Heap *php) {assert(php);return php-size;
}堆的判空
堆的判空即判断堆结构体中的size变量是否为0。
// 堆的判空
bool HeapEmpty(Heap *php) {assert(php);return php-size 0;
}完整代码
#pragma once
#include assert.h
#include stdbool.h
#include stdio.h
#include stdlib.h
#include string.htypedef int HPDataType;
// 堆的结构 - 顺序表
typedef struct Heap {HPDataType *a;int size;int capacity;
} Heap;// 堆的初始化
void HeapInit(Heap *php) {assert(php);php-a NULL;php-size php-capacity 0;
}// 堆的打印
void HeapPrint(Heap *php) {assert(php);for (int i 0; i php-size; i) {printf(%d , php-a[i]);}printf(\n);
}// 堆的销毁
void HeapDestroy(Heap *php) {assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}// 向上调整 - 大堆
void AdjustUp(HPDataType *a, int child) {// 1.找父亲int parent (child - 1) / 2;// 2.跟父亲比大小如果是大堆知道父亲大于孩子循环结束如果一直小于孩子一直交换然后循环结束条件是child0while (child 0) {// 孩子大于父亲则交换if (a[child] a[parent]) {Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;} else {break;}}
}// 向下调整 - 大堆
void AdjustDown(HPDataType *a, int n, int parent) {// 如果是大堆先找父亲的孩子中的大的然后跟他交换// 先假设左孩子是大的如果不是重新设置为右孩子是大的int child parent * 2 1;// child的值不会越界所以循环条件是child nwhile (child n) {// 重新设置最大的孩子如果右孩子大就child。特殊情况最后的节点只有左孩子没有右孩子所以还要加条判断左孩子1n说明还有一个右孩子if (child 1 n a[child] a[child 1]) {child;}// 1.父亲小于孩子交换继续向下调整// 2.父亲大于孩子跳出if (a[parent] a[child]) {Swap(a[parent], a[child]);// 交换后重新设置parent找下一个位置开始向下调整parent child;child parent * 2 1;} else {break;}}
}// 堆的插入
void HeapPush(Heap *php, HPDataType x) {assert(php);// 内存满了扩容if (php-size php-capacity) {int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType *tmp (HPDataType *) realloc(php-a, sizeof(HPDataType) * newcapacity);if (tmp NULL) {perror(realloc fail);exit(-1);}php-a tmp;php-capacity newcapacity;}// 插入php-a[php-size] x;php-size;// 插入完开始向上调整建堆// 将数组和child的位置传过去AdjustUp(php-a, php-size - 1);
}// 堆的删除
void HeapPop(Heap *php) {assert(php);assert(php-size 0);// 堆的删除因为不能破坏堆的结构所以将堆顶和堆底最后一个数据交换然后删除堆底堆顶再向下调整保持堆的结构// 1.交换堆顶和堆底Swap(php-a[0], php-a[php-size - 1]);// 2.删除堆底php-size--;// 3.向下调整AdjustDown(php-a, php-size, 0);
}// 取堆顶
HPDataType HeapTop(Heap *php) {assert(php);assert(php-size 0);return php-a[0];
}// 求堆的长度
size_t HeapSize(Heap *php) {assert(php);return php-size;
}// 堆的判空
bool HeapEmpty(Heap *php) {assert(php);return php-size 0;
}// 交换
void Swap(HPDataType *p1, HPDataType *p2) {HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}// 堆的创建 - 建堆算法
void HeapCreate(Heap *php, HPDataType *a, int n) {assert(php);php-a (HPDataType *) realloc(php-a, sizeof(HPDataType) * n);if (php-a NULL) {perror(realloc fail);exit(-1);}// 内存复制 数组复制到php-a中memcpy(php-a, a, sizeof(HPDataType) * n);php-size php-capacity n;// 建堆算法 - 从最后一个叶子节点的父亲节点开始向下调整然后从父亲节点的前所有节点都向下调整一次// 最后节点的父亲的坐标是(n-1-1)/2 n-1因为n是节点个数坐标从0开始for (int i (n - 1 - 1) / 2; i 0; i--) {AdjustDown(php-a, n, i);}
}3.堆的应用
堆排序
堆排序即利用堆的思想来进行排序总共分为两个步骤
建堆 升序建大堆降序建小堆 利用堆删除思想来进行排序建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。 代码如下
#include stdio.h
// 交换
void Swap(int *p1, int *p2) {int tmp *p1;*p1 *p2;*p2 tmp;
}// 向下调整 - 大堆
void AdjustDown(int *a, int n, int parent) {// 如果是大堆先找父亲的孩子中的大的然后跟他交换// 先假设左孩子是大的如果不是重新设置为右孩子是大的int child parent * 2 1;// child的值不会越界所以循环条件是child nwhile (child n) {// 重新设置最大的孩子如果右孩子大就child。特殊情况最后的节点只有左孩子没有右孩子所以还要加条判断左孩子1n说明还有一个右孩子if (child 1 n a[child] a[child 1]) {child;}// 1.父亲小于孩子交换继续向下调整// 2.父亲大于孩子跳出if (a[parent] a[child]) {Swap(a[parent], a[child]);// 交换后重新设置parent找下一个位置开始向下调整parent child;child parent * 2 1;} else {break;}}
}// 对数组进行堆排序
void HeapSort(int *a, int n) {// 向上调整建堆 -- N*logN/*for (int i 1; i n; i){AdjustUp(a, i);}*/// 向下调整建堆 - 大堆 O(N) _for (int i (n - 1 - 1) / 2; i 0; i--) {AdjustDown(a, n, i);}int end n - 1;while (end 0) {// 第一个和最后一个交换除了最后一个剩下的进行建堆调整把最大的调整到堆顶Swap(a[0], a[end]);// end为坐标坐标比个数多一个所以下面的end是剩余的个数AdjustDown(a, end, 0);end--;}
}int main() {int arr[10] {32, 43, 56, 76, 84, 12, 45, 67, 43, 37};HeapSort(arr, sizeof(arr) / sizeof(int));for (int i 0; i sizeof(arr) / sizeof(int); i) {printf(%d , arr[i]);}
}TOPK问题
TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。
比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下
用数据集合中前K个元素来建堆 前k个最大的元素则建小堆前k个最小的元素则建大堆 用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
//交换函数
void Swap(int *x, int *y) {int tmp *x;*x *y;*y tmp;
}
//堆的向下调整小堆
void AdjustDown(int *a, int n, int parent) {//child记录左右孩子中值较小的孩子的下标int child 2 * parent 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 2 * parent 1;} else {//已成堆break;}}
}int *getLeastNumbers(int *arr, int arrSize, int k, int *returnSize) {*returnSize k;if (k 0)return NULL;//用数组的前K个数建小堆int i 0;int *retArr (int *) malloc(sizeof(int) * k);for (i 0; i k; i) {retArr[i] arr[i];}for (i (k - 1 - 1) / 2; i 0; i--) {AdjustDown(retArr, k, i);}//剩下的N-k个数依次与堆顶数据比较for (i k; i arrSize; i) {if (arr[i] retArr[0]) {retArr[0] arr[i];//堆顶数据替换}AdjustDown(retArr, k, 0);//进行一次向下调整}return retArr;//返回最大的k个数
}时间复杂度O(k N * log k)空间复杂度O(k)
