최대 힙 배열 표현

Question

최대 힙을 만들려고합니다. 논리가 간단합니다. 부모가 자식 노드 중 하나보다 작 으면이를 바꿉니다. I 제가

 
     90 
     36 17 
    25 26 7 1 
2 3 19 

그렇게 배열 표현 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()); 

모두 결과 :

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; 
} 

그러나, 어떤 코드가하는 일은이에 상응하는 힙에 preinserts 모든 요소를, 그리고 다음을 주선 똑같이 유효합니다.