向上调整&向下调整算法

AdjustUp向上调整

前提是：插入数据之后，除去插入的数据其他的数据还是为堆

应用：插入数据。

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

步骤：

1. 插入数据
2. 与自己的父亲比较
3. 交换/不交换
4. 交换：孩子来到父亲位置，父亲来到自己父亲的位置
5. 结束循环两个点：

• 不交换（跳出循环）
• 一直交换直到来到根节点>0

性质：

• parent=(child-1)/2
• leftchild=parent*2+1
• rightchild=parent*2+2

结束循环条件：child > 0

时间复杂度：O(logN) -- 高度次（后面细讲）

//交换
void Swap(HpDataType* H1, HpDataType* H2)
{
  HpDataType tmp = *H1;
  *H1 = *H2;
  *H2 = tmp;
}

//向上调整算法
void AdjustUp(HpDataType* a, int child)
{
  int parent = (child - 1) / 2;
  while ( child > 0 )//此刻parent已经数组越界
  {
    if (a[child] < a[parent])
    {
      //交换
      Swap(&a[child], &a[parent]);
      child = parent;
      parent = (parent - 1) / 2;
    }
    else//child>=parent
    {
      break;
    }
  }
}

AdjustDown向下调整

向下调整算法有一个前提：左右子树必须是一个堆，才能调整

应用：删除数据。

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

步骤：

1. 删除堆顶元素
2. 堆顶元素与最后一个元素交换
3. 删除最后一个元素
4. 堆顶元素与左右两个孩子（最小/最大的孩子比较）
5. 交换/不交换
6. 交换：父亲来到孩子位置，孩子来到自己孩子的位置
7. 结束循环条件：

• 不交换（跳出循环）
• 交换直到来到最后一个叶子节点<size
• 注意❗跳出循环还有坑

性质：

• parent=(child-1)/2
• leftchild=parent*2+1
• rightchild=parent*2+2

结束循环条件：child < size (❌child+1 < size && child <size)

时间复杂度：O(logN)-- 高度次（后面细讲）

int array[] = {27,15,19,18,28,34,65,49,25,37};

Adjustdown(php->a, php->size, 0);
//向下调整
void Adjustdown(HpDataType* a, int size, int parent)
{
  //假设法
  int child = parent * 2 + 1;
  while (child < size )//why child < size && child+1<size
  {
    if (child + 1 < size && a[child + 1] < a[child])
    {
      child++;
    }
    //比较
    if (a[child] < a[parent])
    {
      //交换
      Swap(&a[child], &a[parent]);
      parent = child;
      child = child * 2 + 1;
    }
    else//>=
    {
      break;
    }
  }
}

//交换
void Swap(HpDataType* H1, HpDataType* H2)
{
  HpDataType tmp = *H1;
  *H1 = *H2;
  *H2 = tmp;
}

下篇重点：

• 建堆（方式/时间复杂度）
• 堆排序
• ToK问题

🙂感谢大家的阅读，若有错误和不足，欢迎指正！