algorithm - 最小堆中第k个最小元素的复杂度分析

我正在寻找最小堆中的第k个最小元素我有一个代码，这个代码的复杂度是O(k log k)。我试着把它提高到O(k)。
下面是代码。

 struct heap{
      int *array;
      int count;
      int capacity;
 };

 int kthsmallestelement(struct heap *h,int i,int k){
      if(i<0||i>=h->count)
         return INT_MIN;
      if(k==1)
        return h->array[i];
      k--;
      int j=2*i+1;
      int m=2*i+2;
      if(h->array[j] < h->array[m])
      {
         int x=kthsmallestelement(h,j,k);
         if(x==INT_MIN)
            return kthsmallestelement(h,m,k);
         return x;
      }
      else
      {
           int x=kthsmallestelement(h,m,k);
           if(x==INT_MIN)
                return kthsmallestelement(h,j,k);
            return x;
      }
 }

我的代码遍历堆中的k元素，因此复杂性为O(k)。
对吗？

最佳答案

你的代码，事实上，它的整个方法都是完全错误的，IIUC。
在一个经典的min堆中，您只知道从根到子级的每个路径都是非递减的。没有其他约束，特别是路径之间没有约束。
因此，第k个最小元素可以位于前2k元素中的任何位置。如果您只是使用使用经典堆算法构建和维护的整个堆数组，那么任何解决方案都必须是Ω（min（n，2k））下面的任何内容都需要对数组结构、额外的数据结构或两者都有额外的要求。

关于algorithm - 最小堆中第k个最小元素的复杂度分析，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/31291316/