상향식 코드


#include


int number = 9;

int heap[9] = {7,6,5,8,3,5,9,1,6};


int main(void){

// 먼저 전체 트리 구조를 최대 힙 구조로 바꿉니다. 

for(int i = 1; i

int c = i;

do{

int root = (c-1) / 2;

if(heap[root]

int temp = heap[root];

heap[root] = heap[c];

heap[c] = temp;

}

c = root;

}  

while(c != 0); 

}

// 크기를 줄여가면서 반복적으로 힙을 구성

for(int i = number - 1; i>=0;i--){

int temp = heap[0];

heap[0] = heap[i];

heap[i] = temp; 

int root = 0;

int c = 1;

do{

c = 2 * root + 1;

// 자식 중에 더 큰 값을 찾기

if(heap[c]

c++;

} 

// 루트보다 자식이 더 크다면 교환

if(heap[root]

int temp = heap[root];

heap[root] = heap[c];

heap[c] = temp;

  } 

  root = c;

}

while(c

} 

for(int i = 0; i

printf("%d ",heap[i]);

}

}


하향식 코드


#include

#include


using namespace std;


int number;

int heap[1000001];


void heapify(int i) {

// 왼쪽 자식 노드를 가리킵니다. 

int c = 2 * i + 1;

// 오른쪽 자식 노드가 있고, 왼쪽 자식노드보다 크다면 

if(c

c++;

}

// 부모보다 자식이 더 크다면 위치를 교환합니다. 

if(heap[i]

int temp = heap[i];

heap[i] = heap[c];

heap[c] = temp;

} 

// number / 2까지만 수행하면 됩니다. 

if(c <= number / 2) heapify(c);

}


int main(void) {

cin >> number;

for(int i = 0; i

int x;

cin >> heap[i];

}

// 힙을 생성합니다. 

for(int i = number / 2; i >= 0; i--) {

heapify(i);

}

// 정렬을 수행합니다. 

for (int i = number - 1; i >= 0; i--) { 

for(int j = 0; j

cout <

}

cout << '\n';

int temp = heap[0];

heap[0] = heap[i];

heap[i] = temp;

int root = 0;

int c = 1;

do {

c = 2 * root + 1;

if(c

if(c

temp = heap[root];

heap[root] = heap[c];

heap[c] = temp;

}

root = c;

} while (c

}

}


코드 상으로는 약간의 차이가 있으나 실질적인 결과는 같더라구요 그래서 문득 의문이 듭니다. 왜 굳이 상향식 하향식을 나누는 것이며 무슨 차이가 존재하는 지..