heap - max-heapify 和 min-heapify 有什么区别？

Question

其实我也听说过向上再堆化和向下再堆化这两个名词。但是 max-heapify 和 min-heapify 是什么意思呢？这两个术语（最大堆和最小堆）是否与向上再堆和向下再堆有关？根据我的说法，向上再堆和向下再堆都属于最大堆和最小堆。如果我错了，请纠正我。另外请告诉我所有这四个术语的时间复杂度。

Answer 1

将项目添加到二叉堆时会执行向上重新堆化。添加项目时，请执行以下操作：

1. 将项目添加到数组的末尾。
2. 将它在堆中向上移动到适当的位置。这一步是向上的再堆化。它也被称为“起泡”、“筛选”或“游泳”。

从堆中删除根项时，请执行以下操作：

1. 用堆上的最后一项替换根项。
2. 将该项目从堆中移到适当的位置。这是向下的重组。它也被称为“冒泡”、“筛下”或“下沉”。

这两种操作同样适用于最小堆和最大堆。

在最小堆中，实现向下重新堆的函数通常称为“最小堆”。在最大堆实现中，该函数通常称为“最大堆”。

向上再堆化和向下再堆化都具有 O(log n) 的复杂度。