最大ヒープの配列表現

Question

私は最大ヒープを作成しようとしていますが、ロジックが単純です。私は、私は木が

 
     90 
     36 17 
    25 26 7 1 
2 3 19 

ように見えるshoudその配列表現が90 36 17 25 26 7 1 2 3 19 する必要があり、まだコードの出力は

で入力

2 7 26 25 19 17 1 90 3 36 

を使用しています

void maxHeapify(int i , int *a , int n){ 

    int largest = i; 
    int left = (i * 2) + 1; 
    int right = (i * 2) + 2; 

    if(left < n && a[ largest] < a[ left ]) 
     largest = left; 
    if(right < n && a[ largest ] < a[right]) 
     largest = right; 
    if(largest != i){ 
     swap(a[i], a[largest]); 
     maxHeapify(largest , a, n); 
    } 
} 


int main(){ 
    int n; 
    int * a; 
    cout << "Number of elements : "; 
    cin >> n ; 
    a = new int[n]; 
    for(int i = 0; i < n ; i++){ 
     cin >> a[i]; 
    } 

    for(int i = n/2 -1 ; i >= 0 ; i--){ 
     maxHeapify(i , a, n); 
    } 
    for(int i = 0; i < n ; i++){ 
     cout << a[i] << " "; 
    } 

    return 0; 
} 

を使用して、それを実装してみました

90 36 26 25 19 17 1 7 3 2 

私はそれを見て、多くのチュートリアルで多くの同じコードを見つけました。どのように出力がツリーの配列で表されていないのですか？私はそれを誤解しましたか？

ありがとうございました

Answer 1

なぜヒープが特定の方法で見えると思われますか？これらの入力番号をヒープに配置する方法はたくさんあります。あなたが取得している結果も有効なヒープである - 各親はその子よりも、大きいです：

 90 
    36  26 
25 19 17 1 
7 3 2 

Answer 2

最終ヒープ構造の挿入順序と初期構造に基づいて変化します。あなたのケースでは、2 7 26 25 19 17 1 90 3 36は、空のヒープで開始し、指定された順序で要素を挿入し、各挿入後にheapifedした場合に期待される結果をもたらします。

このコードは、あなたが期待する結果が得られます：

std::vector<int> b = {2, 7, 26, 25, 19, 17, 1, 90, 3, 36}; 
std::make_heap(b.begin(), b.end()); 

両方の結果：しかし、どのようなコードがないことは、このに相当preinsertsヒープへのすべての要素、およびそれを配置し、ある

std::vector<int> b = {2, 7, 26, 25, 19, 17, 1, 90, 3, 36}; 
auto it = b.begin(); 
while (it != b.end()) 
{ 
    std::make_heap(b.begin(), it+1); 
    ++it; 
} 

を同様に有効です。