6. 번 단락 힙정렬예제에서 질문드립니다.
예제 17.14.13.15.16.19.11.18.12 를 힙 트리로 구성하시오.
2레벨과 3레벨 4레벨에서 ... 4레벨 18노드가 위로 올라오고 다시 크기를비교하여 2레벨 3레벨에서
14노드 18노드 16노드간에 대소를 비교하여 교환해주었습니다.
19노드와 13노드도 마찬가지로 교환한걸로 나오구요.
그렇다면 18노드-14노드-16노드간에 크기를 비교해 자리를 바꾸어준것처럼
최종 정답에서 1레벨 19노드, 2레벨 왼쪽 18노드 오른쪽 17노드가
1레벨 19노드..
2레벨 왼쪽 17노드 오른쪽 18노드가 되어야 하는것 아닌가요?
안녕하세요.
힙 정렬은 주어진 값을 전이진 트리로 구성하되 근(부모), 좌(왼쪽자식), 우(오른쪽자식)의 순으로 구성을 합니다.
그런 다음 반대로 아래 자식 노드에서 부모 노드를 비교하면서 큰 값을 위로 올립니다.
이때 순서는 전이진 트리의 반대이므로 우, 좌, 근의 순서가 됩니다. 즉 오른쪽 자식과 부모 비교 -> 왼쪽 자식과 부모 비교
그래서
12와 15 비교
18과 15 비교 - 교환
11과 13 비교
19와 13 비교 - 교환
16과 14 비교 - 교환
18과 16 비교 - 교환
.
.
.
의 순으로 정렬되는 것 입니다.
오늘도 즐거운 하루 되세요.
"-
*2015-01-14 09:13:03
안녕하세요.
힙 정렬은 주어진 값을 전이진 트리로 구성하되 근(부모), 좌(왼쪽자식), 우(오른쪽자식)의 순으로 구성을 합니다.
그런 다음 반대로 아래 자식 노드에서 부모 노드를 비교하면서 큰 값을 위로 올립니다.
이때 순서는 전이진 트리의 반대이므로 우, 좌, 근의 순서가 됩니다. 즉 오른쪽 자식과 부모 비교 -> 왼쪽 자식과 부모 비교
그래서
12와 15 비교
18과 15 비교 - 교환
11과 13 비교
19와 13 비교 - 교환
16과 14 비교 - 교환
18과 16 비교 - 교환
.
.
.
의 순으로 정렬되는 것 입니다.
오늘도 즐거운 하루 되세요.
"