從一個數組，該方法更有效，建立一個二進制堆爲什麼

我正在學習有關堆，我發現從給定陣列創建這些文件的方法有兩種：我試圖建立一個最大堆。從一個數組，該方法更有效，建立一個二進制堆爲什麼

1.Top到向下的方法

在這裏，我只是檢查每一個元素，如果它是在正確的位置與否。通過使用名爲restoreUp的方法，其中每個密鑰與其父密鑰進行比較，並且如果父密鑰小於父密鑰，則向下移動。此過程繼續，直到父密鑰更大。我檢查每個密鑰的起始位置在索引位置2

我的代碼是：

void restoreUp(int arr[],int i) 
{ 
    int k=arr[i]; 
    int par=i/2; 
    while(arr[par]<k) 
    { 
     arr[i]=arr[par]; 
     i=par; 
     par=i/2; 
    } 
    arr[i]=k; 
} 
void buildheap1(int arr[],int size) 
{ 
    int i; 
    for(i=2;i<=size;i++) 
     restoreUp(arr,i); 
}

底向上的方法

在這裏，我從第一非存在於索引地板（尺寸/ 2）葉節點開始，並調用一個方法restoreDown，直到節點號爲1.I comp是左右兩個孩子的關鍵，然後較大的孩子向上移動。如果兩個孩子都大於該關鍵點，則向上移動兩個孩子中較大的一個。當兩個孩子都小於該關鍵點時，該過程停止。

我的代碼是：

void restoreDown(int arr[],int i,int size) 
{ 
    int left=2*i; 
    int right=2*i+1; 
    int num=arr[i]; 
    while(right<=size) 
    { 
     if(num>arr[left] && num>arr[right]) 
     { 
      arr[i]=num; 
      return; 
     } 
     else if(arr[left]>arr[right]) 
     { 
      arr[i]=arr[left]; 
      i=left; 
     } 
     else 
     { 
      arr[i]=arr[right]; 
      i=right; 
     } 
     left=2*i; 
     right=2*i+1; 
    } 
    if(left==size && arr[left]>num) 
    { 
     arr[i]=arr[left]; 
     i=left; 
    } 
    arr[i]=num; 
} 
void buildheap2(int arr[],int size) 
{ 
    int i; 
    for(i=size/2;i>=1;i--) 
     restoreDown(arr,i,size); 
}

這兩個方法都爲我工作。我只是想知道哪種方法更有效率，爲什麼？

來源

2013-07-19 poorvankBhatia

對於漸進複雜，參見[相關的維基百科文章（http://en.wikipedia.org/wiki/Heapsort），從開始*此外，「siftDown」版本heapify的*。對於真實的性能，請使用分析器。 –

一般用現代的CPU（有緩存）說。讀取和向後數組通常是一個非常糟糕的主意，因爲它會產生大量的緩存未命中。除非（當然）陣列已經在緩存中。

所以第一種方法似乎是從這個角度看更好。

來源

2013-07-23 06:48:15 Laurent

從一個數組，該方法更有效，建立一個二進制堆爲什麼

回答

相關問題