树--二叉树--堆

本节目标简单了解树二叉树堆的概念认识堆这个数据结构堆排序topk问题一、树的概念及结构1.树的概念在现实生活中树是随处可见的如下图,那么数据结构中的树是什么样的数据结构中的“树”看起来像是一颗倒挂的树根在最上面向下生长形成许多分支。树的定义树是一种非线性的数据结构由节点或称为顶点和边组成具有以下特性有且仅有一个根节点树中唯一没有父节点的节点作为整个树的起点。除根节点外每个节点有且仅有一个父节点从根到任意节点有且只有一条路径。无环树中不存在任何环路即不能从某个节点出发沿着边回到自身。连通性任意两个节点之间通过唯一路径连接。2.树的相关术语树的基本术语节点Node树中的每个元素称为节点包含数据项及指向其他节点的分支。根节点Root树的顶层节点没有父节点是整棵树的起点。父节点Parent一个节点的直接上层节点称为其父节点。子节点Child一个节点的直接下层节点称为其子节点。叶节点Leaf没有子节点的节点位于树的末端。内部节点Internal Node至少有一个子节点的非根节点。树的层级与关系度Degree一个节点拥有的子节点数量称为该节点的度。树的度Tree Degree树中所有节点的度的最大值。层次Level根节点为第1层或第0层取决于定义其子节点为第2层以此类推。高度Height从某节点到其最远叶节点的最长路径边数。树的高度即根节点的高度。深度Depth从根节点到某节点的路径边数。根节点的深度为0或1。3.树的分类树可以根据其特性分为多种类型包括二叉树、满二叉树、完全二叉树、二叉搜索树和平衡二叉树等。下面我们将重点介绍前三种类型。1.二叉树二叉树概念二叉树是一种树形数据结构每个节点最多有两个子节点分别称为左子节点和右子节点。事实上任意二叉树的构成为以下几种情况2.满二叉树和完全二叉树满二叉树概念和性质满二叉树是一种特殊的二叉树结构其特点是每一层的节点都达到最大数量。具体定义为所有非叶子节点都有两个子节点左子节点和右子节点。所有叶子节点都位于同一层。若满二叉树的深度为 ( h )根节点深度为 1则其总节点数为[ N 2^k - 1 ]叶子节点数为 ( 2^{h-1} )完全二叉树概念和性质完全二叉树是二叉树的一种特殊形式满足以下条件结构特性前 (k-1) 层是满的第 (k) 层的节点集中在左侧。最后一层可以不满但缺失的节点必须位于右侧。对于满二叉树和完全二叉树若从根节点开始按照从上到下从左到右的顺序从0开始编号则对序号为i的节点有(树有n个节点)若i0,则i节点的父节点序号为(i-1)/2,若i0,i为根节点无父节点若2i1n,则i节点的左孩子序号为2i1若2i1n,则无左孩子若2i2n,则i节点的右孩子序号为2i2若2i2n,则无右孩子二、堆二叉树的存储结构二叉树一般可以使用两种方式来存储顺序结构以及链式结构1.顺序存储顺序存储是指将二叉树每个节点按顺序存储到数组中完全二叉树按照存储的顺序能够找到其父节点或子节点也能够高效利用空间。而非完全二叉树则会浪费一定的空间。2.链式存储链式存储通过节点对象和指针来实现每个节点包含数据域和左右子节点指针。适用于任意形态的二叉树空间利用率灵活。链式存储将在后续博客中讲解。堆的概念和实现普通的二叉树用数组实现会造成空间浪费而完全二叉树则非常适合用数组来存储现实中我们通常把堆一种完全二叉树使用数组来存储。堆的概念堆是一种特殊的完全二叉树结构其每个节点的值都遵循特定的顺序关系。具体来说堆可以分为两种主要类型小堆最小堆/Min-Heap每个节点的值都小于或等于其子节点的值根节点是整个堆中的最小值典型操作时间复杂度获取最小值O(1)插入元素O(log n)删除最小值O(log n)大堆最大堆/Max-Heap每个节点的值都大于或等于其子节点的值根节点是整个堆中的最大值示例应用场景堆排序算法、求Top K问题典型操作时间复杂度获取最大值O(1)插入元素O(log n)删除最大值O(log n)堆的存储通常使用数组实现利用完全二叉树的性质可以高效地进行节点定位对于任意节点i从0开始计数父节点位置(i-1)/2左子节点位置2i1右子节点位置2i2堆的一个重要特性是对于一个包含n个元素的堆其高度为⌊log₂n⌋这使得堆的各种操作都能保持较好的时间复杂度。在构建堆时可以采用自底向上的堆化方法时间复杂度为O(n)。堆的实现1.Heap.h文件#pragma once #includestdio.h #includestdlib.h #includestdbool.h #includeassert.h typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }HP; //交换 void Swap(HPDataType* p1, HPDataType* p2); //初始化销毁 void HeapInit(HP* php); void HeapDestroy(HP* php); //插入删除 void HeapPush(HP* php, HPDataType x); void HeapPop(HP* php); //取堆顶 HPDataType HeapTop(HP* php); //判空 bool HeapEmpty(HP* php); //调整 void AdjustUp(HPDataType* a, int child); void AdjustDown(HPDataType* a, int n, int parent);2.Heap.c文件#include Heap.h void Swap(HPDataType* p1, HPDataType* p2) { HPDataType tmp *p1; *p1 *p2; *p2 tmp; } 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 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; } } } void HeapPush(HP* php, HPDataType x) { assert(php); if (php-size php-capacity) { int newcapacity (php-capacity 0) ? 4 : 2 * php-capacity; 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) { if (child 1 n a[child] a[child 1]) //看建小堆还是大堆改变符号 { child; } if (a[child] a[parent]) //看建小堆还是大堆改变符号 { Swap(a[child], a[parent]); parent child; child parent * 2 1; } else { break; } } } 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); } //取堆顶 HPDataType HeapTop(HP* php) { assert(php); assert(php-size 0); return php-a[0]; } //判空 bool HeapEmpty(HP* php) { assert(php); return php-size 0; }堆的调整算法向上调整算法在插入新节点时首先确定该节点的位置然后将其数据与父节点进行比较。如果是小堆结构且新节点的数据小于父节点数据则交换两者的位置并将父节点序号赋给子节点。重复这一比较过程直至满足条件child 0。(大堆类似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; } } }向下调整算法将该节点数据与子节点进行比较 如果是小堆且该节点的数据大于子节点数据则交换两者的位置并将子节点序号赋给父节点重复这一比较过程直至满足条件child nvoid AdjustDown(HPDataType* a, int n, int parent) { int child parent * 2 1; while (child n) { if (child 1 n a[child] a[child 1]) //看建小堆还是大堆改变符号 { child; } if (a[child] a[parent]) //看建小堆还是大堆改变符号 { Swap(a[child], a[parent]); parent child; child parent * 2 1; } else { break; } } }建堆向上调整建堆及其时间复杂度分析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; HeapInit(hp); for (int i 0; i sizeof(a) / sizeof(int); i) { HeapPush(hp, a[i]); }向下调整建堆及其时间复杂度分析for (int i (n-1-1)/2; i 0; i--) { AdjustDown(a, n, i); }向上调整与向下调整算法实际上是不同的层数的调整次数不同向上调整算法是节点多*调整次数多向下调整算法是节点多*调整次数少所以向下调整算法更好。堆排序堆排序的时间复杂度是 O(n log n)无论最好、最坏还是平均情况都是如此。这个复杂度由两部分组成1. 建堆使用向下调整的 Floyd 方法只需 O(n) 时间。从最后一个非叶子节点开始调整每个节点的调整代价与其高度成正比整体加起来是线性复杂度。2. 排序需要执行 n 次 删除堆顶操作。每次删除后都要从根向下调整调整代价为 O(log n)所以这部分的复杂度是 O(n log n)。总时间复杂度 O(n) O(n log n) O(n log n)。空间复杂度为 O(1)是原地排序但不稳定。另外如果你的建堆方式是逐个插入向上调整建堆本身就会是 O(n log n)但总复杂度依然是 O(n log n)不过实际效率不如 Floyd 方法。void HeapSort(HPDataType* a, int n) { //降序 建小堆 //升序 建大堆 //for (int i 1; i n; i) //{ // AdjustUp(a, i); //} for (int i (n-1-1)/2; i 0; i--) { AdjustDown(a, n, i); } int end n - 1; while (end0) { Swap(a[0], a[end]); AdjustDown(a, end, 0); --end; } }topk问题在现实生活中经常会有在一堆数据中找最小或最大的前K个比如找出全球最富有的前十个人有时这些数据很少用堆排序即可实现但是当数据量很大占据的内存很多时该怎么解决假设求100000个数字中最大的前K个1.建一个只有K个数的小堆2.将剩下的n-k个数与堆顶比较如果大于堆顶则将两个数交换再向下调整void CreatNode() { int n 100000; srand((unsigned)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) % 10000000000; fprintf(fin, %d\n, x); } fclose(fin); } void test_3() { int k 0; printf(请输入要找的前个数); scanf_s(%d, k); int* kmaxheap (int*)malloc(sizeof(int) * k); if (kmaxheap NULL) { perror(malloc fail); return; } const char* file data.txt; FILE* fout fopen(file, r); if (fout NULL) { perror(fopen error); return; } //读取文件中前k个树 for (int i 0; i k; i) { fscanf_s(fout, %d, kmaxheap[i]); } //建堆 for (int i (k - 1 - 1) / 2; i 0; i--) { AdjustDown(kmaxheap, k, i); } //遍历剩下的n-k个数 int x 0; while (fscanf_s(fout, %d, x) 0) { if (x kmaxheap[0]) { kmaxheap[0] x; AdjustDown(kmaxheap, k, 0); } } printf(最大的前%d个数, k); for (int i 0; i k; i) { printf(%d , kmaxheap[i]); } printf(\n); } int main() { //test_1(); //test_2(); //CreatNode(); test_3(); return 0; }该算法的时间复杂度为O(n) (N-K)logN