힙은 자료구조 중 하나로, 완전 이진 트리 구조이다.
힙의 높이는 루트에서 가장 깊은 리프노드까지의 경로를 나타낸다.
힙은 배열 A[1...n]으로 저장될 수 있으며,
- 트리의 루트는 A[1] 이다.
- A[i]의 부모는 A[i/2] 이다.
- A[i]의 왼쪽 자식은 A[2i]이고, 오른쪽 자식은 A[2i + 1]이다.
- 이진 표시의 구현은 컴퓨팅이 빠르다.
가장 큰 요소가 루트에 존재하는 max-heaps는, 루트를 포함한 모든 노드 i에 대해 A[Parent(i)] $\geq$ A[i]이다.
가장 작은 요소가 루트에 존재하는 min-heaps는, 루트를 포함한 모든 노드 i에 대해 A[Parent(i) $\leq$ A[i]이다.
힙정렬 알고리즘은 max-heaps를 사용하며, 힙은 이진트리가 아니라 k트리도 가능하다.
방금 설명한 max-heaps의 속성을 유지하도록 하는 알고리즘이 MAX-HEAPIFY 알고리즘이다.
Max-heapify 이전에는 A[i]는 자식보다 작은 값을 가지고, 하위트리들은 최대 힙 속성을 모두 만족하고 있다.
Max-heapigy 이후에는 인덱스 i를 루트로 하는 서브트리가 최대 힙 속성을 만족할 것이다.
l에 왼쪽 자식의 인덱스 값을 넣고, r에 오른쪽 자식의 인덱스 값을 넣은 후에 먼저 A[l]과 A[i]를 비교한다.
더 큰 요소의 인덱스 값을 largest에 넣어준다.
또 A[largest]와 A[r]의 값을 비교한다. 더 큰 요소의 인덱스 값을 largest에 넣어준다.
만약 largest의 값이 i가 아니라면, A[i]와 A[largest]를 교환해준다.
이렇게 교환한 후에도, 교환된 자식 노드를 루트로 하는 서브트리에서도 최대 힙 속성이 만족되어야하기 때문에 재귀적으로 작동한다.
Max-heapify의 시간 복잡도는 $O(\lg{n})$이다.
배열 A의 길이를 heap-size[A]라고 했을 때, i가 배열의 길이를 2로 나눈 값에서 1까지 Max-heapify 알고리즘을 반복한다.
왜 2로 나눈값으로 반복하냐면, 그 이후의 인덱스를 가진 노드는 리프노드이기 때문이다. 리프 노드는 자식 노드가 없으니, 알고리즘을 사용할 필요가 없다.
위 예시를 보면, 인덱스 6이후의 노드들은 리프 노드인 것을 확인할 수 있다.
Max-Heapify 알고리즘을 호출하는 Build-max-heap 알고리즘의 시간복잡도는 $O(n\ln{n})$이다.
Heapsort Algorithm
위에서 힙을 만드는 알고리즘들에 대해서 배웠다.
이제는 만들어진 힙으로 정렬을 하는 알고리즘에 대해 알아볼 것이다.
주어진 입력 배열로 max-heap을 구축한다. (build-max-heap algorithm)
루트에서 시작해서, 최대 요소를 배열에서 올바른 위치에 배열한다. 루트는 제일 큰 수 일테니, 배열의 맨 마지막 요소와 최대 요소를 교환한다.
이 루트 노드는 배열에서 올바른 위치에 있다고 인식하고, 노드를 제거한다. 후에 다시 max-heapify를 호출해 최대 힙 속성을 복구한다.
노드의 제거 과정은 하나의 노드가 남을 때까지 반복되며, 이는 가장 작은 요소일 것이다. 이 요소는 이미 배열에서 정렬된 위치에 있을 것이며, 주어진 입력 배열의 정렬은 완료된다.
Heapsrot의 시간복잡도 역시 $O(n\lg{n})$이다.
Priority Queue: 우선순위 큐
힙을 사용하여 우선순위 큐를 구현할 수 있다.
힙 구조는 우선순위 큐를 효율적으로 구현하는데 적합한 자료구조이며, 최대 힙은 최대 우선순위 큐를 구현할 수 있다. 즉, 우선순위가 가장 높은 요소는 가장 큰 요소이며, 제일 먼저 처리된다.
힙이 효율적인 이유는, 삽입과 추출간에 균형을 잘 맞춘 자료구조이기 때문이다. 삽입이 빠르면서 추출이 느리거나, 추출이 빠르면서 삽입이 느리거나 하지 않고 둘 다 효율적인 속도를 보장한다는 것이다. 삽입과 추출 연산 모두 $O(\lg{n})$의 시간 복잡도를 가진다.
우선순위 큐는 동적 집합 S의 요소들을 유지하고 관리하는 자료구조다. 각 요소는 우선순위를 나타내는 key값을 가진다.
또한, 우선순위 큐는 요소들을 비교하는 특정 방식에 따라 가장 높은 우선순위에 접근하거나 제거할 수 있다.
최대 우선순위 큐는 다음과 같은 동적 집합 연산을 지원한다.
- INSERT(S, x): 요소 x를 우선순위 큐 S에 추가한다.
- MAXIMUM(S): 집합 S에서 가장 큰 키 값을 가진 요소를 반환한다. (제거가 아님)
- EXTRACT-MAS(S): 집합 S에서 가장 큰 키 값을 가진 요소를 제거하고 반환한다.
- INXREASE-KEY(S, x, k): 요소 x의 키 값을 k로 증가시킨다. 이때 k는 현재 x의 값보다 크거나 같다고 가정한다.
최대 우선순위 큐는 공유 컴퓨터에서 작업을 스케줄링할 때 사용된다.
Heap-Maximum
루트의 값을 가져오기만 하면 되기 때문에 $\Theta(1)$의 시간복잡도를 가진다.
Heap-Extract-Max
배열 A가 주어졌을 때, 힙이 비어있지 않은지 먼저 확인한다.
최댓값(루트)를 복사하고, 트리의 마지막 노드를 새로운 루트로 설정한다.
마지막 노드를 루트로 설정함으로써 힙이 깨졌으니, 힙 성질을 다시 맞추기 위해 재졍렬을 한다.
마지막으로 최댓값을 반환한다.
Max-Heapify의 실행 시간이 있으므로, 시간복잡도는 $O(\lg{n})$이 된다.
Heap-Increase-Key
노드의 값을 증가시키는 알고리즘이기 때문에, key 값이 현재 노드의 크기보다 작으면 에러가 발생한다.
key값을 노드에 적용시키고, 부모 노드가 더 작다면 교환한다. 이제 인덱스를 부모 노드의 인덱스로 바꾼 후에, 비교를 반복한다.
트리를 타고 올라가면서 힙 성질을 맞추게 된다.
최악의 경우, 매번 교환을 하며 루트까지 올라가야하므로, 시간복잡도는 트리의 높이인 $O(\lg{n})$이 된다.
Max-Heap-Insert
주어진 key값을 힙에 삽입하는 것이다.
먼저 힙의 맨 마지막에 새로운 노드를 생성한 후에, $-\infty$ 값을 넣어준다.
Heap-Increase-Key를 통해 $-\infty$값을 key값으로 증가시켜준다.
Heap-Increase-Key 알고리즘의 실행 시간이 있으므로, $O(\lg{n})$의 시간복잡도를 가진다.
** 대학교 수업을 듣고 이해한 부분을 최대한 풀어서 작성한 글입니다.
틀린 정보가 존재할 수 있으며, 언제나 피드백은 환영입니다. **
'DKU > 알고리즘 및 실습' 카테고리의 다른 글
| Sorting in Linear Time (0) | 2024.11.01 |
|---|---|
| Quick Sort Algorithm (1) | 2024.10.16 |
| Recurrences (0) | 2024.10.08 |
| Bubble Sort Algorithm (0) | 2024.10.03 |
| Growth of Functions (0) | 2024.09.26 |