数据结构C语言版——二叉树的顺序存储堆的实现-创新互联
- 二叉树顺序结构实现(堆)
- 1. 堆的概念
- 2. 堆的基本操作
- 堆的向下调整算法
- 堆的创建
- 堆的向上调整算法
- 3. 堆的实现
- 堆的创建
- 向堆中插入元素
- 删除堆顶元素
- 获取堆顶元素
- 获取堆中元素个数
- 判断堆是否为空
- 堆的销毁
- 4. TopK问题
二叉树顺序结构实现(堆) 1. 堆的概念
- 堆在物理上是一个一维数组，在逻辑上是一颗完全二叉树
- 满足父亲节点小于等于孩子节点的叫做小堆或者小根堆
- 满足父亲节点大于等于孩子节点的叫做大堆或者大根堆
堆的孩子和父亲的下标关系
已知父亲(parent)的下标
- 左孩子(left)下标等于 l e f t = 2 ∗ p a r e n t + 1 left = 2*parent+1 left=2∗parent+1
- 右孩子(right)下标等于 r i g h t = 2 ∗ p a r e n t + 2 right = 2 * parent + 2 right=2∗parent+2
已知左孩子或右孩子下标(child)
- 父亲节点下标等于 p a r e n t = ( c h i l d − 1 ) / 2 parent = (child-1)/2 parent=(child−1)/2
下面这个数组逻辑上可以看作是一棵完全二叉树，通过从根节点开的向下调整算法可以把它调整成一个堆(大堆或小堆)，向下调整算法有以有一个前提：左右子树必须是一个堆，才能调整。我这里的是实现小堆的向下调整算法。
建小堆的向下调整的基本思路就是：从堆顶开始，拿自己和较小的一个孩子进行比较大小，如果小就进行交换然后把交换的位置当作父节点继续向下调整，如果两个孩子都比自己小就停止调整，否则一直调整到叶子节点。
// 向下调整(小堆)
void AdjustDown(HPDataType* arr, int n, int index)
{int parent = index;
int child = 2 * parent+1;
while (parent< n)
{ //找出两个孩子里的较小的
if (child< n && child + 1< n && arr[child] >arr[child + 1])
{ child++;
}
// 拿较小的孩子比较和父亲比价大小
if (child< n && arr[child]< arr[parent])
{ Swap(&arr[child], &arr[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{ //说明无需调整
break;
}
}
}堆的向下调整每次调整的一个节点，假设树的高度为 h h h最坏情况下调整的次数就是 h − 1 h-1 h−1，所以向下调整的时间复杂度就是树的深度 l o g 2 ( n − 1 ) log_{2}(n-1) log2(n−1)，最后得出 l o g 2 n log_{2}n log2n
堆的创建我们知道堆的向下调整算法必须满足左右子树都是一个堆，那有的时候是一个普通的数组，也就是一颗普通的完全二叉树，所以要通过建堆来让一个数组变成堆。
建堆的实现思路：从最后一个节点的父节点，也就是第一个非叶子节点的父亲开始不断向下调整，直到整课树都被调整成一个堆。
//向下调整建堆
int i = 0;
//从倒数第一个非叶子节点开始向下调整
for (i = (n - 2) / 2; i >= 0; --i)//n为数组元素个数
{AdjustDown(arr,n ,i);
}建堆的时间复杂度
我们知道时间复杂度就是计算最坏的时间复杂度，实际上就是计算一个满二叉树，这样每一棵树都会进行调整。
假设这一棵树的高度是 h h h
- 第一层的节点个数就是 2 0 2^{0} 20、第二层 2 1 2^{1} 21、第三层 2 2 2^{2} 22，第 n n n层就有 2 n − 1 2^{n-1} 2n−1个，那么最后一层就有 2 h − 1 2^{h-1} 2h−1个节点
- 每一层调整的高度：第一层 h − 1 h-1 h−1、第二层 h − 2 h-2 h−2、…、1
那么假设时间复杂度为 T n T_{n} Tn，时间复杂度就是从第一层到倒数第二层每个节点的调整次数之和
- 时间复杂度： T ( n ) = 2 0 ∗ ( h − 1 ) + 2 1 ∗ ( h − 2 ) + 2 2 ∗ ( h − 3 ) + 2 3 ∗ ( h − 4 ) + . . . + 2 h − 3 ∗ 2 + 2 h − 2 ∗ 1 T(n) = 2^{0}*(h-1)+2^{1}*(h-2)+2^{2}*(h-3)+2^{3}*(h-4)+...+2^{h-3}*2+2^{h-2}*1 T(n)=20∗(h−1)+21∗(h−2)+22∗(h−3)+23∗(h−4)+...+2h−3∗2+2h−2∗1
- 等式两边同时乘2： 2 ∗ T ( n ) = 2 1 ∗ ( h − 1 ) + 2 2 ∗ ( h − 2 ) + 2 3 ∗ ( h − 3 ) + 2 4 ∗ ( h − 4 ) + . . . + 2 h − 2 ∗ 2 + 2 h − 1 ∗ 1 2*T(n) = 2^{1}*(h-1)+2^{2}*(h-2)+2^{3}*(h-3)+2^{4}*(h-4)+...+2^{h-2}*2+2^{h-1}*1 2∗T(n)=21∗(h−1)+22∗(h−2)+23∗(h−3)+24∗(h−4)+...+2h−2∗2+2h−1∗1
- 使用错位相减法(将上面两个等式进行相减)： T ( n ) = 2 1 + 2 2 + 2 3 + 2 4 + . . . + 2 h − 2 + 2 h − 1 − h + 1 T(n) = 2^{1}+2^{2}+2^{3}+2^{4}+...+2^{h-2}+2^{h-1}-h+1 T(n)=21+22+23+24+...+2h−2+2h−1−h+1
- 错位相减后得到一个等比数列： T ( n ) = 2 0 + 2 1 + 2 2 + 2 3 + 2 4 + . . . + 2 h − 2 + 2 h − 1 − h T(n) = 2^{0}+2^{1}+2^{2}+2^{3}+2^{4}+...+2^{h-2}+2^{h-1}-h T(n)=20+21+22+23+24+...+2h−2+2h−1−h
- 通过等比数列公式$S_{n} = \frac{a_{1}(1-q^{n})}{1-q} $
- 1 − 2 ( h − 1 ) ∗ 2 1 − 2 \frac{1-2^{(h-1)}*2}{1-2} 1−21−2(h−1)∗2
- T ( n ) = 2 h − 1 − h T(n) = 2^{h}-1-h T(n)=2h−1−h；( h h h是错位相减得到的)
- 假设有 N N N个节点，于是就推出 N = 2 h − 1 N = 2^{h}-1 N=2h−1,即 h = l o g 2 ( N + 1 ) h =log_{2}(N+1) h=log2(N+1)（一棵高度为 h h h的满二叉树的节点个数等于 2 h − 1 2^{h}-1 2h−1）
- 把上面两个公式带入 T ( n ) = 2 h − 1 − h T(n) = 2^{h}-1-h T(n)=2h−1−h得出，得到 T ( n ) = N − l o g 2 ( N + 1 ) T(n) = N - log_{2}(N+1) T(n)=N−log2(N+1)
- 通多大O渐近法表示得到最后的时间复杂度 O ( N ) O(N) O(N)
所以建堆的时间复杂度就是 O ( N ) O(N) O(N)，因为当 N N N足够大时，对数的大小就根本不值得一提了。
堆的向上调整算法堆的向上调整算法是用一个堆中，当我们要在堆的末尾插入一个新元素。
将堆顶元素和最后一个元素进行交换，然后将最后一个位置的元素进行向上调整。
如果是建小堆，拿最后一个元素和父节点进行比较，如果父节点大于自己就进行交换，接着以父节点的位置继续开始向上调整，如果不小于父节点就停止向上调整(说明此时已经满足小堆的条件了)。
// 交换函数
void Swap(HPDataType* x, HPDataType* y)
{HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
// 向上调整(建小堆)
void AdjustUp(HPDataType* arr, int index)
{int child = index;
int parent = (child-1) / 2;//获取父节点下标
while (child >0)
{if (arr[parent] >arr[child])//如果节点如果大于孩子就交换
{ Swap(&arr[parent], &arr[child]);
child = parent;
parent = (child-1) / 2;
}
else
{ //说明无需调整
break;
}
}
}通过一维数组来实现一个逻辑上的完全二叉树，需要定义以下接口
堆的结构体
typedef int HPDataType;
typedef struct Heap
{HPDataType* arr;//数组
int size;//堆中元素个数
int capacity;//堆的容量
}Heap;// 交换函数
void Swap(HPDataType* x, HPDataType* y);
// 堆的创建
Heap* HeapCreate(HPDataType* arr, int n);
// 向下调整
void AdjustDown(HPDataType* arr, int n, int index);
// 向上调整
void AdjustUp(HPDataType* arr, int index);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType data);
// 堆的删除
void HeapPop(Heap* hp);
// 获取堆顶元素
HPDataType HeapTop(Heap* hp);
// 获取堆的元素个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);首先先通过malloc开辟空间
如果一个数组不是堆，在创建的时候就需要通过向下调整算法，从最后一个叶子节点的父亲开始调整，把它调整成一个小堆
// 交换函数
void Swap(HPDataType* x, HPDataType* y)
{HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
// 堆的创建
Heap* HeapCreate(HPDataType* arr, int n)
{assert(arr);
Heap* heap = (Heap*)(malloc(sizeof(Heap)));
if (heap == NULL)
{printf("malloc erro!\n");
exit(-1);
}
heap->arr = (HPDataType*)(malloc(sizeof(HPDataType) * n));
heap->size = n;
heap->capacity = n;
memcpy(heap->arr, arr, sizeof(HPDataType) * n);
//向下调整建堆
int i = 0;
//从倒数第一个非叶子节点开始向下调整
for (i = (n - 2) / 2; i >= 0; --i)
{AdjustDown(heap->arr,heap->capacity ,i);
}
return heap;
}
// 向下调整
void AdjustDown(HPDataType* arr, int n, int index)
{int parent = index;
int child = 2 * parent + 1;
while (parent< n)
{ //找出两个孩子里的较小的
if (child< n && child + 1< n && arr[child] >arr[child + 1])
{ child++;
}
// 拿较小的孩子比较和父亲比价大小
if (child< n && arr[child]< arr[parent])
{ Swap(&arr[child], &arr[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{ //说明无需调整
break;
}
}
}- 堆的插入需要判断扩容，如果堆满了就进行二倍扩容。
- 每次默认在堆的末尾插入一个元素，再拿这个元素进行向上调整
// 堆的插入
void HeapPush(Heap* hp, HPDataType data)
{assert(hp);
//扩容
if (hp->size == hp->capacity)
{// 二倍扩容
HPDataType* ptr = (HPDataType*)(realloc(hp->arr, sizeof(HPDataType)*hp->capacity * 2));
if (ptr == NULL)
{ printf("扩容失败\n %s", strerror(errno));
exit(-1);
}
hp->arr = ptr;
hp->capacity = 2 * hp->capacity;
}
hp->arr[hp->size] = data;
//向上调整
AdjustUp(hp->arr,hp->size);
hp->size++;
}删堆顶元素实现思路
- 拿堆顶元素和数组最后一个元素进行交换
- 在把堆中元素个数减一
- 再从堆顶进行向下调整
// 堆的删除
void HeapPop(Heap* hp)
{//堆中没有元素
assert(hp && hp->size != 0);
//拿堆顶元素和数组最后一个元素交换
Swap(&(hp->arr[0]), &(hp->arr[hp->size - 1]));
hp->size--;
//向下调整
AdjustDown(hp->arr, hp->size, 0);
}这个比价简单，就会返回数组 第一个元素就好
// 获取堆顶元素
HPDataType HeapTop(Heap* hp)
{assert(hp && hp->size != 0);
return hp->arr[0];
}
// 获取堆的元素个数
int HeapSize(Heap* hp)
{assert(hp);
return hp->size;
}// 堆的判空
int HeapEmpty(Heap* hp)
{assert(hp);
return hp->size == 0;
}// 堆的销毁
void HeapDestory(Heap* hp)
{assert(hp);
free(hp->arr);
hp->size = 0;
hp->capacity = 0;
hp->arr = NULL;
free(hp);
}Topk问题：给你一个组数据找出前k大的数
思路：对数组排序，取出前k个
size_t IntCmp(const void* x, const void* y)
{return *((int*)y) - *((int*)x);
}
void Test(int* arr, int n, int k)
{qsort(arr, n, sizeof(arr[0]), IntCmp);
int i = 0;
for (i = 0; i< k; i++)
{printf("%d ", arr[i]);
}
} qsort底层是通过快排实现的，而快排的时间复杂度为 n ∗ l o g 2 n n*log_{2}n n∗log2n
问题升级：能不能让时间复杂度在降低一点
此时就可以通过堆来解决这个问题
- 找前k个大的建小堆
- 找前k个小的建大堆
假设前面的找前k个大的数，建个小堆，因为小堆的堆顶一定是是一组数里最小的一个数字，如果来了一个数字比最小的数还要大，那么它肯定是要先如堆的。
于是写出代码
// 堆的创建
Heap* HeapCreate(HPDataType* arr, int n)
{assert(arr);
Heap* heap = (Heap*)(malloc(sizeof(Heap)));
if (heap == NULL)
{printf("malloc erro!\n");
exit(-1);
}
heap->arr = (HPDataType*)(malloc(sizeof(HPDataType) * n));
heap->size = n;
heap->capacity = n;
memcpy(heap->arr, arr, sizeof(HPDataType) * n);
//向下调整建堆
int i = 0;
//从倒数第一个非叶子节点开始向下调整
for (i = (n - 2) / 2; i >= 0; --i)
{AdjustDown(heap->arr,heap->capacity ,i);
}
return heap;
}
// 向下调整
void AdjustDown(HPDataType* arr, int n, int index)
{int parent = index;
int child = 2 * parent;
while (parent< n)
{ //找出两个孩子里的较小的
if (child< n && child + 1< n && arr[child] >arr[child + 1])
{ child++;
}
// 拿较小的孩子比较和父亲比价大小
if (child< n && arr[child]< arr[parent])
{ Swap(&arr[child], &arr[parent]);
parent = child;
child = 2 * parent;
}
else
{ //说明无需调整
break;
}
}
}
// 堆的删除
void HeapPop(Heap* hp)
{//堆中没有元素
assert(hp && hp->size != 0);
//拿堆顶元素和数组最后一个元素交换
Swap(&(hp->arr[0]), &(hp->arr[hp->size - 1]));
hp->size--;
//向下调整
AdjustDown(hp->arr, hp->size, 0);
}
// 获取堆顶元素
HPDataType HeapTop(Heap* hp)
{assert(hp && hp->size != 0);
return hp->arr[0];
}然后不断获取堆顶元素，不断删除堆顶元素，就能得到前K个小的数。于是 O ( n ) O(n) O(n)的时间复杂就解决了问题
问题继续升级：假设有100亿个整数，从中找出前10大的数。
此时用单纯用堆肯定行不通的，因为一个整形4个字节，那么100亿个整形就是400亿个字节，那么这就是将近40G的数据，如果单纯用堆肯定是不行的。
思路：建一个大小为10的小堆，不断往堆中插入元素，如果元素满了，就和堆顶比较，如果小就删除堆顶元素，然后再进行插入，直到遍历完整个数组。
那么此时的时间复杂度为 O ( n ) O(n) O(n)，而空间复杂度则是 O ( k ) O(k) O(k)
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享文章：数据结构C语言版——二叉树的顺序存储堆的实现-创新互联
当前URL：http://6mz.cn/article/dhppdj.html