k個最大元素

Question

我使用的最大堆找到對數組中的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; 

    } 

Answer 1

的Selection algorithm就可以找到的第k個元素，或k中O（n）的時間的陣列最大元素。

Answer 2

你的推理幾乎是正確的，然而堆棧大小爲k，heapify操作需要O(log k)。因此，總的複雜性是O(n log k)。爲什麼？在最糟糕的情況下，你應該爲其餘的元素執行heapify每個n-k。由於k是固定的，並且n可以是任意大的，也就是O(n)的步驟，最後給出O(n log k)。

參見：

• Heap sort