트리는 데이터들을 관리할 때 나무모양처럼 맨위 Root라는 최상위 계층부터 밑에있는 하위 계층까지 펼쳐지는 모양이라서 트리라는 이름이 붙여졌으며, 가장 큰 특징은 위에있는 하나의 노드밑에 또 다른노드가 추가가 된다면, 하나의 노드는 부모가되고 추가된 노드는 자식노드라 부른다. 이 자식노드는 부모노드보다 값이 커야하는 특성을 가지고 힙 정렬을 구현할 수 있다.
쉽게 연결리스트로 구현할 수 있으나, 힙 정렬에서 사용 할 트리는 왼쪽부터 차례로 쌓아가며 최대 두개의 노드를 가질 수 있는 이진트리(Binary Tree)라는것이라 가정하에 정렬을 하므로 연결리스트를 사용하지 않고 구현하도록 하겠다.
힙 정렬 구현은 밑의 3가지 방법을 잘 이용하면 된다.
(1) 입력받은 N개의 값들을 힙의 특징인 트리구조로 변환시키기.
(2) 루트 노드부터 차례로 데이터를 뽑아서 최하위 노드와 값을 바꾸기.
(3) 정렬이 되기 전까지 과정(2)에서의 위치가 바뀐 root노드를 제외하고 과정(1)부터
반복 수행하기.
간단히 말해, 전체 데이터의 갯수 N개를 트리구조로 만들어주고 루트를 최하위 노드와 위치를 바꿔주고, N(정렬 할 값의 크기)-(과정1,2,3을)반복횟수만큼 다시과정(1)부터 시작해 과정(3)까지 실행한다면, 힙 정렬이 완성된다.
ex) 힙 정렬 (1) 힙 만들기 A = { 4, 7, 2, 5, 9, 3, 1 }
" 각 과정은 " A배열 갯수 / 2 " 에 해당하는 A배열의 위치를 기준으로 힙의 형태가
완성되며, 각 힙에서 자식노드와 부모노드의 위치를 바꿀 시 자식노드를 기준으로
재귀호출을 하도록 해야함.(위치가 변환했을경우, 부모노드가 자식노드보다 커야 하는
트리의 형태를 유지하기 위해서) "
트리의 형태를 유지하기 위해서) "
▶시작 전 [ 4, 7, 2, 5, 9, 3, 1 ]
 |
| 트리 구조 만족 X |
▶1회 과정 (기준 : 3번째) // 전체 0~6개 이므로 6 / 2 = 3 이 기준이 됨.
 |
| 자식노드가 존재하지 않으므로 변화 X |
▶2회 과정 (기준 : 2번째)
 |
| 노드 2번째를 기준으로 값이 작은 자식노드가 존재하므로 위치 바꾸기 |
▼
 |
| 위치가 바뀐 노드(값 : 2)를 기준으로 자식노드가 존재하지 않으므로 재귀 X |
▶3회 과정 (기준 : 1번째)
 |
| 노드 1번째를 기준으로 값이 작은 자식노드가 존재하므로 위치 바꾸기 |
▼
 |
| 위치가 바뀐 노드(값 : 7)를 기준으로 자식노드가 존재하지 않으므로 재귀 X |
▶4회 과정 (기준 : 0번째)
 |
| 노드 0번째를 기준으로 값이 작은 자식노드가 존재하므로 위치 바꾸기 |
▼
 |
| 위치가 바뀐 노드(값 : 4)를 기준으로 자식노드가 존재하므로 자식과 크기비교(재귀호출) |
▼
 | |
|
 |
| 힙을 만들기 완료 하지만 정렬되지 않음 |
위의 예시를 통해서 부모노드가 자식노드보다 크다는 특성을 만족하도록 트리를 만들어 보았다. 여기서 최상단에 존재하는 루트(부모노드)에서부터 자식노드들 중 값이 가장 작은것을 뽑아내서 뒤에 노드들과 차례로 위치를 교환시키면 정렬을 만들 수 있다.
위의 예시를 이어서 정렬시켜보자.
ex) 힙 정렬 (2) 정렬 (루트와 자식노드와의 교환방식)
▶정렬 전 : { 1, 5, 2, 7, 9, 3, 4 }
|
| 트리의구조는 만족하지만, 정렬이되어 있지않음 |
▶1회 과정 (기준 : 6번째)
 |
| 최상단의 노드(루트)와 6번째의 위치를 교환 |
 |
| 힙의 구조로 다시 변환시키기(1) |
 |
| 힙의 구조로 다시 변환시키기(2) |
▶2회 과정 (기준 : 5번째)
 |
| 최상단의 노드(루트)와 5번째의 위치를 교환 |
 |
| 힙의 구조로 다시 변환시키기(1) |
: 노드 2번째의 값 4의 자식노드가 존재하지 않으므로 힙 특성 만족
▶3회 과정 (기준 : 4번째)
 |
| 최상단의 노드(루트)와 4번째의 위치를 교환 |
 |
| 힙의 구조로 다시 변환시키기(1) |
▶4회 과정 (기준 : 3번째)
 |
| 최상단의 노드(루트)와 3번째의 위치를 교환 |
 |
| 힙의 구조로 다시 변환시키기(1) |
: 노드 1번째의 값 7의 자식노드가 존재하지 않으므로 힙 특성 만족
▶5회 과정 (기준 : 2번째)
 |
| 최상단의 노드(루트)와 2번째의 위치를 교환 |
 |
| 힙의 구조로 다시 변환시키기(1) |
▶6회 과정 (기준 : 1번째)
 |
| 최상단의 노드(루트)와 1번째의 위치를 교환 |
 |
| 힙 정렬 완료 |
: A = { 9, 7, 5, 4, 3, 2, 1 };
위의 예시 2가지(힙 만들기, 정렬시키기)를 통해서 힙 정렬을 만들어 보았다.
그림에서는 트리의 특징(부모노드 값 < 자식노드 값)을 이용한다면 힙 정렬을 만들 수 있다는 것을
알 수 있다.
힙 정렬의 수행시간을 알아보자.
힙 정렬을 만들때 가장 중요한 특징 두 가지를 보면,
1) 힙을 만드는 수행시간 ▶ log n에 비례
: 힙을 만들때 절반[전체 크기 / 2]의 원소 갯수만큼 트리 특성에 맞도록 구현함.
2) 정렬을 시켜주는 수행시간 ▶ n에 비례
: 정렬 시 전체크기-1 만큼 정렬과정이 필요한데, 이때 루트노드(최상단노드)와의 자리를 바꾸는 정렬과정이 발생할때에 (1의 과정을)재귀 호출하여 다시한번 힙을 만족시켜야 하는 과정이 필요함.
병합, 퀵 정렬과 마찬가지로 힙 정렬또한 평균수행시간은 n log n이라는것을 알 수 있다.
알고리즘을 살펴보면,
▶실행 결과
굿
답글삭제굿
답글삭제