[자료구조, Swift] 힙(Heap) 구현하기

Swift같은 개발 언어 중에는 힙, 큐, 덱같이 기본적으로 다른 언어에서 제공해주는 라이브러리가 따로 있지 않다. 따라서 직접 구현해줘야 한다.

---

알아야 될 것

1. 완전 이진트리로 부모 노드를 탐색하려면, 시작 인덱스를 1부터 시작해야 한다.

2. 힙은 우선순위 큐를 위한 자료형이다.

3. 우선순위 큐의 목적은 값을 추가할 때 부모 노드에 최댓값 or 최솟값을 넣기 위함이다.

4. 따라서 입, 출력을 할 때만 연산이 수행되고, 전체 힙의 값을 확인하면 오름차순이나 내림차순으로 정렬되지 않을 수 있다.

---

struct Heap {
    var heap: Array<Int> = []
    
    // 초기화 1. 아무 것도 넣지 않을 때
    init() { }
    
    // 초기화 2. 시작부터 넣을 때
    init(_ data: [Int]) {
        heap.append(0)
        heap += data
    }
    
    // 더하기, 해당 값이 최대일 때 idx 1에 도달, 아닐 때는 중간에 멈춤
    mutating func add(_ i: Int) {
        heap.append(i)
        var idx = heap.count - 1
        while idx > 1 && heap[idx] > heap[idx/2] {
            heap.swapAt(idx, idx/2)
            idx /= 2
        }
    }
    
    // 빼기, 최댓값을 마지막값과 swap후 삭제 + idx 1 요소만 정렬
    mutating func delete() {
        if heap.count <= 1 {
            print(0) // 힙이 비어 있으면 0을 로그에 출력(선택 사항)
            return
        }
        
        heap.swapAt(1, heap.count - 1)
        print(heap.removeLast()) // 삭제 값 출력(선택 사항)
        sort(1)
    }
    
    // 정렬
    mutating func sort(_ i: Int) {
        var root = i
        let left = i * 2
        let right = i * 2 + 1
        
        // 완전 이진 트리이므로, 자식 노드의 왼쪽부터 판단
        if left < heap.count && heap[left] > heap[root] {
            root = left
        }
        
        // 오른쪽 자식 노드가 있으면 왼쪽 노드와 비교
        if right < heap.count && heap[right] > heap[root] && heap[right] > heap[left] {
            root = right
        }
        
        // 바꿀 경우가 없을 때(이미 최대일 때)를 제외하고는 재귀로 해당 함수 반복
        if i != root {
            heap.swapAt(i, root)
            sort(root)
        }
    }
}