普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结 构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统 虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是操作系统中管理内存的一块区域分段。
如果有一个关键码的集合K = { k0,k1 ,k2…,kn-1 },把它的所有元素按完全二叉树的顺序存储方式存储
在一个一维数组中,并满足:Ki<= K2i+1且 Ki<=K2i+2 ( Ki>=
K2i+1且Ki<=K2i+2) i = 0,1,
2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
简单描述:
大堆(大根堆):树中父亲都大于(等于)孩子。
小堆(小根堆):树中父亲都小于(等于)孩子。
堆的性质:
应用场景:堆排序、topk。
typedef int HPDataType;//堆中存放的数据,假设是整型
typedef struct Heap
{
HPDataType* a;//指针指向堆中存储的数据
size_t size;//堆中当前元素的数目
size_t capacity;//堆中所能存储数据的容量
}HP;
void HeapInit(HP* php)
{
assert(php);
php->capacity = php->size = 0;
php->a = NULL;
}
void HeapDestory(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
}
思路:
时间复杂度:log(N)
void Swap(HPDataType* pa, HPDataType* pb)//交换函数:交换数组中的两个元素
{
HPDataType tmp = *pa;
*pa = *pb;
*pb = tmp;
}
void AdjustUp(HPDataType* a, size_t child )//堆的向上调整
{
size_t parant = (child - 1) / 2;
while (child > 0)
{
if (a[child] < a[parant])//此处如果是<就是小堆,如果是>就是大堆
{
Swap(&a[child], &a[parant]);
child = parant;
parant = (child - 1) / 2;
}
else
{
break;
}
}
}
void HeapPush(HP* php, HPDataType x)
{
assert(php);
//判断是否需要扩充并进行扩充
if (php->size == php->capacity)
{
size_t newCapacity = php->capacity == 0 ? 2 : 2 * php->capacity;
HPDataType*tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)*newCapacity);
if (tmp == NULL)
{
printf("realloc failed\n");
exit(-1);
}
php->a = tmp;
php->capacity = newCapacity;
}
php->a[php->size] = x;
php->size++;
//向上调整,控制保持是堆
AdjustUp(php->a, php->size - 1);
}
思路:
下面是向下调整的图示:
时间复杂度:O(log2N)
void Swap(HPDataType* pa, HPDataType* pb)//交换函数:交换数组中的两个元素
{
HPDataType tmp = *pa;
*pa = *pb;
*pb = tmp;
}
void AdjustDown(HPDataType* a, size_t size,size_t root)
{
size_t parant = root;
size_t child = 2*parant+1;
while (child<size)
{
if (child+1<size &&a[child + 1] < a[child])//此时后面的这个如果是<就是小堆,如果是>就是大堆
++child;
if (a[child] < a[parant])//如果是<就是小堆,如果是>就是大堆
{
Swap(&a[child], &a[parant]);
parant = child;
child = 2 * parant + 1;
}
else
{
break;
}
}
}
void HeapPop(HP* php)
{
assert(php);
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}
问:堆的删除为什么不直接从后向前进行覆盖,把第一个元素覆盖掉?
答:首先时间复杂度是O(N),其次堆原来的结构可能会被打乱,同时也可能丧失堆原来的性质变得不再是堆,除非堆原来的数组元素是从小到大或者从大到小是有序的情况下才一定能够保持堆的性质,但即使这种情况下堆的结构仍然会被打乱,即它们的父子关系被破坏掉。
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
size_t HeapSize(HP* php)
{
assert(php);
return php->size;
}
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
void HeapPrint(HP* php)
{
assert(php);
for (size_t i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
}
printf("\n");
}
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/m0_57304511/article/details/124246461
内容来源于网络,如有侵权,请联系作者删除!