堆排序时间复杂度深入理解
Heap-sort time complexity deep understanding
我在大学学习数据结构课程时，学到了以下公理：
在最坏的情况下，向堆中插入一个新数字需要 O(logn)（取决于它作为叶）
构建一个 n 个节点的堆，使用 n 个插入，从一个空堆开始，总结为O(n) 时间，使用摊销分析
在最坏的情况下，移除最小值需要 O(logn) 时间（取决于新的顶部节点在与最后一片）
将所有的最小值一一移除，直到堆为空，需要O(nlogn)时间复杂度
温馨提示：“堆排序”算法的步骤为：
- 将所有数组值添加到堆中：使用摊销分析技巧求和为 O(n) 时间复杂度
- 从堆中弹出最小值 n 次并将第 i 个值放入 i-数组的第一个索引：O(nlogn) 时间复杂度，因为摊销分析技巧在弹出最小值时不起作用
我的问题是：为什么摊销分析技巧在清空堆时不起作用，导致堆排序算法需要 O(nlogn) 次而不是 O(n) 次？
Edit/Answer
当堆存储在数组中（而不是带有指针的动态树节点）时，我们可以自底向上构建堆，即从叶子开始向上到根，然后使用摊销分析我们可以获得 O(n) 的总时间复杂度，而我们不能清空堆最小值的自下而上。
假设您只能通过比较两个对象来了解它们的相对排名，那么无法在时间 O(n) 内从二叉堆中出列所有元素。如果你能做到这一点，那么你可以通过在时间 O(n) 内构建堆然后在时间 O(n) 内将所有内容出队来在时间 O(n) 内对列表进行排序。但是，排序下限表示比较排序为了正确，平均运行时间必须为 Ω(n log n)。换句话说，您不能太快地从堆中出列，否则您会打破排序障碍。
还有一个问题是为什么从二进制堆中取出 n 个元素需要时间 O(n log n) 而不是更快。展示起来有点棘手，但这是基本思想。考虑您在堆上进行的出列的前半部分。查看实际出列的值并考虑它们在堆中的位置。除了最下面一行的那些，其他所有出队的东西都必须一次一个交换地渗透到堆的顶部才能被删除。您可以证明堆中有足够的元素来保证仅此一项就需要时间 Ω(n log n)，因为这些节点中大约有一半将位于树的深处。这解释了为什么摊销论点不起作用——你不断地将深层节点拉到堆上，所以节点必须移动的总距离很大。将此与 heapify 操作进行比较，其中大多数节点移动的距离非常短。
让我“从数学上”向您展示我们如何计算将任意数组转换为堆（让我称之为“堆构建”）然后使用堆排序对其进行排序的复杂性。
堆构建时间分析
为了将数组转换为堆，我们必须查看每个具有子节点的节点并“堆化”（下沉）该节点。您应该问问自己我们执行了多少次比较；如果你仔细想想，你会看到 (h = tree height):
- 对于级别 i 的每个节点，我们进行 h-i 比较：#comparesOneNode(i) = h-i
- 在级别 i，我们有 2^i 个节点：#nodes(i) = 2^i
- 所以，通常 T(n,i) = #nodes(i) * #comparesOneNode(i) = 2^i *(h-i)，是在“i”级别“比较”所花费的时间
我们举个例子。假设有一个包含 15 个元素的数组，即树的高度为 h = log2(15) = 3:
- 在第 i=3 级，我们有 2^3=8 个节点，我们对每个节点进行 3-3 次比较：正确，因为在第 3 级，我们只有没有子节点的节点，即叶子。 T(n, 3) = 2^3*(3-3) = 0
- 在第 i=2 级，我们有 2^2=4 个节点，我们对每个节点进行 3-2 次比较：正确，因为在第 2 级，我们只有第 3 级可以与之比较。 T(n, 2) = 2^2*(3-2) = 4 * 1
- 在级别 i=1，我们有 2^1=2 个节点，我们对每个节点进行 3-1 次比较：T(n, 1) = 2^1*(3-1) = 2 * 2
- 在第 i=0 层，我们有 2^0=1 个节点，即根，我们进行 3-0 比较：T(n, 0) = 2^0*(3-0) = 1 * 3
好的，一般来说：
T(n) = 总和(i=0 到 h) 2^i * (h-i)
但是如果你记得 h = log2(n)，我们有
T(n) = sum(i=0 to log2(n)) 2^i * (log2(n) - i) =~ 2n
堆排序时间分析
现在，这里的分析真的很相似。每次我们“删除”最大元素（根）时，我们移动到树中最后一片叶子的根，将其堆化并重复直到结束。那么，我们在这里执行多少次比较？
- 在级别 i，我们有 2^i 个节点：#nodes(i) = 2^i
- 对于级别“i”的每个节点，在最坏的情况下，heapify 将始终执行与级别“i”完全相等的相同数量的比较（我们从级别 i 中取出一个节点，将其移动root，调用 heapify，在最坏的情况下 heapify 会将节点带回级别 i，执行“i”比较：#comparesOneNode(i) = i
- 所以，一般来说T(n,i) = #nodes(i) * #comparesOneNode(i) = 2^i*i，就是去掉前2^i个根再带回来的时间正确定位临时根。
我们举个例子。假设有一个包含 15 个元素的数组，即树的高度为 h = log2(15) = 3:
- 在第 i=3 层，我们有 2^3=8 个节点，我们需要将它们中的每一个移动到根位置，然后将它们中的每一个堆化。每个 heapify 将执行最坏情况下的“i”比较，因为根可能会下沉到仍然存在的级别“i”。 T(n, 3) = 2^3 * 3 = 8*3
- 在级别 i=2，我们有 2^2=4 个节点，我们对每个节点进行 2 次比较：T(n, 2) = 2^2*2 = 4 * 2
- 在第 i=1 层，我们有 2^1=2 个节点，我们对每个节点进行 1 次比较：T(n, 1) = 2^1*1 = 2 * 1
- 在第 i=0 层，我们有 2^0=1 个节点，即根，我们进行 0 次比较：T(n, 0) = 0
好的，一般来说：
T(n) = 总和(i=0 到 h) 2^i * i
但是如果你记得 h = log2(n)，我们有
T(n) = sum(i=0 to log2(n)) 2^i * i =~ 2nlogn
堆构建 VS 堆排序
从直觉上，您可以看到堆排序无法“摊销”他的成本，因为每次我们增加节点数时，我们都必须进行更多比较，而我们在堆构建功能中恰恰相反！你可以在这里看到：
- 堆构建：T(n, i) ~ 2^i * (h-i)，如果i增加，#nodes增加，但#compares减少
- Heapsort: T(n, i) ~ 2^i * i，如果i增加，#nodes增加，#compares增加
所以：
- Level i=3, #nodes(3)=8, Heap build 做 0 次比较，heapsort 做 8*3 = 24 次比较
- 级别 i=2，#nodes(2)=4，堆构建进行 4 次比较，堆排序进行 4*2 = 8 次比较
- 级别 i=1，#nodes(1)=2，堆构建进行 4 次比较，堆排序进行 2*1 = 2 次比较
- 级别 i=0，#nodes(0)=1，堆构建进行 3 次比较，堆排序进行 1*0 = 1 次比较
我在大学学习数据结构课程时，学到了以下公理：
在最坏的情况下，向堆中插入一个新数字需要 O(logn)（取决于它作为叶）
构建一个 n 个节点的堆，使用 n 个插入，从一个空堆开始，总结为O(n) 时间，使用摊销分析
在最坏的情况下，移除最小值需要 O(logn) 时间（取决于新的顶部节点在与最后一片）
将所有的最小值一一移除，直到堆为空，需要O(nlogn)时间复杂度
温馨提示：“堆排序”算法的步骤为：
- 将所有数组值添加到堆中：使用摊销分析技巧求和为 O(n) 时间复杂度
- 从堆中弹出最小值 n 次并将第 i 个值放入 i-数组的第一个索引：O(nlogn) 时间复杂度，因为摊销分析技巧在弹出最小值时不起作用
我的问题是：为什么摊销分析技巧在清空堆时不起作用，导致堆排序算法需要 O(nlogn) 次而不是 O(n) 次？
Edit/Answer
当堆存储在数组中（而不是带有指针的动态树节点）时，我们可以自底向上构建堆，即从叶子开始向上到根，然后使用摊销分析我们可以获得 O(n) 的总时间复杂度，而我们不能清空堆最小值的自下而上。
假设您只能通过比较两个对象来了解它们的相对排名，那么无法在时间 O(n) 内从二叉堆中出列所有元素。如果你能做到这一点，那么你可以通过在时间 O(n) 内构建堆然后在时间 O(n) 内将所有内容出队来在时间 O(n) 内对列表进行排序。但是，排序下限表示比较排序为了正确，平均运行时间必须为 Ω(n log n)。换句话说，您不能太快地从堆中出列，否则您会打破排序障碍。
还有一个问题是为什么从二进制堆中取出 n 个元素需要时间 O(n log n) 而不是更快。展示起来有点棘手，但这是基本思想。考虑您在堆上进行的出列的前半部分。查看实际出列的值并考虑它们在堆中的位置。除了最下面一行的那些，其他所有出队的东西都必须一次一个交换地渗透到堆的顶部才能被删除。您可以证明堆中有足够的元素来保证仅此一项就需要时间 Ω(n log n)，因为这些节点中大约有一半将位于树的深处。这解释了为什么摊销论点不起作用——你不断地将深层节点拉到堆上，所以节点必须移动的总距离很大。将此与 heapify 操作进行比较，其中大多数节点移动的距离非常短。
让我“从数学上”向您展示我们如何计算将任意数组转换为堆（让我称之为“堆构建”）然后使用堆排序对其进行排序的复杂性。
堆构建时间分析
为了将数组转换为堆，我们必须查看每个具有子节点的节点并“堆化”（下沉）该节点。您应该问问自己我们执行了多少次比较；如果你仔细想想，你会看到 (h = tree height):
- 对于级别 i 的每个节点，我们进行 h-i 比较：#comparesOneNode(i) = h-i
- 在级别 i，我们有 2^i 个节点：#nodes(i) = 2^i
- 所以，通常 T(n,i) = #nodes(i) * #comparesOneNode(i) = 2^i *(h-i)，是在“i”级别“比较”所花费的时间
我们举个例子。假设有一个包含 15 个元素的数组，即树的高度为 h = log2(15) = 3:
- 在第 i=3 级，我们有 2^3=8 个节点，我们对每个节点进行 3-3 次比较：正确，因为在第 3 级，我们只有没有子节点的节点，即叶子。 T(n, 3) = 2^3*(3-3) = 0
- 在第 i=2 级，我们有 2^2=4 个节点，我们对每个节点进行 3-2 次比较：正确，因为在第 2 级，我们只有第 3 级可以与之比较。 T(n, 2) = 2^2*(3-2) = 4 * 1
- 在级别 i=1，我们有 2^1=2 个节点，我们对每个节点进行 3-1 次比较：T(n, 1) = 2^1*(3-1) = 2 * 2
- 在第 i=0 层，我们有 2^0=1 个节点，即根，我们进行 3-0 比较：T(n, 0) = 2^0*(3-0) = 1 * 3
好的，一般来说：
T(n) = 总和(i=0 到 h) 2^i * (h-i)
但是如果你记得 h = log2(n)，我们有
T(n) = sum(i=0 to log2(n)) 2^i * (log2(n) - i) =~ 2n
堆排序时间分析
现在，这里的分析真的很相似。每次我们“删除”最大元素（根）时，我们移动到树中最后一片叶子的根，将其堆化并重复直到结束。那么，我们在这里执行多少次比较？
- 在级别 i，我们有 2^i 个节点：#nodes(i) = 2^i
- 对于级别“i”的每个节点，在最坏的情况下，heapify 将始终执行与级别“i”完全相等的相同数量的比较（我们从级别 i 中取出一个节点，将其移动root，调用 heapify，在最坏的情况下 heapify 会将节点带回级别 i，执行“i”比较：#comparesOneNode(i) = i
- 所以，一般来说T(n,i) = #nodes(i) * #comparesOneNode(i) = 2^i*i，就是去掉前2^i个根再带回来的时间正确定位临时根。
我们举个例子。假设有一个包含 15 个元素的数组，即树的高度为 h = log2(15) = 3:
- 在第 i=3 层，我们有 2^3=8 个节点，我们需要将它们中的每一个移动到根位置，然后将它们中的每一个堆化。每个 heapify 将执行最坏情况下的“i”比较，因为根可能会下沉到仍然存在的级别“i”。 T(n, 3) = 2^3 * 3 = 8*3
- 在级别 i=2，我们有 2^2=4 个节点，我们对每个节点进行 2 次比较：T(n, 2) = 2^2*2 = 4 * 2
- 在第 i=1 层，我们有 2^1=2 个节点，我们对每个节点进行 1 次比较：T(n, 1) = 2^1*1 = 2 * 1
- 在第 i=0 层，我们有 2^0=1 个节点，即根，我们进行 0 次比较：T(n, 0) = 0
好的，一般来说：
T(n) = 总和(i=0 到 h) 2^i * i
但是如果你记得 h = log2(n)，我们有
T(n) = sum(i=0 to log2(n)) 2^i * i =~ 2nlogn
堆构建 VS 堆排序
从直觉上，您可以看到堆排序无法“摊销”他的成本，因为每次我们增加节点数时，我们都必须进行更多比较，而我们在堆构建功能中恰恰相反！你可以在这里看到：
- 堆构建：T(n, i) ~ 2^i * (h-i)，如果i增加，#nodes增加，但#compares减少
- Heapsort: T(n, i) ~ 2^i * i，如果i增加，#nodes增加，#compares增加
所以：
- Level i=3, #nodes(3)=8, Heap build 做 0 次比较，heapsort 做 8*3 = 24 次比较
- 级别 i=2，#nodes(2)=4，堆构建进行 4 次比较，堆排序进行 4*2 = 8 次比较
- 级别 i=1，#nodes(1)=2，堆构建进行 4 次比较，堆排序进行 2*1 = 2 次比较
- 级别 i=0，#nodes(0)=1，堆构建进行 3 次比较，堆排序进行 1*0 = 1 次比较