1:树的概念以及结构
1.1:树的概念
- 树是一种非线性的数据结构，它是由 n(n>=0) 个有限结点组成一个具有层次关系的集合。把它叫做树是因为看起来像一颗倒挂的树，也就是说它是根朝上，而叶朝下的。
- 除根节点外，其余结点被分成 M(M > 0) 互不相交的集合 T1、T2、.....、Tm，其中每一个集合 Ti( 1 <= i <= m) 又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱结点，可以有 0 个或多个后继节点
- 因此，树是递归定义的，一棵树可以被拆解为**一个根节点和 n 棵子树 (n >= 0)**构成
PS:树形结构中，子树之间不能有交集，否则就不是树形结构.
1.2:树的相关概念
- **节点的度:**一个节点含有的子树的个数称为该节点的度。
- **叶节点或者终端节点:**度为 0 的节点称为叶子节点 (即没有子树的节点)。
- **非终端节点或分支节点:**度不为 0 的节点即有子树的节点。
- **双亲节点或父节点:**若一个节点含有子节点，则称这个节点为其子节点的父节点。
- 孩子节点或子节点:一个节点含有的子树的根结点称为该结点的子节点。
- 兄弟节点:具有相同父节点的节点互称为兄弟节点。
- 树的度:棵树中，最大的节点的度称为树的度。
- 节点的层次:从根开始定义起，根为第一层,根的第二层为子节点，以此类推.
- 树的高度与深度:树中节点的最大层次。
- 堂兄弟节点:双亲在同一层的节点互为堂兄弟。
- 节点的祖先:从根到该节点所经分支上的所有节点。
- 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。
- 森林:由 m(m > 0) 棵互不相交的树的集合称为森林.
1.3:树的表示
树结构相对线性表比较复杂，要存储表示起来比较麻烦，既要保存值域，也要保存结点和结点之前的关系,实际中树有很多种表示方式如:双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。
1.3.1:左孩子右兄弟表示法
typedef int DataType;
struct Node {
//第一个孩子结点
struct Node * leftchild;
//指向其下一个兄弟结点
struct Node * rightbrother;
//结点中的数据域
DataType _data;
}
2:二叉树的概念以及结构
2.1:概念
- 一棵二叉树是结点的一个有限集合，该集合：1:要么为空，2.由一个根节点加上两棵别称为左子树和右子树的二叉树组成.
- 二叉树不存在度大于 2 的结点**(最大度为 2)**
- 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。
PS:**二叉树不等价于度为 2 的树.**度为 2 的一定是二叉树.
注意：对于任意的二叉树都是由以下几种情况复合而成的:
2.2:特殊的二叉树
- 满二叉树:一个二叉树，如果每一个层的节点数都达到最大值 (即结点数为 2),则该二叉树为满二叉树。也就是说，如果一个二叉树的层数为 K，且节点的总数为**2^k - 1,**则它就是满二叉树。(每一层都是满的)
- 完全二叉树:完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。(前 K-1 层是满的，最后一层不一定满，但是从左向右必须连续)
2.3:二叉树的性质
- 若规定根节点的层数为 1，则一棵非空二叉树的**第 i 层上最多有 2^(i-1)**个结点.
- 若规定根节点的层数为 1，则深度为 h 的二叉树的最大节点数为 2^h - 1**(满二叉树).**
- 若规定根节点的层数为 1，具有n 个结点的满二叉树的深度，h= log2(n + 1)(ps：是 log 以 2 为底，n+1 为对数).
- 完全二叉树度为 1 的节点个数要么是 1 要么是 0.
对任意一棵二叉树，若度为 0 其叶节点个数为 n0，度为 2 的分支结点个数为 n2，则存在 n0 = n2 + 1;(增加一个度为 2 的一定会增加一个度为 0 的)
2.4:二叉树的存储结构
二叉树一般可以使用两种结构存储，一种是顺序结构，另一种则是链式结构.
2.4.1:顺序存储
顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树 or 满二叉树,，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树.
2.4.2:链式存储
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方式是链表中每个结点由三个域组成，数值域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链节点的存储地址。链式结构又分为二叉链和三叉链.
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode {
struct BinTreeNode* _pLeft;
struct BinTreeNode* _pRight;
BTDataType _data;
}
// 三叉链
struct BinaryTreeNode {
struct BinTreeNode* _pParent;
struct BinTreeNode* _pLeft;
struct BinTreeNode* _pRight;
BTDataType _data;
};
3:二叉树的顺序结构以及实现
3.1:二叉树的顺序结构
普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结 构存储。现实中我们通常把堆 (一种二叉树) 使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
3.2:堆的概念以及结构
概念：如果有一个关键码的集合 K={k0,k1,k2,…,kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足 ki<=k2i+1 且 ki<=k2i+2（或满足 ki>=k2i+1 且 ki>=k2i+2），其中 i=0,1,2,…，则称该集合为堆。小堆：将根结点最小的堆叫做小堆 (小堆满足任意一个父亲 <= 孩子) 大堆：将根节点最大的堆叫做大堆 (大堆满足任意一个父亲 >= 孩子) 性质：堆总是一棵完全二叉树。
PS:有序数组一定是堆，但是堆不一定能有序.
3.3:堆的向下调整算法
现在我们给出一个数组，逻辑上看做一棵完全二叉树。我们通过从根节点开始的向下调整算法可以把他弄成一个小堆。
使用向下调整算法有一个前提：若想将其调整为小堆，那么根结点的左右子树必须都为小堆。若想将其调整为大堆，那么根结点的左右子树必须都为大堆。
向下调整算法的算法思想。
- 从根节点开始，选出左右孩子中的最小值。
- 让最小的孩子与父亲进行比较。 - 若孩子比父亲小，则让该孩子的与其父亲的位置进行交换。并将原来小的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止 - 若若小的孩子比父亲大，则不需处理了，调整完成，整个树已经是小堆了
void Swap(int * p1,int * p2) {
assert(p1 && p2);
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustDown(int * Minheap, int size, int parent) {
assert(Minheap);
//假设左孩子最小
int child = parent * 2 + 1;
while (child < size) {
//与右孩子进行比较
if ((child + 1 < size) && (Minheap[child] > Minheap[child + 1])) {
child++;
}
////左右孩子中较小孩子的值比父结点还小
if (Minheap[child] < Minheap[parent]) {
//进行交换
Swap(&Minheap[child], &Minheap[parent]);
//更新孩子和父亲，继续进行向下调整
parent = child;
child = child * 2 + 1;
}
//已成堆
else {
break;
}
}
}
使用堆的向下调整算法，最坏的情况下 (即需要一直交换节点)，需要循环的次数则为 h - 1 次 (h 为树的高度)。而 h = log2(N+1)(N 为树的总结点数)。那么向下调整算法的时间复杂度为：O(logN).
3.4:向下调整算法进行建堆
在上面有提到使用堆的向下调整算法需要满足其根结点的左右子树均为大堆或是小堆才行，那么如何才能将一个任意树调整为堆呢？其实很简单，我们只需要从倒数第一个非叶子节点开始，从后往前，按下标，依次作为根去进行向下调整即可.
//从倒数第一个非叶子节点进行向下调整即最后一个叶子节点的父亲
//时间复杂度为 O(N)
for (int i = (size - 1 - 1) / 2; i >= 0; i--) {
AdjustDown(pile->arr, i, size);
}
3.4.1:建堆的时间复杂度
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明 (时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
因此：建堆的时间复杂度为 O(N).
总结一下： 堆的向下调整算法的时间复杂度：T(n)=O(logN)。 建堆的时间复杂度：T(n)=O(N)。
3.5:向上调整算法
当我们在一个堆的末尾插入一个数据后，需要对堆进行调整，使其仍然是一个堆，这时需要用到堆的向上调整算法.
向上调整算法的基本思想 (以小堆为例)
- 将目标节点与其父节点进行比较。
- 若目标节点的值比父节点小，则进行交换，并且同时将原目标节点的父亲节点当作新的目标节点进行向上调整，若目标结点的值比其父结点的值大，则停止向上调整，此时该树已经是小堆了.
void Swap(int * p1,int * p2) {
assert(p1 && p2);
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustUp(int * arr,int child) {
assert(arr);
//找父亲
int parent = (child - 1) / 2;
//调整到根节点的位置就可以停止
while (child > 0) {
//孩子与父亲进行比较
if(arr[child] < arr[parent]) {
//进行交换
Swap(&arr[child], &arr[parent]);
//原目标节点的父节点当作新的目标节点。
child = parent;
//寻找新的目标节点的父节点。
parent = (parent - 1) / 2;
}
//已经成堆
else {
break;
}
}
}
3.6:堆的代码实现
3.6.1:Heap.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
//堆在物理结构是顺序表，在逻辑结构上是一棵完全二叉树
typedef int HPDataType;
typedef struct Heap {
HPDataType* arr;
int size;
int capcity;
}Heap;
//针对小堆
//初始化堆
void HeapInit(Heap* pile);
//建立堆
void HeapCreate(Heap* hp, HPDataType * arr, int n);
//销毁堆
void HeapDestory(Heap* pile);
//插入
void HeadPush(Heap* pile,HPDataType value);
//向上调整
void AdjustUp(HPDataType* arr,int child);
//向下调整
void AdjustDown(HPDataType* arr, int parent, int size);
//获取堆顶元素
HPDataType HeadTop(Heap* pile);
//规定删除根节点
void HeapPop(Heap * pile);
//获取堆的元素个数
int HeapSize(Heap* pile);
//堆是否为空
bool HeapEmpty(Heap* pile);
3.6.2:Heap.c
3.6.2.1:初始化堆与建堆
#include "Heap.h"
void Swap(int* p1, int* p2) {
assert(p1 && p2);
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向下调整
void AdjustDown(HPDataType* arr, int parent, int size) {
assert(arr);
//假设左孩子为最小值
int child = parent * 2 + 1;
while (child < size) {
//防止越界访问堆并将左孩子与右孩子进行比较
if (child + 1 < size && arr[child + 1] < arr[child]) child++;
//孩子比父亲小
if (arr[child] < arr[parent]) {
//进行交换
Swap(&arr[child], &arr[parent]);
//将原目标节点的父节点当作新的父节点
parent = child;
//寻找新的父节点的左孩子节点
child = parent * 2 + 1;
}
else break;
}
}
//初始化堆
void HeapInit(Heap* pile) {
assert(pile);
pile->arr = NULL;
pile->capcity = 0;
}
//建立堆
void HeapCreate(Heap* pile, HPDataType* arr, int size) {
assert(pile && arr);
HPDataType* Tmp = (HPDataType*)malloc(sizeof(HPDataType) * size);
if (Tmp == NULL) {
perror("malloc fail");
return ;
}
pile->arr = Tmp;
pile->capcity = pile->size = size;
//拷贝数据，第一个参数为 destination，第二个参数为 source，第三个参数为拷贝的字节数
memcpy(pile->arr, arr, sizeof(HPDataType) * size);
//从倒数第一个非叶子节点开始进行向下调整
for (int i = (size - 1 - 1) / 2; i >= 0 ; i--) {
AdjustDown(pile->arr, i, size);
}
}
3.6.2.2:堆的插入
数据插入时是插入到数组的末尾，即树形结构的最后一层的最后一个结点，所以插入数据后我们需要运用堆的向上调整算法对堆进行调整，使其在插入数据后仍然保持堆的结构。
#include "Heap.h"
void Swap(int* p1, int* p2) {
assert(p1 && p2);
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向上调整
void AdjustUp(HPDataType* arr, int child) {
assert(arr);
//找父亲
int parent = (child - 1) / 2;
while( child > 0) {
//孩子比父亲小，则进行交换
if (arr[child] < arr[parent]) {
Swap(&arr[child], &arr[parent]);
//原目标节点的父节点当作新的目标节点
child = parent;
//寻找新的目标节点的父节点
parent = (child - 1) / 2;
}
//调整完成，已成堆
else {
break;
}
}
}
//插入
void HeadPush(Heap* pile, HPDataType value) {
//插入之前先检查容量
if (pile->capcity == pile->size) {
int newcapacity = pile->capcity == 0 ? 4 : pile->capcity * 2;
//进行扩容
HPDataType* Tmp = (HPDataType*)realloc(pile->arr, newcapacity * sizeof(HPDataType));
if (Tmp == NULL) {
perror("malloc fail");
return;
}
pile->arr = Tmp;
pile->capcity = newcapacity;
//插入数据
pile->arr[pile->size] = value;
//进行向上调整
AdjustUp(pile->arr, pile->size);
pile->size++;
}
}
3.6.2.3:堆的删除
- 堆的删除，删除的是堆顶的元素，但是这个删除过程可并不是直接删除堆顶的数据，而是先将堆顶的数据与最后一个结点的位置交换，然后再删除最后一个结点，再对堆进行一次向下调整.
- 若是直接删除堆顶的数据，那么原堆后面数据的父子关系就全部打乱了，需要全体重新建堆，时间复杂度为 O(N)。若是用上述方法，那么只需要对堆进行一次向下调整即可，因为此时根结点的左右子树都是小堆，我们只需要在根结点处进行一次向下调整即可，时间复杂度为 O(log(N))
#include "Heap.h"
void Swap(int* p1, int* p2) {
assert(p1 && p2);
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向下调整
void AdjustDown(HPDataType* arr, int parent, int size) {
assert(arr);
//假设左孩子为最小值
int child = parent * 2 + 1;
while (child < size) {
//防止越界访问堆并将左孩子与右孩子进行比较
if (child + 1 < size && arr[child + 1] < arr[child]) child++;
//孩子比父亲小
if (arr[child] < arr[parent]) {
//进行交换
Swap(&arr[child], &arr[parent]);
//将原目标节点的父节点当作新的父节点
parent = child;
//寻找新的父节点的左孩子节点
child = parent * 2 + 1;
}
else break;
}
}
//规定删除根节点
void HeapPop(Heap* pile) {
assert(pile);
//首尾交换
Swap(&pile->arr[0], &pile->arr[pile->size - 1]);
pile->size--;
//进行向下调整
AdjustDown(pile->arr, 0, pile->size);
}
3.6.2.4:获取堆顶元素与堆的元素个数与判断堆是否为空以及销毁堆
//获取堆顶元素
HPDataType HeadTop(Heap* pile) {
return pile->arr[0];
}
//获取堆的元素个数
int HeapSize(Heap* pile) {
return pile->size;
}
//堆是否为空
bool HeapEmpty(Heap* pile) {
return pile->size == 0 ? true : false;
}
//销毁堆
void HeapDestory(Heap* pile) {
free(pile->arr);
pile->arr = NULL;
pile->capcity = 0;
pile->size = 0;
}
3.6.3:Test.c
3.6.3.1:测试初始化堆与建堆
#include "Heap.h"
void TestInitAndCreate(Heap * hp,int * arr,int size) {
HeapInit(hp);
HeapCreate(hp, arr, size);
for (size_t i = 0; i < size; i++) {
printf("%d ", hp->arr[i]);
}
}
int main() {
Heap hp;
int arr[] = { 23,54,76,33,89,12,78,34,87,10 };
int size = sizeof(arr) / sizeof(arr[0]);
TestInitAndCreate(&hp,arr,size);
return 0;
}
3.6.3.2:测试插入
#include "Heap.h"
void TestPush(Heap* hp, int* arr, int size) {
HeapInit(hp);
HeapCreate(hp, arr, size);
HeadPush(hp, 22);
HeadPush(hp, 54);
for (size_t i = 0; i < hp->size; i++) {
printf("%d ", hp->arr[i]);
}
}
int main() {
Heap hp;
int arr[] = { 23,54,76,33,89,12,78,34,87,10 };
int size = sizeof(arr) / sizeof(arr[0]);
TestPush(&hp, arr, size);
return 0;
}
3.6.3.3:测试删除
#include "Heap.h"
void TestPop(Heap* hp, int* arr, int size) {
HeapInit(hp);
HeapCreate(hp, arr, size);
HeadPush(hp, 22);
HeadPush(hp, 54);
for (size_t i = 0; i < hp->size; i++) {
printf("%d ", hp->arr[i]);
}
printf("\n");
HeapPop(hp);
for (size_t i = 0; i < hp->size; i++) {
printf("%d ", hp->arr[i]);
}
}
int main() {
Heap hp;
int arr[] = { 23,54,76,33,89,12,78,34,87,10 };
int size = sizeof(arr) / sizeof(arr[0]);
TestPop(&hp, arr, size);
return 0;
}
3.6.3.4:测试获取堆顶元素与堆的元素个数与判断堆是否为空以及销毁堆
#include "Heap.h"
void TestOther(Heap* hp, int* arr, int size) {
HeapInit(hp);
HeapCreate(hp, arr, size);
HeadPush(hp, 22);
HeadPush(hp, 54);
for (size_t i = 0; i < hp->size; i++) {
printf("%d ", hp->arr[i]);
}
printf("\n");
printf("堆顶元素为:>%d，堆的元素个数为:%d，堆是否为空:%d\n", HeadTop(hp), HeapSize(hp), HeapEmpty(hp));
HeapDestory(hp);
}
int main() {
Heap hp;
int arr[] = { 23,54,76,33,89,12,78,34,87,10 };
int size = sizeof(arr) / sizeof(arr[0]);
TestOther(&hp, arr, size);
return 0;
}
3.7:堆的总代码
3.7.1:Heap.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
//堆在物理结构是顺序表，在逻辑结构上是一棵完全二叉树
typedef int HPDataType;
typedef struct Heap {
HPDataType* arr;
int size;
int capcity;
}Heap;
//针对小堆
//初始化堆
void HeapInit(Heap* pile);
//建立堆
void HeapCreate(Heap* hp, HPDataType * arr, int size);
//插入
void HeadPush(Heap* pile,HPDataType value);
//向上调整
void AdjustUp(HPDataType* arr,int child);
//向下调整
void AdjustDown(HPDataType* arr, int parent, int size);
//规定删除根节点
void HeapPop(Heap* pile);
//获取堆顶元素
HPDataType HeadTop(Heap* pile);
//获取堆的元素个数
int HeapSize(Heap* pile);
//堆是否为空
bool HeapEmpty(Heap* pile);
//销毁堆
void HeapDestory(Heap* pile);
3.7.2:Heap.c
#include "Heap.h"
void Swap(int* p1, int* p2) {
assert(p1 && p2);
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向下调整
void AdjustDown(HPDataType* arr, int parent, int size) {
assert(arr);
//假设左孩子为最小值
int child = parent * 2 + 1;
while (child < size) {
//防止越界访问堆并将左孩子与右孩子进行比较
if (child + 1 < size && arr[child + 1] < arr[child]) child++;
//孩子比父亲小
if (arr[child] < arr[parent]) {
//进行交换
Swap(&arr[child], &arr[parent]);
//将原目标节点的父节点当作新的父节点
parent = child;
//寻找新的父节点的左孩子节点
child = parent * 2 + 1;
}
else break;
}
}
//向上调整
void AdjustUp(HPDataType* arr, int child) {
assert(arr);
//找父亲
int parent = (child - 1) / 2;
while( child > 0) {
//孩子比父亲小，则进行交换
if (arr[child] < arr[parent]) {
Swap(&arr[child], &arr[parent]);
//原目标节点的父节点当作新的目标节点
child = parent;
//寻找新的目标节点的父节点
parent = (child - 1) / 2;
}
//调整完成，已成堆
else {
break;
}
}
}
//插入
void HeadPush(Heap* pile, HPDataType value) {
//插入之前先检查容量
if (pile->capcity == pile->size) {
int newcapacity = pile->capcity == 0 ? 4 : pile->capcity * 2;
//进行扩容
HPDataType* Tmp = (HPDataType*)realloc(pile->arr, newcapacity * sizeof(HPDataType));
if (Tmp == NULL) {
perror("malloc fail");
return;
}
pile->arr = Tmp;
pile->capcity = newcapacity;
//插入数据
pile->arr[pile->size] = value;
//进行向上调整
AdjustUp(pile->arr, pile->size);
pile->size++;
}
}
//规定删除根节点
void HeapPop(Heap* pile) {
assert(pile);
//首尾交换
Swap(&pile->arr[0], &pile->arr[pile->size - 1]);
pile->size--;
//进行向下调整
AdjustDown(pile->arr, 0, pile->size);
}
//初始化堆
void HeapInit(Heap* pile) {
assert(pile);
pile->arr = NULL;
pile->capcity = 0;
pile->size = 0;
}
//建立堆
void HeapCreate(Heap* pile, HPDataType* arr, int size) {
assert(pile && arr);
HPDataType* Tmp = (HPDataType*)malloc(sizeof(HPDataType) * size);
if (Tmp == NULL) {
perror("malloc fail");
return ;
}
pile->arr = Tmp;
pile->capcity = pile->size = size;
//拷贝数据
memcpy(pile->arr, arr, sizeof(HPDataType) * size);
//从倒数第一个非叶子节点开始进行向下调整
for (int i = (size - 1 - 1) / 2; i >= 0 ; i--) {
AdjustDown(pile->arr, i, size);
}
}
//获取堆顶元素
HPDataType HeadTop(Heap* pile) {
return pile->arr[0];
}
//获取堆的元素个数
int HeapSize(Heap* pile) {
return pile->size;
}
//堆是否为空
bool HeapEmpty(Heap* pile) {
return pile->size == 0 ? true : false;
}
//销毁堆
void HeapDestory(Heap* pile) {
free(pile->arr);
pile->arr = NULL;
pile->capcity = 0;
pile->size = 0;
}
3.7.3:Test.c
#include "Heap.h"
void TestInitAndCreate(Heap * hp,int * arr,int size) {
HeapInit(hp);
HeapCreate(hp, arr, size);
for (size_t i = 0; i < size; i++) {
printf("%d ",hp->arr[i]);
}
}
void TestPush(Heap* hp, int* arr, int size) {
HeapInit(hp);
HeapCreate(hp, arr, size);
HeadPush(hp, 22);
HeadPush(hp, 54);
for (size_t i = 0; i < hp->size; i++) {
printf("%d ", hp->arr[i]);
}
}
void TestPop(Heap* hp, int* arr, int size) {
HeapInit(hp);
HeapCreate(hp, arr, size);
HeadPush(hp, 22);
HeadPush(hp, 54);
for (size_t i = 0; i < hp->size; i++) {
printf("%d ", hp->arr[i]);
}
printf("\n");
HeapPop(hp);
for (size_t i = 0; i < hp->size; i++) {
printf("%d ", hp->arr[i]);
}
printf("\n");
HeapPop(hp);
for (size_t i = 0; i < hp->size; i++) {
printf("%d ", hp->arr[i]);
}
}
void TestOther(Heap* hp, int* arr, int size) {
HeapInit(hp);
HeapCreate(hp, arr, size);
HeadPush(hp, 22);
HeadPush(hp, 54);
for (size_t i = 0; i < hp->size; i++) {
printf("%d ", hp->arr[i]);
}
printf("\n");
printf("堆顶元素为:>%d，堆的元素个数为:%d，堆是否为空:%d\n", HeadTop(hp), HeapSize(hp), HeapEmpty(hp));
HeapDestory(hp);
}
int main() {
Heap hp;
int arr[] = { 23,54,76,33,89,12,78,34,87,10 };
int size = sizeof(arr) / sizeof(arr[0]);
TestOther(&hp, arr, size);
return 0;
}
4:TOP-K 问题
TOP-K 问题：即求数据集合中前 K 个最大的元素或最小的元素，一般情况下数据量都相对来讲比较大
比如说：专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等.
对于 TOP-K 问题，最简单的方式那就是排序，但是如果数据量非常大，排序就基本上不太可能了 (因为可能数据不能一下子全部加载到内存当中).因此最佳的方式就是使用堆来解决
1.用数据集合中的前 K 个元素来建堆
- 前 K 个最大的元素，建立小堆 (因为堆顶是最小的，方便快速知道'当前前 K 个最大数中最小的那个'是谁，这样当有更大的数来时，我们能快速替换掉最小的那一个)
- 前 K 个最小的元素，建立大堆 (因为堆顶是最大的，方便我们快速丢掉'当前最小的 K 个数中最大的那个'，为更小的数腾位置)
2.用剩下的 N-K 个元素依次与堆顶元素来比较，不满足则替换堆顶.
剩下的 N-K 个元素依次与堆顶元素比较完一个，堆中剩下的 K 个元素就是所求的前 K 个最小或者最大的元素.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
void Swap(int* e1, int* e2) {
int tmp = *e1;
*e1 = *e2;
*e2 = tmp;
}
//向上调整
void AdjustUp(int* arr, int child) {
assert(arr);
//找父亲
int parent = (child - 1) / 2;
while (child > 0) {
if (arr[child] < arr[parent]) {
Swap(&arr[child], &arr[parent]);
child = parent;
parent = (parent - 1) / 2;
}
else {
break;
}
}
}
void AdjustDown(int* Minheap, int size, int parent) {
assert(Minheap);
int child = parent * 2 + 1;
while (child < size) {
//选出次小值
if ((child + 1 < size) && (Minheap[child] > Minheap[child + 1])) {
child++;
}
if (Minheap[child] < Minheap[parent]) {
//进行交换
Swap(&Minheap[child], &Minheap[parent]);
parent = child;
child = child * 2 + 1;
}
else {
break;
}
}
}
void TopKprint() {
int k = 0;
printf("请输入要读取的最大数的个数:> ");
scanf("%d", &k);
//读取数据
FILE* pf = fopen("data.txt", "r");
if (pf == NULL) {
perror("fopen fail");
return;
}
//使用数据集合中的前 K 个元素进行建堆
int* Minheap = (int*)malloc(sizeof(int) * k);
for (int i = 0; i < k; i++) {
//输入是指磁盘空间向内存中输入数据，将读取的到的数据向数组 Minheap 输入
fscanf(pf, "%d", &Minheap[i]);
//因为是打印前 K 个最大数因此建立小堆
AdjustDown(Minheap, k,i);
}
for(int i = 0;i < k; i++) {
printf("%d ", Minheap[i]);
}
printf("\n");
int value = 0;
//读取数据，选出文件中的前 K 个最大数
while(fscanf(pf,"%d",&value) != EOF) {
if(value > Minheap[0]) {
//进行交换
Swap(&value, &Minheap[0]);
//交换了以后，子树依旧是小堆，所以进行向下调整
AdjustDown(Minheap, k, 0);
}
}
for (int i = 0; i < k; i++) {
printf("%d ", Minheap[i]);
}
printf("\n");
fclose(pf);
free(Minheap);
Minheap = NULL;
pf = NULL;
}
void CreateData() {
int n = 10000000;
/*
* 使用 rand() 函数之前需要先使用 srand() 函数给系统提供一个起始的随机种子
* 使用 time 函数返回的时间戳作为 srand() 函数起始的随机种子
* 由于时间戳为整型数据因此对其进行强制类型转换将其转换为无符号整型数据
*/
FILE* pf = fopen("data.txt", "w");
if (pf == NULL) {
perror("fopen error");
return;
}
srand((unsigned int)time(NULL));
for (int i = 0; i < n; i++) {
//产生 1w 个随机数
//生成随机数 (使用 rand() 函数用于生成随机数) 生成的范围为 0 - 32767，+i 减少重复的数字
int value = (rand() + i) % 10000000;
//输出是从内存中向文件输出数据
fprintf(pf, "%d\n", value);
}
fclose(pf);
pf = NULL;
}
int main() {
//创建数据
CreateData();
//读取前 K 个最大的数
TopKprint();
}