PHP网站开发简单实例,微娱网络小程序代理,周浦网站建设公司,wordpress心得体会文章目录 1.树的概念1.1树的相关概念1.2树的表示 2.二叉树2.1概念2.2特殊二叉树2.3二叉树的存储 3.堆3.1堆的插入#xff08;向上调整#xff09;3.2堆的删除#xff08;向下调整#xff09;3.3堆的创建3.3.1使用向上调整3.3.2使用向下调整3.3.3两种建堆方式的比较 3.4堆排… 文章目录 1.树的概念1.1树的相关概念1.2树的表示 2.二叉树2.1概念2.2特殊二叉树2.3二叉树的存储 3.堆3.1堆的插入向上调整3.2堆的删除向下调整3.3堆的创建3.3.1使用向上调整3.3.2使用向下调整3.3.3两种建堆方式的比较 3.4堆排序3.5TopK问题 1.树的概念
树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。如下图 有一个特殊的结点称为根结点根节点没有前驱结点。例如A节点
除根节点外其余结点被分成M(M0)个互不相交的集合T1、T2、……、Tm其中每一个集合Ti(1 i m)又是一棵结构与树类似的子树。 例如B节点又可以分成一棵树该树只有根没有子树。 D节点可以分为根节点和子树。D为根节点只有一棵子树H。
因此树可以拆分为根和子树。 每棵子树的根结点有且只有一个前驱可以有0个或多个后继所以树是递归定义的。
注意树形结构中子树之间不能有交集否则就不是树形结构即树中不能有环。例如
1.1树的相关概念
节点的度一个节点含有的子树的个数称为该节点的度 如上图A的为6叶节点或终端节点度为0的节点称为叶节点 如上图B、C、H、I…等节点为叶节点分支节点或非终端节点度不为0的节点 如上图D、E、F、G…等节点为分支节点双亲节点或父节点若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B的父节点孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 如上图B是A的孩子节点H是D的孩子节点兄弟节点具有相同父节点的节点互称为兄弟节点 如上图B、C是兄弟节点树的度一棵树中最大的节点的度称为树的度 如上图树的度为6节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推树的高度或深度树中节点的最大层次 如上图树的高度为4堂兄弟节点双亲在同一层的节点互为堂兄弟如上图H、I互为兄弟节点节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先P的祖先是A、E、J子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙森林由mm0棵互不相交的树的集合称为森林
1.2树的表示
树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了既然保存值域也要保存结点和结点之间的关系。所以树的结构应该怎么定义呢
//假设树的度为6
#define N 6
struct TreeNode
{int val;struct TreeNode* Child[N];
};如果这样定义的话不管你子树有没有孩子都开辟了空间会比较浪费。
struct TreeNode
{int val;struct TreeNode** Child;//使用顺序表存储孩子int size;//当前个数int capacity;//容量
};既然浪费了空间那咱们就动态申请有几个孩子由size决定不够就扩容但这种结构好像也不太好。
struct TreeNode
{int val;struct TreeNode* leftChile;//左孩子struct TreeNode* nextBrother;//右兄弟
};左孩子右兄弟法这种方法设计的非常巧妙每个节点只记录它左边第一个孩子其它孩子是第一个孩子的兄弟由第一个孩子记录。这种方法好像看起来是最好的
2.二叉树
2.1概念
二叉树是从树衍生出来的。 那什么叫二叉树呢 二叉树首先它是一棵树其次它每个节点最多有两个分支并且对两个分支进行区分分别叫做左子树和右子树。如下图 从上图可以看出
二叉树不存在度大于2的结点二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树
注意对于任意的二叉树都是由以下几种情况复合而成的
2.2特殊二叉树
满二叉树
满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。 满二叉树的前n-1层全是满的度为2叶子全在最后一层 如果一个二叉树的层数为K且结点总数是2k-1则这个二叉树就是满二叉树。 完全二叉树
完全二叉树跟满二叉树的区别是完全二叉树的前n-1层也都是满的最后一层不一定满但是要求从左到右的节点连续不能空。(没有左孩子就不能有右孩子) 2.3二叉树的存储
二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。
顺序存储
顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树 使用顺序存储存在一个规律 leftChild parent*21 例C的左孩子的下标为2 * 21 5 rightChild parent*22 例C的右孩子的下标为2 * 22 6 parent (Child - 1) / 2 例F的父亲下标为5-1/ 2 2 G的父亲下标为6-1/ 2 2 有了这个规律我就不需要存储我的孩子或父亲在哪里我使用下标算就可以了。
链式存储
二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别 用来给出该结点左孩子和右孩子所在的链结点的存储地址链式结构又分为二叉链和三叉链 。 该结构一般用来存储非完全二叉树不会有空间的浪费。
3.堆
普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储
堆
堆是一棵完全二叉树。小堆任何一个父亲 孩子大堆任何一个父亲 孩子将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆 使用堆这种数据结构有什么好处呢 TopK问题找最值最值就在根上。 3.1堆的插入向上调整
假设已存在一个堆现需向堆中插入元素5。
void Swap(HeapDataType* x, HeapDataType* y)
{HeapDataType tmp *x;*x *y;*y tmp;
}void AdjustUp(HeapDataType* a, int child)
{int parent (child - 1) / 2;//while(parent 0)while (child){//孩子小于父亲if (a[child] a[parent]){//交换Swap(a[child], a[parent]);//改变下标child parent;//继续找父亲parent (child - 1) / 2;}else{break;}}
}// 堆的插入
void HeapPush(Heap* php, HeapDataType x)
{assert(php);//扩容if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : 2 * php-capacity;HeapDataType* tmp (HeapDataType*)realloc(php-a, sizeof(HeapDataType)*newcapacity);if (tmp NULL){perror(realloc);return;}php-a tmp;php-capacity newcapacity;}//将数据先插入到堆中php-a[php-size] x;php-size;//插入后向上调整使其仍然是堆//开始调整的位置为数组末尾位置size-1AdjustUp(php-a, php-size - 1);
}思考如何让一个数组变成堆 将数组的值插入堆中即可 int main()
{Heap* heap HeapCreate();int arr[] { 1,4,7,3,9,10 };for (int i 0; i sizeof(arr)/sizeof(int); i){HeapPush(heap, arr[i]);}HeapDestroy(heap);return 0;
}3.2堆的删除向下调整 void AdjustDown(HeapDataType* a, int n, int parent)
{int child parent * 2 1;while (child n)//有左孩子就继续{//找小的孩子//若右孩子存在 且 右孩子小于左孩子右孩子是小孩子if (child1 n a[child1] a[child]){child;}//小孩子小于父亲交换if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}// 堆的删除
void HeapPop(Heap* php)
{assert(php);assert(php-size);Swap(php-a[0], php-a[php-size - 1]);//交换php-size--;//删除数组尾位置AdjustDown(php-a, php-size, 0);
}由于向下调整法最多调整高度次那么它的时间复杂度是O(logN)
3.3堆的创建
下面我们给出一个数组这个数组逻辑上可以看做一颗完全二叉树但是还不是一个堆现在我们通过算法把它构建成一个堆。根节点左右子树不是堆我们怎么调整呢
3.3.1使用向上调整
从数组的第二个元素开始使其按照小堆/大堆的规则调整成堆
void HeapCreat(Heap* php, HeapDataType* a, int n)
{assert(php);php-a (HeapDataType*)malloc(sizeof(HeapDataType) * n);//申请和数组同样大的空间if (php-a NULL){perror(malloc fail);return;}memcpy(php-a, a, sizeof(HeapDataType) * n);//将数组中的元素拷贝进堆php-size n;php-capacity n;//向上调整使其成堆for (int i 1; i n; i){AdjustUp(php-a, i);}
}3.3.2使用向下调整
用向下调整法我们从倒数的第一个非叶子节点的子树开始调整一直调整到根节点的树就可以调整成堆。 其实本质上就是从下往上将根的每个子树调整成堆 由于最后一个元素的下标为n-1所以它的父亲应该是(其下标-1)/2也就是(n-1-1)/2。
void HeapCreat(Heap* php, HeapDataType* a, int n)
{assert(php);php-a (HeapDataType*)malloc(sizeof(HeapDataType) * n);//申请和数组同样大的空间if (php-a NULL){perror(malloc fail);return;}memcpy(php-a, a, sizeof(HeapDataType) * n);//将数组中的元素拷贝进堆php-size n;php-capacity n;//向下调整使其成堆for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(php-a, n, i);}
}3.3.3两种建堆方式的比较
树的高度与节点个数的关系 向上调整法建堆时间复杂度的分析 因此向上调整建堆的时间复杂度为O(N*log2N)
向下调整法建堆时间复杂度的分析 因此向下调整建堆的时间复杂度为O(N)
O(N*log2N) 与O(N)看来两种方法的效率差别还是挺大的。为什么差别这么大呢
3.4堆排序
堆排序即利用堆的思想来进行排序总共分为两个步骤 建堆 升序建大堆 降序建小堆 利用堆删除思想来进行排序 首位交换 最后一个值不看做堆里面的向下调整选出次大的数据 #includestdio.h
void _Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}void _AdjustDown(int* 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;//孩子不大于父亲调整结束}}
}int main()
{int arr[] { 3,1,9,18,22,16 };int sz sizeof(arr) / sizeof(arr[0]);//向下调整建堆for (int i (sz - 1 - 1) / 2; i 0; i--){_AdjustDown(arr, sz, i);}int end sz - 1;while (end 0){_Swap(arr[0], arr[end]);//首位交换_AdjustDown(arr, end, 0);end--;}for (int i 0; i sz; i){printf(%d , arr[i]);}return 0;
}所以堆排序的时间复杂度是建堆O(N)每个节点需要调整的次数(N-1* logN 。 该排序的时间复杂度最终为N*logN
3.5TopK问题
TOP-K问题即求数据中前K个最大的元素或者最小的元素一般情况下数据量都比较大。比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下
用数据集合中前K个元素来建堆 前k个最大的元素则建小堆 前k个最小的元素则建大堆用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
void TopK(int k)
{FILE* fp fopen(data.txt, r);if (fp NULL){return;}int* heap (int*)malloc(sizeof(int) * k);if (heap NULL){perror(malloc fail);return;}//先读取k个数据for (int i 0; i k; i){fscanf(fp, %d, heap[i]);}//根据k个数据建小堆for (int i (k - 1 - 1) / 2; i 0; i--){_AdjustDown(heap, k, i);}int num 0;while (fscanf(fp, %d, num) ! EOF){//读取堆顶数据比它大就替换它进堆if (num heap[0]){heap[0] num;_AdjustDown(heap, k, 0);}}for (int i 0; i k; i){printf(%d , heap[i]);}fclose(fp);
}
