从最大堆中删除叶节点的时间复杂度？
Time complexity to delete a leaf node from Max Heap?
假设我们有一个最大堆，我们想删除任何叶节点，那么删除任何叶节点并保持最大堆需要多少时间属性 ？
我的主要疑问是 - 到达叶节点是否需要 O(n) 时间？
另外，为什么二叉堆必须是完全二叉树而不是几乎完全二叉树？
在MAX堆中你可以在O(logn)中访问堆中的叶子节点，因为它是一个完整的二叉树并遍历整个高度树的需要 O(logn)
完成后，您可以调用 heapify 再次构建堆，这需要 O(logn)
Almost Complete Binary Tree 与 Complete Binary Tree 没有区别，只是它有以下两个限制：
在每个节点完成当前关卡后才进入下一个关卡。
在左节点完成后的每个节点转到右。
所有适用于完全二叉树的公式都适用于几乎完全二叉树。
唯一的区别是在几乎完整的二叉树中，从右到左的最后一层有一个间隙。如果没有间隙就是完全二叉树。
为了提高效率，堆被迫具有这种 属性 作为竞争二叉树的特性
二进制堆是 complete binary tree。所有级别都已满，可能最后一个级别除外，它是左填充的。二叉树不一定是全二叉树。
在一个大小为N的二叉堆中，用数组表示，叶节点在数组的后半部分。即从N/2到N-1的节点为叶节点。删除最后一个节点（即 a[N-1]）是一个 O(1) 操作：您所要做的就是删除节点并减小堆的大小。
删除任何其他叶节点可能是一个 O(log n) 操作，因为您必须：
- 将最后一个节点
a[N-1] 移动到您要删除的节点。
- 将该项目冒泡到堆中，到适当的位置。
第一部分当然是 O(1)。第二部分最多需要 log(n) - 1 步。 平均值小于2，但最坏情况是log(n) - 1.
假设我们有一个最大堆，我们想删除任何叶节点，那么删除任何叶节点并保持最大堆需要多少时间属性 ？
我的主要疑问是 - 到达叶节点是否需要 O(n) 时间？
另外，为什么二叉堆必须是完全二叉树而不是几乎完全二叉树？
在MAX堆中你可以在O(logn)中访问堆中的叶子节点，因为它是一个完整的二叉树并遍历整个高度树的需要 O(logn)
完成后，您可以调用 heapify 再次构建堆，这需要 O(logn)
Almost Complete Binary Tree 与 Complete Binary Tree 没有区别，只是它有以下两个限制：
在每个节点完成当前关卡后才进入下一个关卡。 在左节点完成后的每个节点转到右。
所有适用于完全二叉树的公式都适用于几乎完全二叉树。
唯一的区别是在几乎完整的二叉树中，从右到左的最后一层有一个间隙。如果没有间隙就是完全二叉树。
为了提高效率，堆被迫具有这种 属性 作为竞争二叉树的特性
二进制堆是 complete binary tree。所有级别都已满，可能最后一个级别除外，它是左填充的。二叉树不一定是全二叉树。
在一个大小为N的二叉堆中，用数组表示，叶节点在数组的后半部分。即从N/2到N-1的节点为叶节点。删除最后一个节点（即 a[N-1]）是一个 O(1) 操作：您所要做的就是删除节点并减小堆的大小。
删除任何其他叶节点可能是一个 O(log n) 操作，因为您必须：
- 将最后一个节点
a[N-1]移动到您要删除的节点。 - 将该项目冒泡到堆中，到适当的位置。
第一部分当然是 O(1)。第二部分最多需要 log(n) - 1 步。 平均值小于2，但最坏情况是log(n) - 1.