// 初始化元素都为 0
int a[2][3] = {0};
👉简单来说:
大堆
➡️实现:
1️⃣先将原先数组的内容全部拷贝至新创建的堆中
2️⃣将此堆里的元素排序进行调整,建为 大堆
🔥重点: 如何调整为大堆
- 也就是建堆
1.首先:我们假设要建堆的数组的元素除了根节点不满足
大堆
,左右子树都满足大堆
的情况2.思路:此时我们就需要将值为
2
的结点进行向下比较,最终放到适合的位置,从而使整个堆满足大堆
的要求👉向下调整算法: 当左右子树都为
大堆
或小堆
的时候,便可通过此算法调整根结点的位置,使整棵树满足大堆
或小堆
【我们这里本质操控的是数组
】
1️⃣先将值为
2
的结点(父亲结点)的左、右孩子比较值的大小,因为是要建大堆,所以选出左右孩子中的较大值2️⃣比较父亲结点与左右孩子中的较大值哪个值更大,若孩子节点的值大于父亲节点,则交换调整,并将原来孩子的位置当成父亲(因为前面已经交换位置了),继续重复调整下去,直至父亲结点走到
叶子结点
,说明父亲结点已经走到树的最后一层,完成调整了3️⃣若当孩子结点的值小于父亲结点,说明此时父亲结点处在的位置再往下已经满足
大堆
的要求,就可以停止调整了❗特别注意:
- 比较孩子结点的时候,有可能只有左孩子结点,没有右孩子结点的时候(就如上述情况),不可访问右孩子结点,即需要防止数组越界【
child + 1 < n
】
✊综上:向下调整算法的代码实现【时间复杂度:O(logN)O(logN)O(logN)】
void ADjustDown(int * a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
//当 孩子的下标 超出 数组的范围,则说明不存在
{
//1.选出左右孩子中,较小的一个
//child -- 左孩子下标;child+1 -- 右孩子下标
if (child + 1 < n && a[child + 1] > a[child])
{
//想象的时候:默认左孩子是比右孩子小
//如果大的话,child就走到右孩子下标处
child++;
}
//2.交换
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
//满足的情况
break;
}
}
}
❓当左右子树都不是大堆
时候,怎么办
上述仅用于左右子树都满足 大堆
或小堆
的情况,我们现在对于一个结点数值都是随机摆放的完全二叉树,是不能直接运用向下调整算法
进行建堆的
那此时我们便可以创造条件:从后往前建堆
➡️思路:
1️⃣找到完全二叉树中最后一个结点的父亲结点
2️⃣判断此父亲结点与其孩子结点构成的局部二叉树是否是我们想要的
大堆
,若不满足,则向下调整使这个局部的二叉树满足3️⃣调整完后,父亲结点对应的下标
--
【即往前找上一个结点】,再重复步骤2️⃣,直至调整为我们上面举的例子,最终调整最后一次后,这个完全二叉树便为大堆
👉这样,便正真建成了一个大堆
✊综上:建堆的代码实现【时间复杂度:O(N)O(N)O(N)】
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(php->a, php->size, i);
}
❗特别注意:
a
表示需要建堆的数组的首元素地址
n
为数组的a
的元素个数
1️⃣建堆的函数声明:
void HeapInit(HP* php,HPDataYtpe* a,int n);
2️⃣建堆函数的实现:
void HeapInit(HP* php, HPDataYtpe* a, int n)
{
assert(php);
php->a = (HPDataYtpe*)malloc(sizeof(HPDataYtpe)*n);
if (php->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
//1.拷贝
memcpy(php->a, a, sizeof(HPDataYtpe)*n);
php->size = n;
php->capacity = n;
//2.建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(php->a, php->size, i);
}
}
针对问题标题中打印二维数组的问题,可以采用循环嵌套的方式输出每一个元素。具体实现代码如下:
int array[3][3] = {0}; // 定义一个3×3的二维数组,并初始化为0
for(int i=0; i<3; i++){
for(int j=0; j<3; j++){
printf("%d ", array[i][j]); // 逐个输出每一个元素
}
printf("\n"); // 换行,以便区分每一行
}
对于问题内容中初始化二维数组中所有元素为0的方式,也可以采用循环的方式逐个赋值。具体实现代码如下:
int array[3][3] = {0}; // 定义一个3×3的二维数组
for(int i=0; i<3; i++){
for(int j=0; j<3; j++){
array[i][j] = 0; // 逐个将元素赋值为0
}
}
如果想要将所有元素都赋值为同一个值,可以使用数组初始化的方式,例如:
int array[3][3] = {{0}}; // 所有元素都初始化为0
int array2[3][3] = {{1}}; // 所有元素都初始化为1
如果以上解决方案不能解决问题,需要更具体的问题描述和代码展示,具体情况具体分析。