獲取Heapsort的前x個元素

我正準備參加Google開發者面試並處理算法問題。我需要弄清楚如何使用Heapsort算法得到大小爲n的第一個元素x。算法的哪個部分需要修改才能得到最小的第一個元素？獲取Heapsort的前x個元素

這是簡介堆排序算法，算法由Cormen Leiserson（第155頁）：

HEAPSORT(A) 
{ 
    BUILD-MAX-HEAP(A) 
    for i = A.length down to 2 
     exchange A[1] with A[i] 
     A.heap-size = A.heap-size - 1 
     MAX-HEAPIFY(A, 1) 
}

這些組件的算法：

BUILD-MAX-HEAP(A) 
    A.heap-size = A.length 
    for i = floor(A.length/2) down to 1 
    MAX-HEAPIFY(A, i) 

MAX-HEAPIFY(A, i) 
    l = LEFT(i) 
    r = RIGHT(i) 
    if l <= A.heap-size and A[l] > A[i] 
    largest = l 
    else largest = r 
    if r <= A.heap-size and A[r] > A[largest] 
    largest = r 
    if largest != i 
    exchange A[i] with A[largest] 
    MAX-HEAPIFY(A, largest)

我想不出什麼部分進行修改以獲得排序後的數組的最小元素。還需要找到修改算法的時間複雜度。

來源

2014-06-24 MNRC

通過改變MAX-HEAPIFY中的條件，我們可以將它改爲MIN-HEAPIFY，因此我們可以很容易地獲得最小堆。

然後，這個堆的第一個元素是最小的元素，我們可以刪除這個元素，並將堆中的最後一個元素放到第一個元素中，再次調用MIN-HEAPIFY來維護堆的屬性。繼續這個過程n次，我們可以得到第n個最小的對象。

時間複雜度：log（m）+ log（m - 1）+ ... + log（m - n）〜O（nlogm）

來源

2014-06-24 07:59:43

獲取Heapsort的前x個元素

回答

相關問題