二叉树-堆应用（2）-阿里云开发者社区

二叉树-堆应用（2）

2024-02-26 23

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 二叉树-堆应用（2）

建堆

向上调整建堆

向下调整建堆

本质：直接在数组内调整建堆

向上调整建堆：把第一个元素当成一个堆，往后一个元素模拟成插入这个堆

向下调整建队：把整个数组的元素当成一个树，然后从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

方法1&向上调整建堆

向上调整建堆：把第一个元素当成一个堆，往后一个元素模拟成插入这个堆（每个插入的元素调用向上调整算法）

方法2&向下调整建堆❗

向下调整建队：把整个数组的元素当成一个树，然后从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。（把每棵子树调用向下调整算法）

向下调整建堆：

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？

首先把数组元素逻辑上看成一颗树

然后调整成堆

这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

int a[] = {1,5,3,8,7,6};

总代码

//建堆
void CreateHeap(int* a, int size)
{
  //方法1向上调整建堆 建堆--建的小堆--降序 建大堆--升序
  for (int i = 0; i < size; i++)
  {
    AdjustUp(a, i);
  }
  //printf("\n");
  //方法2向下调整建堆
  for (int i = (size - 1 - 1) / 2; i >= 0; i--)//i=0的时候到达根节点此时就是全部向下调整
  {
    Adjustdown(a, size, i);//这里的size不确定，但是肯定比size小所以取最大就size
  }
}
int main()
{
  int a[10] = { 2,3,7,5,4,3,9,7,6,10 };
  int size = sizeof(a) / sizeof(a[0]);
  CreateHeap(a, size);
  for (int i = 0; i < size; i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}

时间复杂度分析

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

建堆的时间复杂度为O(N)。

节点N&高度h存在：N=2^h-1

对比发现向下：节点少*多的调整；节点多*少的调整

向上：节点少*少的调整；节点多*多的调整

所以：【向下】调整方法才是最优解