赞
踩
树是一种非线性
的数据结构,它是由有限个节点组成的一个具有层次关系的集合。
如上图就是一颗树,下面介绍树相关的一些基本概念。
树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,实际中树有很多种表示方式,如:双亲表示法,孩子表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};
这种表示树的方法,只能由父亲节点找到下一层的第一个子节点,由该子节点找到它的兄弟节点,也就是父亲节点的其他子节点。
一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
顾名思义,二叉树是一种特殊的树,它的特点如下:
如下图就是一颗标准的二叉树。
二叉树还有两种特殊的结构——完全二叉树和满二叉树
:
顺序结构存储就是使用数组来存储。
普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。
而完全二叉树更适合使用顺序结构存储。
现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是操作系统中管理内存的一块区域分段。
下面就介绍一下堆的相关概念和应用。
如果有一个集合 K = {k0,k1, k2,…,kn-1} ,
把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,
并满足:ki <= k2i+1 且 ki <= k2i+2 (或 ki >= k2i+1 且 ki >= k2i+2) 其中 i = 0,1,2…,
则称为其为小堆(或大堆)。
将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
可见,堆总是一棵完全二叉树,堆中某个节点的值总是不大于或不小于其父节点的值。
首先先创建一个结构表示堆:
typedef int HPDataType;
struct HP {
HPDataType* a;
int size; //记录当前元素个数
int capacity;//记录堆的容量
}
现在我们给出一个数组,逻辑上看做一颗完全二叉树。
int a[] = {27,15,19,18,28,34,65,49,25,37};
此时它的左子树和右子树都是小堆,
那么接下来如何将它处理为一个小堆呢?
对其做如下变换:
从根节点开始,
每次跟子节点中较小的那个交换,
直至子节点都比自己大或调到最后,
调整完成就得到了一个标准的小堆。
如是的调整方法称为根的向下调整算法。
其代码实现如下:
void Swap(HPDataType* a, HPDataType* b) { HPDataType tmp = *a; *a = *b; *b = tmp; } void AdjustDown(HPDataType* a, int sz, int parent) { int child = parent * 2 + 1; while (child < sz) { if (child + 1 < sz && a[child + 1] > a[child])//1 ++child; if (a[child] > a[parent])//2 { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else break; } }
上面代码后调整得到的是大堆,如果想调小堆只需要改一下 1 和 2 处的逻辑判断符号。
注意:以要调整的节点为根节点,当根节点的左右子树都是大堆(或小堆)时,向下调整算法才有用。
假设一共有 n 个节点,
则树最多有 log2n 层,
向下调整算法中的循环最多执行 log2n 次,
所以向下调整算法的时间复杂度是
O(logN)
。
下面我们给出一个数组,这个数组逻辑上可以看做一颗完全二叉树,但是还不是一个堆。
int a[] = {1,5,3,8,7,6};
现在我们通过算法,把它构建成一个大堆。
以上图为例。
- 首先从第一个非叶子节点开始执行向下调整算法,这里的第一个非叶子节点是 E ,以它为根节点执行向下调整算法,调整后 E-J 就是一个大堆
- 依次向前遍历,接下来对 D 进行向下调整,调整后 D-H/I 就是一个大堆
- 对 C 进行向下调整,调整后 C-F/G 就是一个大堆
- 对 B 进行调整,此前它的两个子树都已调成大堆,所以调整后 B-D/E-H/I/J 就是一个大堆
- 对 A 进行调整,此前它的两个子树都已调成大堆,所以调整后大堆就建好了。
建堆的实现代码如下:
//将给定的数组转移到堆里来,并调整为大堆 void HeapInit(HP* php, HPDataType* a, int n) { //创建堆并导入数据 assert(php); php->a = (HPDataType*)malloc(sizeof(HPDataType) * n); if (php->a == NULL) exit(-1); memcpy(php->a, a, sizeof(HPDataType) * n); php->capacity = n; php->sz = n; //建大堆 for (int i = (php->sz - 1 - 1) / 2; i >= 0; --i) { AdjustDown(php->a, php->sz, i); } }
以上图为例来讨论建堆的时间复杂度。
假设树高为 k(k = 5),
从第四层最后一个非叶子节点开始调整,
第四层每个节点最多需要调整 1 次,有 24-1 个节点,
第三层每个节点最多需要调整 2 次,有 23-1 个节点,
第二层每个节点最多需要调整 3 次,有 22-1 个节点,
第一层每个节点最多需要调整 4 次,有 21-1 个节点,
抽象出来,第 i 层最多需要调整 k - i 次,有 2i-1 个节点,
所以第 i 层的调整次数 Si = 2i-1 × (k - i),
所以总调整次数 S = S1 + S2 + … + Sk-1,
其中 k = log2n,
利用错位相减法求得 S = n - log2n - 1。
所以建堆的时间复杂度为
O(n)
假设现在有一个大堆,想往堆里插入一个数据:
首先将数据放到堆尾,也就是数组末尾,
然后对该数据进行向上调整,
与向下调整相反,
每次拿该节点与父亲节点比较交换,
直至调整完成。
代码如下:
//沿着路径向上调整 static void AdjustUp(HPDataType* a, int child) { int parent = (child - 1) / 2; while (child > 0) { if (a[parent] < a[child]) { Swap(&a[parent], &a[child]); child = parent; parent = (child - 1) / 2; } else return; } } //插入 void HeapPush(HP* php, HPDataType x) { assert(php); if (php->sz == php->capacity) { HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2); if (tmp == NULL) exit(-1); php->a = tmp; php->capacity *= 2; } php->a[php->sz] = x; ++php->sz; AdjustUp(php->a, php->sz-1); }
由于向上调整次数最多为层数,
所以插入的时间复杂度为 O(logn) 。
堆的删除是删除堆顶的数据。
先将堆顶的数据与最后一个数据进行交换,
然后删除最后一个数据,
再重新进行向下调整。
代码如下:
void HeapPop(HP* php)
{
assert(php);
assert(php->sz > 0);
Swap(&php->a[0], &php->a[php->sz - 1]);
--php->sz;
AdjustDown(php->a, php->sz, 0);
}
显然时间复杂度是 O(n)
堆排序是一种极为优秀的排序算法。
其思想如下:
现在想对一组数据进行升序排序,
首先对这组数据建大堆 (排降序就建小堆),
此时堆顶的数据就是数组中最大的元素,
将堆顶最大的数据与数组末尾的数据进行交换,
然后除去已经排好的数据,
对剩余数据重复上述过程。
代码如下:
void Swap(int* x, int* y) { int tmp = *x; *x = *y; *y = tmp; } //向下调整算法 void AdjustDown(int* arr, int n, int parent) { int child = parent * 2 + 1; while (child < n) { //大于号为大堆,小于号为小堆 if (child < n - 1 && arr[child + 1] > arr[child]) ++child; if (arr[child] > arr[parent]) { Swap(&arr[parent], &arr[child]); parent = child; child = parent * 2 + 1; } else break; } } //降序每次要把最小的调到堆顶,所以要建小堆 //升序每次要把最大的调到堆顶,所以要建大堆 void HeapSort(int* arr, int sz) { for (int i = (sz - 1 - 1) / 2; i >= 0; i--) AdjustDown(arr, sz, i); int end = sz - 1; while (end) { Swap(&arr[end], &arr[0]); AdjustDown(arr, end, 0); --end; } }
时间复杂度为 O(nlogn)
TopK 问题是指在含 N 个数的无序序列中找出其中最大的 K 个数。
很容易,因为我们只需要对这 N 个数进行降序排序,排序后的前 K 个数就是最大的 K 个数。
但是,尽管有多种优秀的排序算法供我们使用,但当 N 特别大,大到内存无法一次性容纳这 N 个数,此时简单的排序就不那么可靠。
一种解决方案是将 N 个数据平均分为若干份,分别对每份数据进行排序,然后排序好的若干组进行归并排序,此时得到的 N 个数据就是有序的。显然这种解决方案开销非常大。
另一种解决方案是,先取出其中的 K 个元素,将这 K 个数建成小堆,那么堆顶的数就是这 K 个数中最小的数。然后将剩下的 N - K 个数依次与堆顶的数进行比较,如果比堆顶的数小,那绝不可能是最大的前 K 个数;如果比堆顶的数大,那么该数就有可能是 K 个数之一,这时就替换掉堆顶的数据,此时堆就破坏了,所以还需要重新建堆。遍历结束,堆中的 K 个数就是 TopK 。
代码如下:
void TopK(int* arr, int sz, int k) { //建小堆 int* topK = (int*)malloc(sizeof(int) * k); memcpy(topK, arr, sizeof(int) * k); for (int i = (k - 1 - 1) / 2; i >= 0; --i) AdjustDown(topK, k, i); for (int i = k; i < sz; ++i) { if (topK[0] < arr[i]) { topK[0] = arr[i]; AdjustDown(topK, k, 0); } } for (int i = 0; i < k; ++i) printf("%d ", topK[i]); free(topK); }
时间复杂度为 O(NlogK)
空间复杂度为 O(K)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。