힙에 대한 설명은 이전 포스팅을 참고해주세요.
힙의 구현
힙을 구현하는 자료구조는 배열으로, 배열의 첫 번째 인덱스는 사용되지 않는다.
고로 루트 노드는 인덱스 1이고 아래 노드로 내려갈수록 인덱스가 쭉쭉 추가가 된다.
힙에서 부모 노드와 자식 노드 간의 관계
- 왼쪽 자식의 인덱스 = `(부모의 인덱스) * 2`
- 오른쪽 자식의 인덱스 = `(부모의 인덱스) * 2 + 1`
- 부모의 인덱스 = `(자식의 인덱스) / 2`
이 점을 참고해서 구현해보자 - !
기본 틀
`Comparable` 프로토콜을 채택하여 비교가 가능한 데이터 타입을 받도록 구조체를 생성한다.
struct Heap<T: Comparable> {
private var heap: [T] = []
private let comparer: (T,T) -> (Bool)
init(comparer: @escaping (T,T) -> Bool) {
self.comparer = comparer
}
}`comparer` 상수로 최소 힙과 최대 힙을 한 번에 구현했다.
두 T 타입의 값을 비교하여 조건이 일치하면 `true`, 일치하지 않으면 `false`를 반환한다.
예를 들어, 힙을 생성할 때 `Heap(comparer: <)`와 같이 생성하며, 이 경우에는 두 T 타입의 값 중 앞의 값이 더 작으면 true를 반환한다.
힙의 삽입
힙에 데이터를 삽입하는 과정을 간단히 설명해보자면,
1. 힙의 가장 마지막에 데이터를 삽입하고
2. 삽입한 노드와 부모 노드를 비교해서
3. 힙의 성질을 만족할 때까지 두 노드를 `swap` 한다.
이를 구현해보면
1-1 먼저 `heap`에 요소가 없다면, `data`를 두 번 `append`한다.
두 번인 이유는 힙은 0번 인덱스를 사용하지 않고, 1번부터 사용하므로 0번 인덱스에 임의의 아무값이나 넣은 것이다.
1-2 `heap`에 요소가 있다면, `data`를 한 번 `append`한다.
2. `siftUp()` 함수로 삽입한 `data`의 위치를 조정한다.
mutating func insert(data: T) {
// 0번 인덱스는 사용하지 않으므로 임의의 값 하나 삽입
if heap.isEmpty {
heap.append(data)
heap.append(data)
return
}
heap.append(data)
// data 위치 이동
siftUp(index: heap.count - 1)
}
매개변수로 받은 `index`는 위치를 조정할 `data`의 인덱스이다. 가장 끝에 삽입한 `data`를 조정하는 것이니 위의 `insert()` 함수에서 heap의 가장 마지막 인덱스를 넣은 것이다.
3-1. `index > 1` -> 인덱스가 1보다 커야 위로 올라갈 노드가 있다
3-2. `comparer(현재 노드, 부모 노드)` -> 현재 노드와 부모 노드 값을 비교했을 때 조건이 일치하면 true
4. 위 두 가지를 만족한다면 `index(현재 노드)`와 `index/2(부모 노드)`를 `swap`한 후 `index`를 업데이트 한다.
5. 힙의 성질을 만족할때까지 4번(`swap`)을 반복한다.
mutating func siftUp(index: Int) {
var index = index
// index가 1 이하라면 더이상 부모 노드가 없다
// 현재 노드와 부모 노드의 값을 비교하여 swap 반복
while index > 1 && comparer(heap[index], heap[index/2]) {
heap.swapAt(index, index/2)
index /= 2
}
}
이렇게 하면 힙의 성질을 유지하며 데이터를 삽입할 수 있다.
힙의 삭제
힙에서 데이터를 삭제하는 과정도 간단히 말하자면
1. 힙의 루트 노드를 삭제한다.
2. 힙의 가장 마지막에 있는 노드를 루트 노드로 가져온다.
3. 루트 노드로 가져온 노드의 값과 그 자식 값을 비교하여 힙의 성질을 만족할 때까지 두 노드의 위치를 바꾼다.
이를 실제로 구현할 때
루트 노드를 먼저 삭제하는 것이 아니라, 마지막 노드를 루트 노드와 먼저 위치를 바꾼 후에 마지막 위치로 이동한 루트 노드를 삭제해준다.
1. 루트 노드와 마지막 노드를 `swap`한다.
2. `heap`의 마지막 요소를 `remove`한다.
3. `siftDown()` 함수로 루트 노드로 이동한 데이터의 위치를 조정한다.
mutating func pop() -> T? {
// heap count가 2 이상이어야 pop 가능
if heap.count < 2 { return nil }
// 루트 노드와 마지막 노드를 swap
heap.swapAt(1, heap.count - 1)
// 마지막 노드를 remove (즉, 기존 루트 노드)
let deletedData = heap.removeLast()
// 1번으로 이동한 노드를 다시 자식 노드와 비교하여 아래로 이동
siftDown(index: 1)
return deletedData
}
`siftDown()`이 처음 호출됐을 때 들어온 `index`는 1이다. 해당 노드를 기준으로 왼쪽, 오른쪽 자식 노드의 인덱스를 저장한다.
1-1. `child`가 `heap`의 마지막 `endIndex`보다 작을 때
1-2. 자식 노드와 현재 노드 값을 비교해서 조건이 일치하면 `true`
위 조건을 만족하면 `swapIndex`를 자식 노드의 인덱스로 바꾼다.
왼쪽 자식 노드와 오른쪽 자식 노드를 똑같이 검사하고 `swapIndex`가 업데이트 되었다면 두 노드를 `swap`을 한다.
그럼 이제 바뀐 위치를 기준으로 `siftDown()`을 다시 진행한다.
mutating func siftDown(index: Int) {
var swapIndex = index
let leftChild = index * 2
let rightChild = index * 2 + 1
// leftChild, rightChild가 heap.endIndex보다 크거나 같다면 자식 노드가 더이상 없음
// 현재 노드와 자식 노드 값을 비교하여 swap할지 결정
if leftChild < heap.endIndex && comparer(heap[leftChild], heap[swapIndex]) {
swapIndex = leftChild
}
if rightChild < heap.endIndex && comparer(heap[rightChild], heap[swapIndex]) {
swapIndex = rightChild
}
// swapIndex가 index와 같다면 swap 안함
// 다르다면 swap
if swapIndex != index {
heap.swapAt(swapIndex, index)
// swap한 위치를 기준으로 다시 체크
siftDown(index: swapIndex)
}
}
이렇게 `pop()`까지 완료했다!
전체 코드
struct Heap<T: Comparable> {
private var heap: [T] = []
private let comparer: (T,T) -> (Bool)
var count: Int {
return heap.count
}
init(comparer: @escaping (T,T) -> Bool) {
self.comparer = comparer
}
mutating func insert(data: T) {
// 0번 인덱스는 사용하지 않으므로 임의의 값 하나 삽입
if heap.isEmpty {
heap.append(data)
heap.append(data)
return
}
heap.append(data)
// data 위치 이동
siftUp(index: heap.count - 1)
}
mutating func siftUp(index: Int) {
var index = index
// index가 1 이하라면 더이상 부모 노드가 없다
// 현재 노드와 부모 노드의 값을 비교하여 swap 반복
while index > 1 && comparer(heap[index], heap[index/2]) {
heap.swapAt(index, index/2)
index /= 2
}
}
mutating func siftDown(index: Int) {
var swapIndex = index
let leftChild = index * 2
let rightChild = index * 2 + 1
// leftChild, rightChild가 heap.endIndex보다 크거나 같다면 자식 노드가 더이상 없음
// 현재 노드와 자식 노드 값을 비교하여 swap할지 결정
if leftChild < heap.endIndex && comparer(heap[leftChild], heap[swapIndex]) {
swapIndex = leftChild
}
if rightChild < heap.endIndex && comparer(heap[rightChild], heap[swapIndex]) {
swapIndex = rightChild
}
// swapIndex가 index와 같다면 swap 안함
// 다르다면 swap
if swapIndex != index {
heap.swapAt(swapIndex, index)
// swap한 위치를 기준으로 다시 체크
siftDown(index: swapIndex)
}
}
// 루트 노드를 삭제
mutating func pop() -> T? {
// heap count가 2 이상이어야 pop 가능
if heap.count < 2 { return nil }
// 루트 노드와 마지막 노드를 swap
heap.swapAt(1, heap.count - 1)
// 마지막 노드를 remove (즉, 기존 루트 노드)
let deletedData = heap.removeLast()
// 1번으로 이동한 노드를 다시 자식 노드와 비교하여 아래로 이동
siftDown(index: 1)
return deletedData
}
}
// 최소 힙 & 최대 힙 사용
let minHeap: Heap<Int> = Heap(comparer: <)
let maxHeap: Heap<Int> = Heap(comparer: >)
여러 블로그들을 참고하며 공부를 하면서 쉽게 이해하기가 어려웠어서 최대한 풀어 쓰려고 했는데 막상 쓰고보니 쉽게 이해하긴 힘들 것 같다 ..ㅎㅎ
