힙이란?
힙은 최댓값이나 최솟값을 빠르게 찾아낼 수 있도록 구현된 완전 이진 트리이다.
완전 이진 트리이기 때문에
- 자식을 최대 2개 (Left child, Right child) 까지 가질 수 있고,
- 마지막 레벨을 제외한 모든 레벨이 다 채워져야 하며,
- 마지막 레벨은 왼쪽에서부터 차례대로 채워져야 한다.
완전 이진 트리 예시
힙의 종류
힙은 다음 조건에 따라 최대 힙(Max Heap), 최소 힙(Min Heap)으로 나눌 수 있다.
- 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 같거나 큰 완전 이진 트리
- 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 같거나 작은 완전 이진 트리
최대 힙, 최소 힙 예시
이로써 알 수 있는 건, 최대 힙에서 루트 노드는 최댓값을 가지고, 최소 힙에선 루트 노드가 최솟값을 가진다.
따라서 힙에서 최댓값이나 최솟값을 접근하는 시간은 O(1)로 매우 빠르다.
다만, 힙에 하나의 원소를 삽입하거나 삭제하는 연산은 힙의 성질을 만족하도록 swap하는 과정이 필요하기 때문에 각각 O(logN)의 시간이 소요된다.
힙의 삽입
구체적으로 어떻게 힙에서 삽입 연산이 이루어지는지 알아보자.
힙은 최대 힙이라고 가정하고, 다음과 같이 최대 힙이 구성되어 있는 상태에서 새로운 원소 10을 삽입한다면
우선은 완전 이진 트리 성질을 만족하기 위해 가장 끝 자리에 새로운 원소 10을 키 값으로 하는 child node를 붙인다.
그 다음 Max Heap 조건을 만족하는지 확인하기 위해 자신의 부모인 4와 대소비교를 한다.
10이 4보다 더 크므로 10과 4를 swap 해준다.
그리고 이 과정을 부모 노드가 없거나, 자신보다 더 큰 값을 가진 부모 노드가 나올 때까지 반복한다. 4와 swap을 한 10이 다시 부모 노드인 7과 비교했을 때 더 크므로, 한 번 더 swap 한다.
마지막으로 9와 비교했을 때 10이 더 크므로 10이 루트 노드로 올라가게 되고, 이 위치가 10이 존재해야 하는 최종적인 위치다.
10과 swap한 노드들의 위치를 봐도 Max Heap 조건을 충족하는 것을 확인할 수 있다.
계속 자신의 부모 노드와 비교하는 과정을 거치기 때문에 삽입 연산의 시간 복잡도는 O(logN)이다.
힙의 삭제
최대 힙에서 삭제 연산이 일어난다면, 루트 노드에 있는 최댓값이 삭제된다.
또한 원소 개수 하나 줄어들면서 완전 이진 트리 조건을 만족해야 하므로 우선 다음과 같이 마지막 원소 값을 루트 노드에 덮어 쓴다.
그 다음 마지막 원소인 3의 위치를 Max Heap 조건을 만족하도록 찾아주기만 하면 된다.
삽입 연산과 다르게 삭제는 가장 위인 루트 노드에서부터 아래로 탐색하는 과정을 거치기 때문에 child node와 비교를 해야 한다.
child node가 2개 라면 그 둘 중 더 큰 값을 가지고 있는 노드와 비교한다.
여기서는 두 자식 노드 중 7이 6보다 크므로 7과 비교를 하고, 이 7이 현재 부모인 3보다 크므로 둘을 swap 해준다.
이 과정 역시 자식 노드가 없거나, 자신보다 더 작은 값을 가진 자식 노드가 나올 때까지 반복된다.
이전 단계와 같은 방식으로 두 자식 노드인 5와 4 중 값이 더 큰 5와 비교를 하고, 5가 3보다 크므로 swap 해준다.
그리고 다음 단계에서 두 자식 노드 중 큰 값을 가진 2와 비교했을 때 현재 부모 노드의 값인 3이 더 크기 때문에 swap은 더이상 일어나지 않고, 최종적인 3의 위치가 정해진다.
삭제 연산 역시 자기보다 더 큰 자식이 존재할 때마다 위 과정을 반복하므로 시간복잡도는 O(logN)이다.
구현
힙은 완전 이진 트리이기 때문에 루트 노드를 시작으로 노드의 값을 배열(Array)을 통해 차례대로 저장할 수 있다.
또한 인덱스 계산을 통해 부모 노드와 자식 노드에 접근할 수 있는데, 만약 인덱스가 0부터 시작하고 현재 노드의 인덱스가 i 라면,
- 부모 노드의 인덱스는 (i-1)/2
- 왼쪽 자식 노드의 인덱스는 2*i+1
- 오른쪽 자식 노드의 인덱스는 2*i+2
가 된다.
그럼 Swift로 Heap을 구현해보겠다. (Swift가 낯설다면 양해 바란다.)
-
위의 예시는 원소가 정수인 Max Heap으로 상황을 가정하였지만, Generic을 사용하여 타입과 관계 없이 범용적인 Heap을 구현해보려 한다.
-
또한, 두 원소를 비교할 때 사용자가 지정한 우선 순위대로 비교가 가능하도록 비교하는 closure를 생성자에서 받도록 한다.
struct Heap<T> {
private var heap: [T]
private let compare: (T, T) -> Bool
var size: Int {
return heap.count
}
var isEmpty: Bool {
return heap.isEmpty
}
init(compare: @escaping (T, T) -> Bool) {
heap = []
self.compare = compare
}
// 이하 생략
}삽입 구현 코드
위의 예시에서는 계속 swap을 해주었지만, 사실 비교는 항상 삽입하려는 원소 값과 이루어지므로, 실제 값을 쓰는 작업은 마지막 최종 위치에 한 번만 해주면 된다.
mutating func insert(_ item: T) {
heap.append(item) // 마지막 위치에 삽입
var current = size - 1
while current > 0 { // 부모 노드가 존재하는 조건
let parent = (current - 1) / 2
if compare(heap[parent], item) { break } // heap 조건을 만족하므로 중단
heap[current] = heap[parent] // 현재 위치에 부모 노드의 값을 대입
current = parent
}
heap[current] = item // 최종 위치에 삽입하려는 원소 값을 대입
}삭제 구현 코드
삭제도 마찬가지로 마지막 원소인 last가 있어야 할 최종 위치에 한 번만 값을 쓰도록 구현할 수 있다.
mutating func remove() -> T? {
if isEmpty { return nil } // 비어있다면 nil return
let last = heap.removeLast()
guard let item = heap.first else { return last } // 원소가 1개인 경우
var current = 0
var child = 1
while child < size { // 자식 노드가 존재하지 않는다면 중단
// 오른쪽 자식 노드가 존재하고, 값의 우선순위가 더 높다면 오른쪽 자식 노드가 비교 대상
if child + 1 < size && compare(heap[child + 1], heap[child]) {
child += 1
}
if compare(last, heap[child]) { break } // heap 조건을 만족하므로 중단
heap[current] = heap[child]
current = child
child = 2 * current + 1
}
heap[current] = last // 마지막 원소의 최종 위치에 값 대입
return item // 제거하려는 원소 return
}테스트
다음과 같이 String 타입의 사전순 힙을 구성한 다음, 순차적으로 remove하여 player들의 이름이 오름차순으로 나오는지 확인해보자.
var heap = Heap<String> { $0 < $1 }
let players = ["Azpilicueta", "Silva", "Kante", "Kovacic", "Pulisic", "Mudryk", "Sterling", "Gallagher"]
for player in players { heap.insert(player) }
while let player = heap.remove() {
print(player)
}
👍🏻
Reference
https://en.wikipedia.org/wiki/Heap_(data_structure)
