在二叉堆中查找特定元素？

Question

在一个有 100 个元素的二叉堆中，找到第 99 个元素需要多长时间？

或者在 "n" 个元素的二叉堆中，找到第 (n-1) 个元素所花费的时间？

============================================= ============================

我的时间复杂度为 O(1)，因为您可以简单地转到数组的第 99 个单元格。

Answer 1

在 n 个元素的二进制最小堆中，第 (n-1)^th 个元素（即次大元素）将位于树的最后一层，或堆的倒数第二层。在满堆中，最后一层有 (n+1)/2 项，倒数第二层有 (n+1)/4 项。

这是一个复杂度为 O(n) 的操作，因为您可能需要搜索 (3*(n+1))/4 个元素。

这不是 O(1)，因为堆不一定是有序的。您不能保证 100 项堆中的第 99 个最小项位于数组中的第 99 个位置。考虑这两个最小堆：

        1                   1
    2       3           5       2    
  4   5   6   7       6   7   3   4

这两个都是有效的最小堆，但在第二个中，第二小的项在数组中的位置 3。

更新

实际上，在完整的二进制堆中，倒数第二个项目必须在叶级别上。在一个未满的堆中，它可以在叶级、本级或上级的任何位置。考虑一下，例如：

      1
   2     6            
  3 5   7

关于第(3*(n+1)/2)题：

倒数第二个可以是最后一层（4 个节点）或倒数第二层（2 个节点）的任何位置。总共 6 个可能的节点。最后一层的 (7+1)/2 个节点，倒数第二层的 (7+1)/4 个节点。简化，即 (3*(7+1))/4.

Finding a specific element in Binary Heap?