저번 시간에 알고리즘의 뜻을 말했는데요. 대충 문제 해결 방식입니다.
그럼 자료구조는 뭘까요? 자료 구조는 이름 그대로 자료의 구조. 즉 자료를 담는 방법입니다.
그 중 힙은 정렬, 우선순위 큐 넘버 지정, 스케줄링 등에 활용되는 자료구조입니다.
한번 힙에대해서 알아봅시다.
힙은 각 노드가 일부 값으로 구성되는 거의 완전한 이진 트리입니다.
이진 트리에 대해서는 아래 사진 참고하시면 됩니다.
루트 - 젤 위 부모 노드
리프 - 젤 아래 더이상 자식 노드가 없는 노드
정도만 유의하시면 될것같네요
힙의 특징
힙의 이진 트리에서는 다음의 특징을 가집니다.
힙 속성 : 일부 노드 N의 값(수치)은 N의 두 하위 노드 값(수치)보다 크거나 같습니다.
사진에서는 큰 부모노드 1의 값 16은 자식 노드 2 3의 각각 14와 10보다 크거나 같습니다.
노드의 높이 = 노드에서 리프까지 내려가는 길중 가장 긴 단순한 가장자리의 길의 수입니다.
사진에서는 16 -> 14 -> 8 -> 2, 길의 간선이 3개니깐 높이가 3 되겠네요.
힙의 높이 = 루트 높이 = Θ(lg n), 여기서 n은 트리의 노드 수입니다.
루트(레벨0)~레벨3까지 총 높이가 3이 되겠네요.
힙에는 두가지 종류가 있습니다.
MAX-HEAPIFY 상태와 MIN-HEAPIFY 상태가 있습니다.
최대힙과 최소힙이라하는데 각각 루트노드가 젤 크냐 작냐의 차이입니다.
예시
MAX-HEAPIFY
MAX-HEAPIFY는 max-heap 속성을 만드는데 사용됩니다.
MAX-HEAPIFY 가 적용된 상태 이전에는 A[i]가 자식보다 작을 수 있습니다.
즉 최대힙 상태로 정렬이 안된상태죠. 이걸 정렬해봅시다.
i는 지금 현재 처리중인 노드 인덱스입니다.
i를 루트로하는 왼쪽 및 오른쪽 하위 트리가 최대 힙이라고 가정합니다.
MAX_HEAPIFY를 한 뒤에도 i를 루트로 하는 하위 트리는 최대 힙이어야합니다.
그럼 MAX_HEAPIFY를 해봅시다.
A[i ], A[LEFT(i )] 및 A[RIGHT(i )]를 비교합니다.
만약 비교했을 때 A[i]가 하위 항목 둘 중 하나보다 더 작다면 A[i ]를 두 하위 항목 중 더 큰 항목으로 교환하여 힙 속성을 유지합니다.
i에 루트가 있는 하위 트리가 최대 힙이 될 때까지 힙을 비교하고 교체하는 이 프로세스를 계속합니다.
리프에 도달하면 리프에 뿌리를 둔 하위 트리는 간단하게 최대 힙입니다.
의사 코드로 보면 위와같이 되겠습니다.
최대 힙 만드는 법 Build-Max-HEAP
앞선 MAX-HEAP으로 최대힙을 만드는게 우리의 목표입니다.
나중에 이 최대힙으로 힙 정렬을 할 것이기 때문에 중요합니다.
최대힙 만드는 과정이 올바르려면 다음의 전제가 있어야합니다.
위에서 다뤘던 MAX-HEAPIFY에서 잠깐 얘기 나온 i의 성질 등 그런겁니다.
1. 루프 불변식 (Loop invariant):
매 반복 시작 시, i+1부터 n까지의 모든 노드가 최대 힙의 루트입니다.
이는 i 이후의 모든 노드가 이미 최대 힙 속성을 만족한다는 의미입니다.
2. 초기화 (Initialization):
[n/2]+1부터 n까지의 노드는 모두 리프 노드입니다.
리프 노드는 자식이 없으므로 자체로 사소한(trivial) 최대 힙입니다.
첫 반복 전 i=[n/2]이므로, 초기 상태에서 불변식이 성립합니다.
3. 유지 (Maintenance):
i 노드의 자식들은 i보다 큰 인덱스를 가집니다.
불변식에 따라, i의 자식들은 이미 최대 힙의 루트입니다.
MAX-HEAPIFY는 i 노드를 최대 힙의 루트로 만듭니다.
i를 감소시키면 다음 반복에서도 불변식이 유지됩니다.
4. 종료 (Termination):
i가 0이 되면 루프가 종료됩니다.
이때 불변식에 의해 모든 노드(특히 루트인 1번 노드)가 최대 힙의 루트가 됩니다.
이제 이 MAX-HEAPIFY로 최대 힙을 만들어봅시다.
MAX-HEAPIFY 시행하기 전부터 이미 최대힙으로 정렬되어있는 힙 노드들을 Primitive Max-heaps라고 합니다.
나머질 정렬해야하니 빨간색 선 순서대로 MAX-HEAPIFY가 진행되는데요.
이렇게 위에서부터 i가 하위 항목보다 작다면 내려가서 하나씩 정렬되고 반복해서 다 정렬될까지 최대힙을 만듭니다.
힙 정렬 HEAP SORT
이제 잘 정렬된 최대힙을 통해 힙 정렬을 해봅시다.
힙 정렬은 결국 힙 자료구조를 이용해서 배열을 정렬하는 알고리즘입니다.
루트 노드와 마지막 노드를 교환해서 루트 노드를 하나씩 배열에 넣어줍니다.
그럼 정렬된 배열이 나오겠죠?
그리고 교환하고 나면 트리가 최대힙이 성립 안될 수도 있습니다.
이 경우 다시 최대힙이 되도록 MAX-HEAPIFY를 해줘야합니다.
사진을 천천히 둘러보며 집중하시기 바랍니다.
처음 (a)에서 가장 큰 루트노드는 16이고 리프노드는 2 4 1이렇게 있습니다.
이중 가장 마지막 노드인 리프노드 1와 루트노드 16을 교환해주면 됩니다.
교환했을 때 1이 루트노드인데 최대힙이 성립 안되므로 다시 최대힙이 되도록 MAX-HEAPIFY를 해주면
(b)가 나오게 됩니다. 이과정을 반복하는 것이죠
배열로 보면 이렇게 왼쪽 배열이 오른쪽으로 최대힙으로 정렬된 결과를 볼 수 있습니다.
이렇게 MAX-HEAPIFY 정렬되어있는 최대힙을 계속 정렬하면 큰 수 부터 순서대로 정렬된 배열을 얻게됩니다.
오늘 배운걸 한번 사진으로 정리해보았습니다. 도움이 되셨으면 좋겠네요.
'그냥 개발글 > 알고리즘' 카테고리의 다른 글
| 퀵 정렬 Quick Sort (1) | 2024.10.19 |
|---|---|
| 우선순위 큐 Priority Queues (0) | 2024.10.19 |
| 숫자 정렬 알고리즘 Sorting of Numbers (0) | 2024.10.19 |
| 복잡한 교차로를 위한 신호등 설계 알고리즘 (1) | 2024.10.15 |