k个最大元素

我使用的最大堆找到对数组中的k个最大的元件如下：k个最大元素

1）I具有建立的前k个元素的最小堆MH（ARR [0 ]到arr [k-1]）给定数组。（k）

2）对于每个元素，在第k个元素（arr [k]到arr [n-1]）之后，将其与MH的根进行比较。

...... a）如果元素比根更大然后使它根和呼叫heapify为MH

...... b）中否则忽略它。

//步骤2是O（（N-K））

3）最后，MH具有k个最大元件和MH的根是第k个最大的元素。

我在网上搜索和第二步的复杂性显示我O（nk）logk，我认为应该是（nk）* O（k）如果我们使用自下而上的方法构建堆。因为每步骤我只是在发现更大的元素时替换根。堆积k个元素阵列的复杂性是O（k）

我错了请澄清。我只需要知道我是否正确思考？

我的方法如下：

private static void createMinHeap(int[] arr) { 

     for (int i = arr.length/2; i >= 0; i--) { 
      restoreDown(arr, i); 
     } 

    } 

    private static void restoreDown(int[] arr, int i) { 

     int left = (2 * i) + 1; 
     int right = (2 * i) + 2; 
     int num = arr[i]; 

     while (right <= arr.length) { 

      if (num <= arr[right] && num <= arr[left]) { 
       arr[i] = num; 
       return; 
      } else if (arr[right] < arr[left]) { 
       arr[i] = arr[right]; 
       i = right; 
      } else { 
       arr[i] = arr[left]; 
       i = left; 
      } 

      left = (2 * i) + 1; 
      right = (2 * i) + 2; 
     } 

     if (left == arr.length - 1 && arr[left] < num) { 
      arr[i] = arr[left]; 
      i = left; 
     } 

     arr[i] = num; 

    }

来源

2015-08-03 user2565192

再平衡是登录N，不为N. – stark

你可能会考虑要求在CS或CS理论或算法。 SO更多的是程序代码。 – Elyasin

堆积一个k元素数组的复杂性是O（log（k））我认为。在最糟糕的情况下，您只会为每个节点从顶端开始堆砌一棵子树，不是吗？ –

-2

的Selection algorithm就可以找到的第k个元素，或k中O（n）的时间的阵列最大元素。

来源

2015-08-03 11:28:43

这是如何回答我的问题？ – user2565192

@ user2565192“O（n）time”（引用我的答案中的数组中的k个最大元素）的哪部分你不明白？你是否问过找到“一个数组中的K个最大元素”的复杂性（引自问题）？ –

@JimMischel我想你错过了关于复杂性问题的部分，而不是真实世界实现的效率。使用选择算法（特别是快速选择）为您提供了O（n）的最坏情况复杂度，这比基于渐近复杂度的基于堆的解决方案更好。 –

你的推理几乎是正确的，然而堆栈大小为k，heapify操作需要O(log k)。因此，总的复杂性是O(n log k)。为什么？在最糟糕的情况下，你应该为其余的元素执行heapify每个n-k。由于k是固定的，并且n可以是任意大的，也就是O(n)的步骤，最后给出O(n log k)。

参见：

Heap sort

来源

2015-08-03 11:45:27

k个最大元素

回答

相关问题