数据布局：堆
目录1.堆的概念
2.堆的布局
3.堆的初始化
4.堆的烧毁
5.堆的插入
6.堆的删除
7.判断堆是否为空
1.堆的概念
堆的性子：
[*] 堆中某个结点的值总是不大于或不小于其父结点的值；
[*] 堆总是一棵完全二叉树。https://i-blog.csdnimg.cn/direct/238ce907dbe8486db0692007cc10fd91.png
以下堆的布局默认大堆 ：
2.堆的布局
堆是非线性数据布局，相当于一维数组，有两个直接后继 。
//大堆
typedef int HPDataType;
typedef struct Heap
{
HPDataType* _a;
int _size; //数组中元素的个数
int _capacity;//数组的容量
}Heap; 堆是怎样存储在数组中呢？
在数组下标中，若当前节点在数组中的下标为 i， 则其父节点的下标为 （i-1）/2，其左子节点的下标为 i*2+1，其右子节点的下标为i*2+1+1；
若一个节点的下标为3，其父节点的小标为1，其左孩子节点的下标为7，右孩子结点的下标为8。
3.堆的初始化
/初始化
void HeapInit(Heap* php)
{
assert(php);
php->_a = (HPDataType*)malloc(sizeof(HPDataType)*5);
php->_size = 0;
php->_capacity = 5;
} 4.堆的烧毁
// 堆的销毁
void HeapDestory(Heap* php)
{
free(php->_a);
php->_size = 0;
php->_capacity = 0;
} 5.堆的插入
首先插入时，判断数组空间是否已满，若满了则扩容，接着在数组的最后举行插入，然后举行向上调整（向上调整就是判断父亲和孩子的大小，若孩子大于父亲则举行交换，）
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustUp(Heap* php, int child)
{
assert(php);
// 找到插入节点的父结点的下标
int parent = (child - 1) / 2;
while (child > 0)
{
// 若孩子结点大于父亲结点，则父亲和孩子进行交换，然后改变父亲结点和孩子结点的下标
if (php->_a > php->_a)
{
Swap(&php->_a, &php->_a);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
// 堆的插入
void HeapPush(Heap* php, HPDataType x)
{
assert(php);
//扩容
if (php->_size == php->_capacity)
{
HPDataType* tmp = (HPDataType*)realloc(php->_a, sizeof(HPDataType) * php->_capacity * 2);
if (tmp == NULL)
{
perror("push::realloc");
return;
}
php->_a = tmp;
php->_capacity *= 2;
}
php->_a = x;
php->_size++;
//向上调整
// 插入元素的数组下标
AdjustUp(php, php->_size - 1);
} 6.堆的删除
这里的删除是删除数组中第一个元素（即最大的的元素），首先将数组中最后一个元素和第一个元素举行交换，然后举行向下调整，满足大堆的条件
void AdjustDown(Heap* php,int n,int parent)
{
assert(php);
//找到左孩子
int child = parent * 2 + 1;
while (child < n)
{
//判断右孩子是否存在， 若存在则将左孩子和右孩子进行比较
// 若右孩子大于左孩子，则将右孩子与父亲作比较，即child++，找到右孩子下标
if (child + 1 < n && php->_a < php->_a)
{
child++;
}
//当父母小于孩子时，交换，同时重新赋值父亲结点和孩子结点
if(php->_a < php->_a)
{
Swap(&php->_a, &php->_a);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
// 堆的删除
void HeapPop(Heap* php)
{
assert(php);
assert(!HeapEmpty(php));
//删除头元素
Swap(&php->_a, &php->_a);
php->_size--;
//向下调整
//需要从根节点进行调整
AdjustDown(php,php->_size,0);
} 7.判断堆是否为空
// 堆的判空 空1，非空0
int HeapEmpty(Heap* php)
{
assert(php);
return php->_size == 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]