二進制堆 - 如何以及何時使用max-heapify

我正在閱讀有關堆數據結構，我無法弄清楚何時使用max heapify函數以及爲什麼。二進制堆 - 如何以及何時使用max-heapify

我寫了一個插入函數，它將始終保持堆最大堆，我無法看到何時會使用max-heapify。

你能解釋一下嗎？謝謝

這是我的代碼：

int PARENT(int i) 
    { 
return i/2; 
    } 

    int LEFT(int i) 
    { 
return 2*i; 
    } 
    int RIGHT(int i) 
    { 
return 2*i +1; 
    } 


    void max_heapify(int *v, int index, int heapsize) 
    { 
int largest; 
    int left = LEFT(index); 
int right = RIGHT(index); 
if (left<heapsize && v[left] > v[index]) 
    largest = left; 
else 
    largest = index; 
if (right < heapsize && v[right] > v[largest]) 
    largest = right; 
if (largest !=index) 
{ 
    v[index] = v[index] ^v[largest]; 
    v[largest] = v[index] ^v[largest]; 
    v[index] = v[index] ^v[largest]; 
    max_heapify(v,largest,heapsize); 
} 

    } 

    void insert(int *v, int * length, int value) 
    { 
v[++*length] = value; 
int valuePos = *length; 
int parent = PARENT(valuePos); 
if (parent!=valuePos) 
{ 
    while (v[parent] < v[valuePos]) 
    { 
     v[parent] = v[parent]^v[valuePos]; 
     v[valuePos] = v[parent] ^v[valuePos]; 
     v[parent] = v[parent]^v[valuePos]; 
     valuePos = parent; 
     parent = PARENT(valuePos); 
    } 
}

}

來源

2012-01-21 Dan Dinu

注意：標準庫已經提供了這個功能。 –

的heapify算法應該轉向一個數組堆時使用。你可以通過將每個數組元素依次插入一個新堆來實現，但這需要O（n n n）時間，而heapify在O（n）時間內完成。

來源

2012-01-21 16:34:47

那麼，我的max_heapify算法出錯了，因爲我試圖調用無序數組的函數來將它變成堆。它雖然不起作用。你能給我舉個例子嗎？我試過調用max_heapify（v，0，n），但結果不是堆 –

正如我的回答中所提到的，may_heapify（）僅適用於已排序的序列。由於在堆中插入元素以某種方式對它們進行排序，插入必須至少需要O（_n_ lg _n_）時間 - 沒有更快的排序算法:)但是，您可以使用該函數在在O（_n_）堆中，而插入具有'insert'函數的_n_元素時，無論順序如何，_always_都會帶上O（_n_ lg _n_）。 – penelope

max_heapify預計將在常規數組上調用，以使其成爲堆。並且insert負責維護工作，這需要數組（v在您的函數中）已經成爲堆。

來源

2012-01-21 16:38:50 grapeot

max-heapify函數，就像你所說的那樣，是一個通用的函數（堆可以使用任何有效的比較函數來對它的元素進行排序）。它旨在用作從數組構建堆的init函數。

init（MAX-heapify）：功能用於與堆處理（與他們的intented用途）

的複雜性O（Ñ），用於從初始化堆排序序列（陣列）（最大排序，你的情況）
insert：O（LG ñ），用於在堆插入單個元件（保持堆樹「排序」）
delete：O（LG ñ），用於從堆中取出「最佳」（最大，你的情況）元素（保持堆樹「排序」）

但是，由於這問題的標籤爲C++，您還應該考慮使用STL中的std::set，而不是實現自己的堆。所考慮的操作的複雜性與任何堆實現相同，並且可以使用任何比較函數（預先編寫或用戶編寫）輕鬆操作。針對堆實現的另一個優點是它是一個已排序的容器，並且可以在不破壞結構的情況下輕鬆遍歷排序順序中的所有元素（而不僅僅是第一個元素）。

std::set唯一的問題是它是一個獨特的容器 - 意味着只有一個具有相同鍵的元素的副本可以存在於其中。但也有一個解決方案 - std::multiset使用相同的密鑰保存多個對象的排序實例。

此外，根據您所需的用途（它有很多與搜索關鍵字相關的數據），您可能還想嘗試std::map或std::multimap。

如果你想製作自己的堆實現，如果你的目的是最大限度地使用C++，我強烈建議將它放在一個單獨的類（甚至是命名空間）中。如果你只是想保持它的形式，你應該考慮將問題重新標記爲C

來源

2012-01-21 17:02:32 penelope

你需要隨機地將數據插入到數組中。之後你可以調用max heapify函數來保留Max Heap的屬性。這裏是我的代碼

class max_heap{ 
private:    // are the private members of class 
     int *arr; 
     int size; 
     int ind; 
}; 

     void max_heap::bubbledown(int *ar, int i) 
     { 
     int len = ind - 1; 
     int lt = 2 * i; 
     int rt = lt + 1; 
     while (lt <= len && rt <= len)           
     { 
      if (arr[i] > arr[lt] && arr[i] > arr[rt]) 
       break; 

      else if (ar[lt] > ar[rt]) 
      { 
       if (ar[i] < ar[lt]){ 
        swap(ar[i], ar[lt]); 
        i = lt; 
        lt = 2 * i; 
       } 
      } 
      else if (ar[lt] < ar[rt]) 
      { 
       if (ar[i] < ar[rt]){ 
        swap(ar[i], ar[rt]); 
        i = rt; 
        rt = (2 * i)+1; 
       } 
      } 
     } 
    } 

    void max_heap::heapify() 
    { 
     int len = ind - 1; 
     for (int i = len; i >= 1 && (i/2) >= 1; i--) 
     { 
      if (arr[i] > arr[i/2]) 
      { 
       swap(arr[i], arr[i/2]); 
       bubbledown(arr, i); 
      } 
     } 
    }

來源

2015-11-11 18:30:27 Hamza

二進制堆 - 如何以及何時使用max-heapify

回答

相關問題