스위프트 | "(최소)힙 구현"하기 (Swift5 | Heap - MinHeap)

 

 

코테알고리즘 공부를 하던 중, 백준 1927번을 풀기 위해선 최소힙(MinHeap) 구현이 필요했습니다.

Swift엔 힙이 없습니다.

물론 큐, 덱, 순열, 조합 등등 다 없습니다... 

 

---

최대 힙에 대해선 아래 링크에서 확인하실 수 있습니다.

https://developer-p.tistory.com/196

백준 Swift 최소 힙, 최대 힙, 절댓값 힙 (백준 Swift 1927번, 11279번, 11286번)

 

 

https://developer-p.tistory.com/146

스위프트 | "스택, 큐, 덱 구현"하기 (Swift5 | Stack, Queue, Deque)

 

https://developer-p.tistory.com/145

스위프트 | "순열과 조합 구현"하기 (Swift5 | Permutation, Combination)

 

---

 

최소 힙(MinHeap)

뭔가 구현이 어려워 보여 미루다가 설명이 잘 되어 있는 글을 보고 공부했습니다.

아래는 위 글의 코드(수정)이고, 부연 설명도 잘 되어 있으니 꼭 한 번 읽어보시길 추천드립니다.

 

매번 찾기엔 번거로워,

최소 힙과 관련된 문제가 나올 때 유용할만한 코드를 남겨둡니다.

(위 설명 글에 있는 코드 및 주석부분이 잘못된 게 있어 수정했습니다.)

 

최소 힙(MinHeap) 구현

(오류 수정됨.)

백준 1927번 반례 추가.

// MARK: - MinHeap
import Foundation

struct MinHeap<T: Comparable> {
    var heap: [T] = []
    
    var isEmpty: Bool {
        return heap.count <= 1 ? true : false
    }
    
    init() {}
    init(_ element: T) {
        heap.append(element) // 0번 index채우기 용
        heap.append(element) // 실제 Root Node 채움.
    }
    
    mutating func insert(_ element: T) {
        if heap.isEmpty {
            heap.append(element)
            heap.append(element)
            return
        }
        heap.append(element)
        
        func isMoveUp(_ insertIndex: Int) -> Bool {
            if insertIndex <= 1 { // Root Node일 때,
                return false
            }
            let parentIndex = insertIndex / 2
            return heap[insertIndex] < heap[parentIndex] ? true : false
        }
        
        var insertIndex = heap.count - 1
        while isMoveUp(insertIndex) {
            let parentIndex = insertIndex / 2
            heap.swapAt(insertIndex, parentIndex)
            insertIndex = parentIndex
        }
    }
    
    enum moveDownStatus { case left, right, none }
    
    mutating func pop() -> T? {
        if heap.count <= 1 {
            return nil
        }
        let returnData = heap[1]
        heap.swapAt(1, heap.count - 1)
        heap.removeLast()
        
        func moveDown(_ poppedIndex: Int) -> moveDownStatus {
            let leftChildIndex = poppedIndex * 2
            let rightChildIndex = leftChildIndex + 1
            
            // case1. 모든(왼쪽) 자식 노드가 없는 경우(완전이진트리는 왼쪽부터 채워지므로)
            if leftChildIndex >= heap.count {
                return .none
            }
            
            // case2. 왼쪽 자식 노드만 있는 경우
            if rightChildIndex >= heap.count {
                return heap[leftChildIndex] < heap[poppedIndex] ? .left : .none
            }
            
            // case3. 왼쪽&오른쪽 자식 노드 모두 있는 경우
            // case3-1. 자식들이 자신보다 모두 큰 경우(자신이 제일 작은 경우)
            if (heap[leftChildIndex] > heap[poppedIndex]) && (heap[rightChildIndex] > heap[poppedIndex]) {
                return .none
            }
            
            // case3-2. 자식들이 자신보다 모두 작은 경우(왼쪽과 오른쪽 자식 중, 더 작은 자식을 선별)
            if (heap[leftChildIndex] < heap[poppedIndex]) && (heap[rightChildIndex] < heap[poppedIndex]) {
                return heap[leftChildIndex] < heap[rightChildIndex] ? .left : .right
            }
            
            // case3-3. 왼쪽과 오른쪽 자식 중, 한 자식만 자신보다 작은 경우
            if (heap[leftChildIndex] < heap[poppedIndex]) || (heap[rightChildIndex] < heap[poppedIndex]) {
                return heap[leftChildIndex] < heap[rightChildIndex] ? .left : .right
            }
            
            return .none
        }
        
        var poppedIndex = 1
        while true {
            switch moveDown(poppedIndex) {
            case .none:
                return returnData
            case .left:
                let leftChildIndex = poppedIndex * 2
                heap.swapAt(poppedIndex, leftChildIndex)
                poppedIndex = leftChildIndex
            case .right:
                let rightChildIndex = (poppedIndex * 2) + 1
                heap.swapAt(poppedIndex, rightChildIndex)
                poppedIndex = rightChildIndex
            }
        }
    }
}

 

