数据结构--顺序结构二叉树（堆）

目录1. 二叉树1.1 概念与结构1.2 特殊的二叉树1.2.1 满二叉树1.2.2 完全二叉树1.2.3 二叉树性质1.3 二叉树存储结构1.3.1 顺序结构1.3.2 链式结构2. 实现顺序结构二叉树2.1 堆的概念与结构2.2 堆的实现2.2.1 代码解析1. 插入操作以小堆为例2. Pop删除3. 向上调整算法4. 向下调整算法5. test1测试样例2.2.2 代码编写Heap.h 头文件Heap.c 源文件test.c 源文件3.堆的应用3.1 堆排序3.2 Top-k 问题正文开始1. 二叉树1.1 概念与结构在树形结构中我们最常用的就是二叉树一棵二叉树是结点的一个有限集合该集合由一个根结点加上两棵别称为左子树和右子树的二叉树组成或者为空。从上图可以看出二叉树具备以下特点二叉树不存在度大于2的结点二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树注意对于任意的二叉树都是由以下几种情况复合而成的1.2 特殊的二叉树1.2.1 满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为k且结点总数是2^k−12的k次方 -1则它就是满二叉树。1.2.2 完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。1.2.3 二叉树性质根据满二叉树的特点可知若规定根结点的层数为1则一棵非空二叉树的第 i层上最多有 2的(i-1)次方个结点若规定根结点的层数为1则深度为h的二叉树的最大结点数是 2的h次方-1若规定根结点的层数为1具有n个结点的满二叉树的深度hlog2(n1)(log以2为底n1为对数)1.3 二叉树存储结构二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。1.3.1 顺序结构顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费完全二叉树更适合使用顺序结构存储。现实中我们通常把堆一种二叉树使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。1.3.2 链式结构二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链和三叉链当前只介绍二叉链。2. 实现顺序结构二叉树一般堆使用顺序结构的数组来存储数据堆是一种特殊的二叉树具有二叉树的特性的同时还具备其他的特性。堆在物理上来说是一个数组在逻辑上来说是一个顺序结构的二叉树。2.1 堆的概念与结构如果有一个关键码的集合K{k0,k1,k2,...kn−1}把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足KiK2∗i1KiK2∗i1且KiK2∗i2i 0、1、2 ...则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆根结点最小的堆叫做最小堆或小根堆。堆具有以下性质堆中某个结点的值总是不大于或不小于其父结点的值堆中的兄弟节点间没有大小关系堆总是一棵完全二叉树。对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有结点从0开始编号则对于序号为i的结点有若i0i位置结点的双亲序号(i-1)/2i 0i为根结点编号无双亲结点若2i1左孩子序号2i12i1n否则无左孩子若2i2右孩子序号2i22i2n否则无右孩子2.2 堆的实现堆的底层结构为数组2.2.1 代码解析1. 插入操作以小堆为例若以上述插入10数据为例插入后再经判断后此堆有不符合小堆定义的情况则需要向上调整10这个数据的位置调整过程涉及数据比较、数据交换。如AdjustUp()函数所示。2. Pop删除要求删除堆顶的数据根位置注意不能选择暴力的直接删除堆顶数据的方式因为这样的删除操作会打乱堆的基本结构。正确的做法是将堆顶的数据和堆末尾的数据互换互换之后进行堆末尾的删除然后再利用向下调整函数AdjustDown()将堆调整为正确的结构实现Pop的正确操作3. 向上调整算法将新数据插入到数组的尾上再进行向上调整算法直到满足堆。先将元素插入到堆的末尾,即最后一个孩子之后插入之后如果堆的性质遭到破坏将新插入结点顺着其双双亲往上调整到合适位置即可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 (parent - 1) / 2; } else { break; } } } void HPPush(HP* php, HPDataType x) { assert(php); if (php-size php-capacity) { newCapacity php-capacity 0 ? 4 : php-capacity * 2; HPDataType* tmp realloc(php-a, (HPDataType)*newCapacity); if (tmp NULL) { perror(realloc fail); return; } php-a tmp; php-capacity newCapacity; } php-a[php-size] x; php-size; AdjustUp(php-a, php-size - 1); }4. 向下调整算法删除堆是删除堆顶的数据将堆顶的数据根最后一个数据一换然后删除数组最后一个数据再进行向下调整算法。向下调整算法有一个前提左右子树必须是一个堆才能调整。将堆顶元素与堆中最后一个元素进行交换删除堆中最后一个元素将堆顶元素向下调整到满足堆特性为止void AdjustDown(HPDataType* 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 HPPop(HP* php) { assert(php); assert(php-size 0); Swap(php-a[0], php-a[php-size - 1]); php-size--; AdjustDown(php-a, php-siz, 0); }5. test1测试样例注若想调整小堆调整为大堆只需调整向上调整算法和向下调整算法中的比较逻辑即可此处不做过多解释。2.2.2 代码编写Heap.h 头文件#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #includestdio.h #includeassert.h #includestdlib.h #includestdbool.h typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }HP; void HPInit(HP* php); void HPDestroy(HP* php); void Swap(HPDataType* p1, HPDataType* p2); void AdjustUp(HPDataType* a, int child); void AdjustDown(HPDataType* a, int n, int parent); void HPPush(HP* php, HPDataType x); void HPPop(HP* php); HPDataType HPTop(HP* php); bool HPEmpty(HP* php);Heap.c 源文件#define _CRT_SECURE_NO_WARNINGS #includeHeap.h void HPInit(HP* php) { assert(php); php-a NULL; php-size php-capacity 0; } void HPDestroy(HP* php) { assert(php); free(php-a); php-a NULL; php-size php-capacity 0; } void Swap(HPDataType* p1, HPDataType* p2) { HPDataType tmp *p1; *p1 *p2; *p2 tmp; } void AdjustUp(HPDataType* a, int child) { // 初始条件 // 中间过程 // 结束条件 int parent (child - 1) / 2; //while (parent 0) while (child 0) { if (a[child] a[parent]) { Swap(a[child], a[parent]); child parent; parent (child - 1) / 2; } else { break; } } } void HPPush(HP* 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, newcapacity * sizeof(HPDataType)); if (tmp NULL) { perror(realloc fail); return; } php-a tmp; php-capacity newcapacity; } php-a[php-size] x; php-size; AdjustUp(php-a, php-size - 1); } void AdjustDown(HPDataType* a, int n, int parent) { // 先假设左孩子小 int child parent * 2 1; while (child n) // 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; } } } //最坏的情况下时间复杂度为logN void HPPop(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); } HPDataType HPTop(HP* php) { assert(php); assert(php-size 0); return php-a[0]; } bool HPEmpty(HP* php) { assert(php); return php-size 0; }test.c 源文件#define _CRT_SECURE_NO_WARNINGS #include Heap.h void test1() { int a[] { 4,2,8,1,5,6,9,7 }; HP hp; HPInit(hp); for (size_t i 0; i sizeof(a) / sizeof(int); i) { HPPush(hp, a[i]); } } void test2() { int a[] { 4,2,8,1,5,6,9,7,3,2,23,55,232,66,222,33,7,1,66,3333,999 }; HP hp; HPInit(hp); for (size_t i 0; i sizeof(a) / sizeof(int); i) { HPPush(hp, a[i]); } int i 0; while (!HPEmpty(hp)) { printf(%d , HPTop(hp)); HPPop(hp); } printf(\n); HPDestroy(hp); } void test3() { int a[] { 4,2,8,1,5,6,9,7,3,2,23,55,232,66,222,33,7,1,66,3333,999 }; HP hp; HPInit(hp); for (size_t i 0; i sizeof(a) / sizeof(int); i) { HPPush(hp, a[i]); } //找出最小的前k个 int k 0; scanf(%d, k); while (k--) { printf(%d , HPTop(hp)); HPPop(hp); } printf(\n); HPDestroy(hp); } int main() { //test1(); //小堆的数据插入测试 //test2(); //将小堆里的数据以升序的形式打印显示出来 //test3(); //找出最小的前k个测试该测试时间复杂度为O() return 0; }3.堆的应用3.1 堆排序相较于冒泡排序其时间复杂度为O( N² )堆排序更具实际意义其时间复杂度为O(N * LogN)。版本一基于已有数组建堆、取堆顶元素完成排序版本。但有个前提必须提供有现成的数据结构堆//需要堆的数据结构 //空间复杂度为O(N) void HeapSort(int* a, int n) { HP hp; for (int i 0; i n; i) { HPPush(hp, a[i]); } int i 0; while (!HPEmpty(hp)) { a[i] HPTop(hp); HPPop(hp); } HPDestroy(hp); }版本二数组建堆首尾交换交换后的堆尾数据从堆中删掉将堆顶数据向下调整选出次大的数据。//升序建大堆 //降序建小堆 //O(N*logN) void HeapSort(int* a, int n) { //a数组直接建堆o(N) for (int i (n - 1 - 1) / 2; i 0; --i) { AdjustDown(a, n, i); //向下调整建堆法 } //O(N*logN) int end n - 1; while (end 0) { Swap(a[0], a[end]); AdjustDown(a, end, 0); --end; } }向下建堆法说明此建堆法采取的是从倒数第一个非叶子节点开始往上依次进行向下调整算法的方式进行建堆。即下图中数字5的位置i (n-1-1/2)开始调整。此建堆法时间复杂度为O(N)3.2 Top-k 问题Top-k 问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下第一步用数据集合中的前k个来建堆需要获取数据中的前k个最大的元素则建小堆需要获取数据中的前k个最小的元素则建大堆第二步用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素void CreateNData() { //造数据 int n 100000; srand(time(0)); const char* file data.txt; FILE* fin fopen(file, w); if (fin NULL) { perror(fopen fail); return; } for (int i 0; i n; i) { int x (rand() i) % 1000000; fprintf(fin, %d\n, x); } fclose(fin); } void topk() { printf(请输入k: ); int k 0; scanf(%d, k); const char* file data.txt; FILE* fout fopen(file, r); if (fout NULL) { perror(fopen fail); return; } int val 0; int* minheap (int*)malloc(sizeof(int) * k); if (minheap NULL) { perror(malloc fail); return; } for (int i 0; i k; i) { fscanf(fout, %d, minheap[i]); } //建k个数据的小堆 for (int i (k - 1 - 1) / 2; i 0; i--) { AdjustDown(minheap, k, i); } int x 0; while (fscanf(fout, %d, x) ! EOF) { //读取剩余数据比堆顶的值大就替换他进堆 if (x minheap[0]) { minheap[0] x; AdjustDown(minheap, k, 0); } } for (int i 0; i k; i) { printf(%d , minheap[i]); } fclose(fout); }