时间戳

首页 > 解决方案 > 从最大堆中删除叶节点的时间复杂度？

algorithm - 从最大堆中删除叶节点的时间复杂度？

问题描述

假设我们有一个 MAX Heap，我们想要删除任何叶节点，那么删除任何叶节点并保持最大堆属性需要多长时间？

我的主要疑问是 - 到达叶节点是否需要 O(n) 时间？

另外，为什么二叉堆必须是完整的二叉树而不是几乎完整的二叉树？

标签： algorithmdata-structurestime-complexityheapbinary-heap

解决方案

二叉堆是一棵完全二叉树。所有级别都是满的，除了可能是最后一个，它是左填充的。二叉树不一定是完整的二叉树。

在以数组表示的大小为 N 的二进制堆中，叶节点位于数组的后半部分。即从 N/2 到 N-1 的节点是叶子节点。删除最后一个节点（即a[N-1]）是一个 O(1) 操作：您所要做的就是删除该节点并减小堆的大小。

删除任何其他叶节点可能是 O(log n) 操作，因为您必须：

  1. 将最后一个节点移动a[N-1]到要删除的节点。
  2. 将该项目冒泡到堆中，到它的正确位置。

第一部分当然是 O(1)。第二部分可能需要最多log(n) - 1移动。平均值小于 2，但最坏的情况是log(n) - 1.

推荐阅读