코드 사용

// var myMinHeap: MinHeap<Int> = MinHeap() // 값 없이 초기화
var minHeap = MinHeap.init(30) // 값 있게 초기화

minHeap.insert(10)
print(minHeap)

minHeap.insert(7)
print(minHeap)

minHeap.insert(8)
print(minHeap)

minHeap.insert(3)
print(minHeap)

print(minHeap.pop()!)

예시 출력 결과

 

예시 출력 결과

 

아래 더보기는, 수정 전 코드입니다.

 

(오류 수정 전) MinHeap 코드

반례

(백준 최소힙문제 : https://www.acmicpc.net/problem/1927)
(반례 관련 테스트케이스 추가 요청 : https://www.acmicpc.net/board/view/86132)

<안 되는 반례>
11
2
2
3
3
1
0
0
0
0
0
0

// MARK: - MinHeap
import Foundation

struct MinHeap<T: Comparable> {
    var heap: [T] = []
    
    var isEmpty: Bool {
        return heap.count <= 1 ? true : false
    }
    
    init() {}
    init(_ element: T) {
        heap.append(element) // 0번 index채우기 용
        heap.append(element) // 실제 Root Node 채움.
    }
    
    mutating func insert(_ element: T) {
        if heap.isEmpty {
            heap.append(element)
            heap.append(element)
            return
        }
        heap.append(element)
        
        func isMoveUp(_ insertIndex: Int) -> Bool {
            if insertIndex <= 1 { // Root Node일 때,
                return false
            }
            let parentIndex = insertIndex / 2
            return heap[insertIndex] < heap[parentIndex] ? true : false
        }
        
        var insertIndex = heap.count - 1
        while isMoveUp(insertIndex) {
            let parentIndex = insertIndex / 2
            heap.swapAt(insertIndex, parentIndex)
            insertIndex = parentIndex
        }
    }
    
    enum moveDownStatus { case left, right, none }
    
    mutating func pop() -> T? {
        if heap.count <= 1 {
            return nil
        }
        let returnData = heap[1]
        heap.swapAt(1, heap.count - 1)
        heap.removeLast()
        
        func moveDown(_ poppedIndex: Int) -> moveDownStatus {
            let leftChildIndex = poppedIndex * 2
            let rightChildIndex = leftChildIndex + 1
            
            // case1. 모든(왼쪽) 자식 노드가 없는 경우(완전이진트리는 왼쪽부터 채워지므로)
            if leftChildIndex >= heap.count {
                return .none
            }
            
            // case2. 왼쪽 자식 노드만 있는 경우
            if rightChildIndex >= heap.count {
                return heap[leftChildIndex] < heap[poppedIndex] ? .left : .none
            }
            
            // case3. 왼쪽&오른쪽 자식 노드 모두 있는 경우
            // case3-1. 자식들이 자신보다 모두 큰 경우
            if (heap[leftChildIndex] > heap[poppedIndex]) && (heap[rightChildIndex] > heap[poppedIndex]) {
                return .none
            }
            
            // case3-2. 자식들이 자신보다 모두 작은 경우(왼쪽과 오른쪽 자식 중, 더 작은 자식을 선별)
            if (heap[leftChildIndex] < heap[poppedIndex]) && (heap[rightChildIndex] < heap[poppedIndex]) {
                return heap[leftChildIndex] < heap[rightChildIndex] ? .left : .right
            }
            
            // case3-3. 왼쪽과 오른쪽 자식 중, 한 자식만 자신보다 작은 경우
            return heap[leftChildIndex] < heap[poppedIndex] ? .left : .right
            
        }
        
        var poppedIndex = 1
        while true {
            switch moveDown(poppedIndex) {
            case .none:
                return returnData
            case .left:
                let leftChildIndex = poppedIndex * 2
                heap.swapAt(poppedIndex, leftChildIndex)
                poppedIndex = leftChildIndex
            case .right:
                let rightChildIndex = (poppedIndex * 2) + 1
                heap.swapAt(poppedIndex, rightChildIndex)
                poppedIndex = rightChildIndex
            }
        }
    }
}

 

 

코드 출처 : https://github.com/sossam/SwiftHeap/blob/main/Heap/MinHeap.swift

참고한 자료 : https://babbab2.tistory.com/109 | https://icksw.tistory.com/216 | https://medium.com/devslopes-blog/swift-data-structures-heap-e3fbbdaa3129 | https://fomaios.tistory.com/entry/Data-Structure-%ED%9E%99Heap%EC%9D%B4%EB%9E%80-feat-Swift

 

---

코드 중 이해가 안 되는 부분이 있거나, 잘못된 부분이 있다면 편하게 댓글 부탁드립니다.