杭州网站优化方案,龙岩网站建设哪里比较好,金华规划局网站开发区,什么是网站风格在数据结构之《二叉树》(上)中学习了树的相关概念#xff0c;还了解的树中的二叉树的顺序结构和链式结构#xff0c;在本篇中我们将重点学习二叉树中的堆的相关概念与性质#xff0c;同时试着实现堆中的相关方法#xff0c;一起加油吧#xff01; 1.实现顺序结构二叉树
在…在数据结构之《二叉树》(上)中学习了树的相关概念还了解的树中的二叉树的顺序结构和链式结构在本篇中我们将重点学习二叉树中的堆的相关概念与性质同时试着实现堆中的相关方法一起加油吧 1.实现顺序结构二叉树
在实现顺序结构的二叉树中通常把堆使用顺序结构的数组来存储因此我们先要了解堆的概念与结构
1.1 堆的概念与结构
如果有一个关键码的集合 K {k0 , k1 , k2 , ...kn−1 } 把它的所有元素按完全二叉树的顺序存储方式式存储在⼀个⼀维数组中并满足 Ki K2∗i1 Ki K2∗i1 且 Ki K2∗i2 i 0、1、2... 则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆根结点最小的堆叫做最小堆或小根堆。
以上的堆的概念简单来说就是堆是完全二叉树在大堆中根结点为最大的元素在此之后的每个孩子结点都要小于或者等于它的父结点在小堆中根结点为最小的元素在此之后的每个孩子结点都要大于或者等于的父结点 因此通过堆的概念的了解需要知道堆有以下的性质• 堆中某个结点的值总是不大于或不小于其父结点的值• 堆总是一棵完全二叉树 例如以下图示就是大堆并且将其结点的数据存储到数组当中 以下图示就是小堆并且将其结点的数据存储到数组当中 1.2二叉树的性质
在了解的堆的相关概念和结构后之后我们要来实现堆因此在此之前还要再了解二叉树的相关性质 二叉树性质• 对于具有 n 个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有结点从0 开始编号则对于序号为 i 的结点有1. 若 i0 i 位置结点的双亲序号 i0 i 为根结点编号无双亲结点2. 若 2i1n 左孩⼦序号 2i1n 否则无左孩子3. 若 2i2n 右孩⼦序号 2i2n 否则无右孩子 对以上的性质来通过一个示例来加深理解 以下就是根据二叉树的性质来求出各节点的孩子结点以及父结点的图示 1.3堆的实现
在了解了堆相关的性质与结构后接下来就可以来试着实现堆 在实现堆的程序中还是将代码分为三个文件 1.堆结构的定义
//堆结构的定义
typedef int HDataType;
typedef struct Heap
{HDataType* arr;int size;//有效数据个数int capacity;//空间大小
}Heap;
在定义堆的结构中使用一个结构体来定义堆的结构里面的成员变量和顺序表中相同arr为数组首元素的指针size为数组中有效元素的个数capacity为数组空间的大小
2.堆的初始化
在堆的初始化函数的实现中先要在Heap.h内完成初始化函数的声明
//初始化堆
void HeapInit(Heap* php);
将该函数命名为HeapInit函数的参数为结构体指针
在完成了函数的声明后就是在Heap.c内完成函数的定义
//初始化堆
void HeapInit(Heap* php)
{assert(php);php-arr NULL;php-size php-capacity 0;
} 3.堆的插入 在堆的插入函数的实现中先要在Heap.h内完成插入函数的声明
//堆的插入
void HeapPush(Heap* php,HDataType x);
将该函数命名为HeapPush函数参数有两个第一个为结构体指针第二个为要插入的数据
在完成了函数的声明后就是在Heap.c内完成函数的定义
在堆的插入当中我们要实现的是在堆的末尾插入数据也就是在数组的size-1位置插入新的数据并且在插入之后由于堆的特性还要将堆中各元素的位置进行调整使得其变为一个小堆或者大堆
因此在插入函数中我们先要实现向上调整的函数
3.1 向上调整法
要实现堆中的向上调整结点的函数首先要来分析在调整过程中需要实现哪些步骤我们来看下面这个堆的示例 在这个小堆中我们先在堆的末尾插入数据为10的结点在这之后要将该二叉树重新调整为小堆需要哪些操作呢 首先就是要将新插入的结点10与它的父结点做对比如果比父结点大就和父结点交换之后再和父结点的父结点比较重复以上操作直到最后父结点为0时就停止在此过程中如果比父结点小就不进行交换 所以以上的二叉树要调整为小堆就要经过以下的步骤 在完全向上调整实例的分析后接下来就可以来实现向上调整的代码 先再Heap.h内对向上调整函数进行声明通过以上的分析就可以推测出函数的参数有两个一个为数组的首元素指针另一个为数组的有效元素个数 //向上调整法
void AdjustUp(HDataType* arr, int child); 在以下的代码当中parent就来表示父结点的数组下标child就来表示孩子节点的下标因此在知道孩子结点的下标时要求父结点的下标就可以用到前面提到的二叉树的性质父结点的下标等于其孩子结点下标减一再除以二
//向上调整法
void AdjustUp(HDataType* arr, int child)
{int parent (child - 1) / 2;//求父结点下标while (child0){//小堆时下面的if判断部分就用//大堆时下面的if判断部分就用if (arr[child] arr[parent])//若父结点大于孩子结点就交换{Swap(arr[child], arr[parent]);child parent;parent (child - 1) / 2;}else{break;//若不符合以上if的条件就退出循环}}
} 例如以上的示例中在以下代码中parent和child的变化就如以下图所示 在以上函数中的Swap是来实现两个数的交换以下是函数的定义 void Swap(HDataType* p1, HDataType* p2)
{HDataType* tmp *p1;*p1 *p2;*p2 tmp;
} 3.2 插入函数代码实现
在完成了向上调整的代码后接下来就可以来完成堆插入函数的实现
在插入函数中由于php为结构体指针因此php不能为空所以要将php进行assert断言并且在插入之前也要判断数组空间是否满了满了就要对空间进行调整在此的调整代码和顺序表中相同 之后再将数据尾插到数组当中再进行向上调整最后切记要将size1
//堆的插入
void HeapPush(Heap* php, HDataType x)
{assert(php);if (php-size php-capacity)//对数组空间进行调整{int newcapacity php-capacity 0 ? 4 : 2 * php-capacity;Heap* tmp (Heap*)realloc(php-arr,sizeof(HDataType) * newcapacity);if (tmp NULL){perror(malloc file);exit(1);}php-arr tmp;php-capacity newcapacity;}php-arr[php-size] x;//进行尾插AdjustUp(php-arr, php-size);//进行向上调整php-size;
} 4.堆的删除
在堆的删除函数的实现中先要在Heap.h内完成删除函数的声明
//堆的删除
void HeapPop(Heap* php);
将该函数命名为HeapPop函数的参数是结构体指针
在完成了函数的声明后就是在Heap.c内完成函数的定义
在堆的删除中是将跟结点给删除在删除过程中是将根结点和最后一个结点交换之后将数组的有效个数减一这样就将原来的根结点给删除了之后再进行各结点的调整使其重新变为一个堆
因此在插入函数中我们先要实现向下调整的函数
4.1向下调整法
要实现堆中的向下调整结点的函数首先要来分析在调整过程中需要实现哪些步骤我们来看下面这个堆的示例
在这个小堆中我们如果已经跟结点删除在这之后要将该二叉树重新调整为小堆需要哪些操作呢 首先就是要将新的的跟结点70与它的两个孩子结点中小的做对比如果比该孩子结点大就和该孩子结点交换之后再和该孩子结点的两的孩子结点中小的比较重复以上操作直到最后开始的跟结点为叶子节点时就停止如果在这过程中比孩子结点中小的那个还小就不进行交换 所以以上的二叉树要调整为小堆就要经过以下的步骤 在完全向下调整实例的分析后接下来就可以来实现向下调整的代码 先再Heap.h内对向上调整函数进行声明通过以上的分析就可以推测出函数的参数有三个一个为数组的首元素指针另一个为数组的有效元素个数 最后一个是要向下调整的元素的数组下标 //向下调整法
void AdjustDown(HDataType* arr, int n, int parent); 之后就是在Heap.c内完成函数的定义 在以下的代码当中parent就来表示父结点的数组下标child就来表示孩子节点的下标因此在知道父结点的下标时要求孩子结点的下标就可以用到前面提到的二叉树的性质孩子结点的下标等于其父结点下标乘二再加一或二
while循环中当孩子节点下标大于数组有效个数也就是父节点为叶子节点时就退出循环因此进入while条件为childn
//向下调整法
void AdjustDown(HDataType* arr, int n, int parent)
{int child 2 * parent 1;//孩子节点的下标while (childn){//如果为小堆 以下的if判断部分就用//如果为大堆 以下的if判断部分就用if (child1n arr[child] arr[child 1]){child;//若为小堆就找孩子节点中小的大堆就找孩子节点中大的}if (arr[parent] arr[child])//若孩子节点小于父节点就交换{Swap(arr[parent], arr[child]);parent child;child 2 * parent 1;}else{break;//若不符合以上if的条件就退出循环}}
} 例如以上的示例中在以下代码中parent和child的变化就如以下图所示 4.2删除函数代码实现
在插入函数中由于php为结构体指针因此php不能为空所以要将php进行assert断言在删除函数中因为要删除的是堆的根结点所以先将堆的根结点和堆的最后一个节点进行交换之后再将size-1这样就可以让数组当中的有效个数减一使得原来的根结点被删除之后再将该二叉树使用向下调整重新调整为堆
//堆的删除
void HeapPop(Heap* php)
{assert(php php-size);php-arr[0] php-arr[php-size - 1];--php-size;AdjustDown(php-arr, php-size, 0);
} 5.取堆顶的元素
在堆的取堆顶的元素函数的实现中先要在Heap.h内完成取堆顶的元素函数的声明
//取堆顶的元素
HDataType HeapTop(Heap* php);
将该函数命名为HeapTop函数的参数是结构体指针函数的返回值是堆跟结点内的数据
在完成了函数的声明后就是在Heap.c内完成函数的定义
//取堆顶的元素
HDataType HeapTop(Heap* php)
{assert(php);return php-arr[0];
}6.堆的数据个数
在求堆的数据个数函数的实现中先要在Heap.h内完成堆的数据个数函数的声明
//堆的数据个数
int HeapSize(Heap* php);
将该函数命名为HeapSize函数的参数是结构体指针函数的返回值是堆的结点结点个数
在完成了函数的声明后就是在Heap.c内完成函数的定义因为堆是用数组来实现的所以堆中的结点个数就为数组的有效元素个数
//堆的数据个数
int HeapSize(Heap* php)
{assert(php);return php-size;
} 7.堆的判空
在判断堆是否为空函数的实现中先要在Heap.h内完成判断堆是否为空函数的声明
//堆的判空
bool HeapEmpty(Heap* php);
将该函数命名为HeapEmpty函数的参数是结构体指针函数的返回类型是布尔类型
在完成了函数的声明后就是在Heap.c内完成函数的定义在该函数中当当堆为空时就返回true不为空时返回false
//堆的判空
bool HeapEmpty(Heap* php)
{assert(php);return php-size 0;
} 8.堆的销毁
在堆的销毁函数的实现中先要在Heap.h内完成堆的销毁函数的声明
//销毁堆
void HeapDestory(Heap* php);
将该函数命名为HeapDestory函数的参数是结构体指针
在完成了函数的声明后就是在Heap.c内完成函数的定义
//销毁堆
void HeapDestory(Heap* php)
{assert(php);if (php-arr){free(php-arr);}php-arr NULL;php-size php-capacity 0;
} 9.堆实现完整代码
Heap.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h//堆结构的定义
typedef int HDataType;
typedef struct Heap
{HDataType* arr;int size;//有效数据个数int capacity;//空间大小
}Heap;//初始化堆
void HeapInit(Heap* php);
//销毁堆
void HeapDestory(Heap* php);
//堆的插入
void HeapPush(Heap* php,HDataType x);
//堆的删除
void HeapPop(Heap* php);
//取堆顶的元素
HDataType HeapTop(Heap* php);
//堆的数据个数
int HeapSize(Heap* php);
//堆的判空
bool HeapEmpty(Heap* php);
//向上调整法
void AdjustUp(HDataType* arr, int child);
//向下调整法
void AdjustDown(HDataType* arr, int n, int parent);
Heap.c
#includeHeap.hvoid Swap(HDataType* p1, HDataType* p2)
{HDataType* tmp *p1;*p1 *p2;*p2 tmp;
}//向上调整法
void AdjustUp(HDataType* arr, int child)
{int parent (child - 1) / 2;while (child0){//小堆 //大堆 if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);child parent;parent (child - 1) / 2;}else{break;}}}//向下调整法
void AdjustDown(HDataType* arr, int n, int parent)
{int child 2 * parent 1;while (childn){//小堆 //大堆 if (child1n arr[child] arr[child 1]){child;}if (arr[parent] arr[child]){Swap(arr[parent], arr[child]);parent child;child 2 * parent 1;}else{break;}}
}//初始化堆
void HeapInit(Heap* php)
{assert(php);php-arr NULL;php-size php-capacity 0;
}//销毁堆
void HeapDestory(Heap* php)
{assert(php);if (php-arr){free(php-arr);}php-arr NULL;php-size php-capacity 0;
}//堆的插入
void HeapPush(Heap* php, HDataType x)
{assert(php);if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : 2 * php-capacity;Heap* tmp (Heap*)realloc(php-arr,sizeof(HDataType) * newcapacity);if (tmp NULL){perror(malloc file);exit(1);}php-arr tmp;php-capacity newcapacity;}php-arr[php-size] x;AdjustUp(php-arr, php-size);php-size;
}//堆的删除
void HeapPop(Heap* php)
{assert(php php-size);php-arr[0] php-arr[php-size - 1];--php-size;AdjustDown(php-arr, php-size, 0);
}//取堆顶的元素
HDataType HeapTop(Heap* php)
{assert(php);return php-arr[0];
}//堆的数据个数
int HeapSize(Heap* php)
{assert(php);return php-size;
}//堆的判空
bool HeapEmpty(Heap* php)
{assert(php);return php-size 0;
} 2.堆的应用
1.堆排序
在之前的C语言的学习当中我们实现了冒泡排序但在算法的复杂度中得出了冒泡排序的时间复杂度为O(n^2),因此其实冒泡排序的效率是不高的。接下来我们就要来学习一种使用堆来实现排序的算法。
在此之前通过学习堆的相关概念知道了在小堆中的根结点是堆中最小的那么在小堆中只要一直取堆的根结点就可以得到升序的数据以下就是使用这种方法来实现的堆排序
void HeapSort(int* a, int n)
{Heap hp;for(int i 0; i n; i){HeapPush(hp,a[i]);}int i 0;while (!HeapEmpty(hp)){a[i] HeapTop(hp);HeapPop(hp);}HeapDestroy(hp);
}
但是在以上的这种算法中需要将数组中的数据先要先存储在堆当中才能在之后得到堆顶的数据因此以上这种方法的空间复杂度就为O(n),那么有什么方法能在不申请新的空间下来实现堆排序呢接下来就来看以下的这种基于原来数组建堆的方法
//堆排序算法
void HeapSort(int* arr, int n)
{for (int i 0; i n; i){AdjustUp(arr, i);}int end n - 1;while (end 0){Swap(arr[end], arr[0]);AdjustDown(arr, end, 0);end--;}for (int i 0; i n; i){printf(%d , arr[i]);}
}
在以上这种堆排序中先用向上调整法来将数组通过循环的将数组数组调整为堆根据之前向上调整的代码在此的建的是小堆。之后的while循环中实现的是将小堆中的跟结点和尾结点进行交换这时数组中最小的元素就排在了数组的末尾之后再进行向下排序就可重新变为小堆一直重复以上的操作就可以将数组的元素从小到大依次移动到数组末尾最终原数组就变为升序的了。
那么以上除了使用向上调整建堆外其实使用向下调整法也可以建堆以下是使用向下调整法建堆的代码
//堆排序算法
void HeapSort(int* arr, int n)
{for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(arr, n, i);}int end n - 1;while (end 0){Swap(arr[end], arr[0]);AdjustDown(arr, end, 0);end--;}for (int i 0; i n; i){printf(%d , arr[i]);}
}
这两种那一这种效率更好呢这就需要来分析向上建堆和向下建堆的时间复杂度
先来看向上调整法
因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值多几个结点不影响最终结果)
以下是各层的结点在向上调整过程中各层结点在调整过程中最坏的情况下移动的层数 需要移动结点总的移动步数为每层结点个数 * 向上调整次数第⼀层调整次数为0
由此可得 向上调整算法建堆时间复杂度为 O(n ∗ log2 n)
接下来看向下调整法
以下是各层的结点在向下调整过程中各层结点在调整过程中最坏的情况下移动的层数 则需要移动结点总的移动步数为每层结点个数 * 向下调整次数 向下调整算法建堆时间复杂度为 O(n)
通过以上的分析后可以得出在堆排序中使用向下调整法建堆更好
堆排序第二个循环中的向下调整与建堆中的向上调整算法时间复杂度计算一致。因此堆排序的时间复杂度为 O(n n ∗ log n) 即 O(n log n) 2.TOP-K问题
TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。 比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下⼦全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下 1用数据集合中前K个元素来建堆 前k个最大的元素则建小堆 前k个最小的元素则建大堆2用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者大的元素 以下这段代码可以实现将大量的整型数据输入到data.txt的文件当中
void CreateNDate()
{// 造数据int n 100000;srand(time(0));const char* file data.txt;FILE* fin fopen(file, w);if (fin NULL){perror(fopen error);return;}for (int i 0; i n; i){int x (rand() i) % 1000000;fprintf(fin, %d\n, x);}fclose(fin);
} 接下来就来实现解决TOP-K问题的代码以下是实现的是得出数据结合中前K个最大的元素
void topk()
{int k0;printf(k:);scanf(%d, k);//读取文件中的前k个数据FILE* pf fopen(data.txt, r);if (pf NULL){perror(fopen fail);exit(1);}int* pa (int*)malloc(k * sizeof(int));if (pa NULL){perror(malloc fail);exit(2);}for (int i 0; i k; i){fscanf(pf, %d, pa[i]);}//使用前k个数据建堆for (int i (k - 1 - 1) / 2; i 0; i--){AdjustDown(pa, k, i);}int tmp0;//循环将k个数据之后的数据堆中最小的元素比较若比这个元素大就交换while (fscanf(pf, %d, tmp) ! EOF){if (tmp pa[0]){pa[0] tmp;AdjustDown(pa, k, 0);}}for (int i 0; i k; i){printf(%d , pa[i]);}fclose(pf);pf NULL;}以上就是二叉树(中)的全部内容了接下来在二叉树(下)将继续学习二叉树的知识在下一篇中我们将重点学习链式结构的二叉树的相关知识未完待续……
