二叉树-堆的详解
一，树的概念1，树的概念
树是一种非线性的数据布局，它是由n（n>=0）个有限结点组成一个具有条理关系的集合。
把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
有一个特殊的结点，称为根结点，根结点没有前驱结点
除根结点外，别的结点被分成M(M>0)个互不相交的集合
T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵布局与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
因此，树是递归定义的
https://img-blog.csdnimg.cn/direct/d0f953af6a9841d9806076b26158db0a.png
注意：树形布局中，子树之间不能有交集，否则就不是树形布局
2，树的相关概念
https://img-blog.csdnimg.cn/direct/cc3b41ba4a244079b7e440ab9c1281f9.png
3，二叉树的概念
一棵二叉树是结点的一个有限集合，该集合:
1. 或者为空
2. 由一个根结点加上两棵别称为左子树和右子树的二叉树组成
https://img-blog.csdnimg.cn/direct/ef9dbc59ebec4e2a8af15c0f2ce3d685.png
1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，序次不能颠倒，因此二叉树是有序树
注意：对于任意的二叉树都是由以下几种情况复合而成的：
https://img-blog.csdnimg.cn/direct/63263715a9bb485ab1289d97a78151a7.png
特殊的二叉树：
1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是 说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
2. 完全二叉树：完全二叉树是服从很高的数据布局，完全二叉树是由满二叉树而引出来的。对于深度为K 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
https://img-blog.csdnimg.cn/direct/f2e3a8a4c31b47fe8c70f5e7d29ceb77.png
节点与高度关系
设高度为h，节点个数为N
https://img-blog.csdnimg.cn/direct/8e76c31818b14594a4372e6b3c8ee4a6.png
4,堆的概念
如果有一个关键码的集合K = { ， ， ，…， }，把它的全部元素按完全二叉树的序次存储方式存储 在一个一维数组中，并满足： = 且 >= ) i = 0，1， 2…，则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。
物理：数组
逻辑：完全二叉树
堆的性子
堆中某个结点的值总是不大于或不小于其父结点的值；
堆总是一棵完全二叉树。
https://img-blog.csdnimg.cn/direct/158796586ce042b6a4609319dbc7ebfa.png
二，堆的实现
老规矩建立三个文件 Heap.c Heap.h Test.c
1，堆的布局
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP; 2，堆的初始化
void HPInit(HP* php);
void HPInit(HP* php)
{
assert(php);
php->a = NULL;
php->capacity = php->size = 0;
} 3，堆的销毁
void HPDestroy(HP* php);
void HPDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
} 4，数据的交换
void Swap(HPDataType* p1, HPDataType* p2);
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
} 5，向上调整（小堆为例）
void AdjustUp(HPDataType* a, int child);
void AdjustUp(HPDataType* a, int child)
{
// 初始条件
// 中间过程
// 结束条件
int parent = (child - 1) / 2;
//while (parent >= 0)
while (child > 0)
{
if (a < a)
{
Swap(&a, &a);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
} 条件while (parent >= 0) 不正确，由于child==0时，parent = (child - 1) / 2;是整型还是为0，故可以实现
6，堆的插入
void HPPush(HP* php, HPDataType x);
判断空间是否足够
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 = x;
php->size++; 调整数据
AdjustUp(php->a, php->size - 1); 总代码
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 = x;
php->size++; AdjustUp(php->a, php->size - 1);}
https://img-blog.csdnimg.cn/direct/a59d1cdd45f24ee09dbdb019c7f73882.png
7，堆的删除（删除堆顶）
挪动覆盖删除堆顶数据，会导致堆的关系错误
可以将堆顶数据和堆尾数据互换，这样其两个左右子树还是小堆，然后使用向下调节算法
https://img-blog.csdnimg.cn/direct/d264f64511f0426299ab0cbf629f0c00.png
void HPPop(HP* php);
void HPPop(HP* php)
{
assert(php);
assert(php->size > 0);
Swap(&php->a, &php->a);
php->size--;
AdjustDown(php->a, php->size, 0);
} 8，向下调整（小堆为例）
void AdjustDown(HPDataType* a, int n, int parent);
void AdjustDown(HPDataType* a, int n, int parent)
{
// 先假设左孩子小
int child = parent * 2 + 1;
while (child < n)// child >= n说明孩子不存在，调整到叶子了
{
// 找出小的那个孩子
if (child + 1 < n && a < a)
{
++child;
}
if (a < a)
{
Swap(&a, &a);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
} 9，取堆顶数据
HPDataType HPTop(HP* php);
HPDataType HPTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a;
} 10，判断堆是否为空
bool HPEmpty(HP* php);
bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
} 三，堆的应用
使用堆排序
向上调整建堆
for (int i = 1; i < n; i++)
{
AdjustUp(a, i);
} 向下调整建堆
for (int i = (n-1-1)/2; i >= 0; i--)
{
AdjustDown(a, n, i);
} 完备代码
void HeapSort(int* 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 (end > 0) { Swap(&a, &a); AdjustDown(a, end, 0); --end; }}
不可以用大堆进行降序，因为首先第一个定死了，后面接着用大堆会使关系庞杂
建堆时间复杂度
向下调整
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度原来看的 就是近似值，多几个结点不影响终极效果)：
https://img-blog.csdnimg.cn/direct/262ae2f08d81423597c61600d22f68f3.png
https://img-blog.csdnimg.cn/direct/98fc8cc7375a4e9fa8b272c0fd41fd20.png
向下调整建堆 O(N)
向上调整
https://img-blog.csdnimg.cn/direct/8f9cd04966324c6ba19a5144a7456077.png
向上调整建堆O(N*logN)
n个数找最大的前K个
方法一
建一个N个数的大堆 O(N)
pop k次 O(K*logN)
方法二
用前k个数 建一个小堆 O(K)
剩下的数跟堆顶数据比较，如果比堆顶数据大，就替换堆顶数据进堆（覆盖跟位置然后向下调整）
O(log K*(N-K))
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]