tags: 알고리즘

BOJ_1927 최소힙

첫 풀이때는 min() 함수를 이용하여 최소값을 구한 뒤, filter 고차함수를 이용해 최소값을 제거 해주었다. 그런데 시간초과로 실패를 했고. 일반적인 풀이방법이 통하지 않는다는 것을 깨닳았다.

해답은 우선순위 큐 를 이용하여 문제를 풀어야 하는데 이게 뭔지 몰라서 찾아보았다.

우선순위 큐(Priority queue)

평범한 큐나 스택과 비슷한 축약 자료형이다. 스택의 경우 (LIFO), 큐는 (FIFO) 의 순서를 가진다. 그러나 우선순위 큐의 각 원소들은 우선순위를 갖고 있다.

우선순위 큐 구현방식	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙(Heap)✅	O(logN)	O(logN)

힙이 시간복잡도가 더 적기 때문에 힙으로 구현을 해야했다.

힙 (Heap)

• 힙은 완전 이진 트리 자료구조의 일종이다.
• 우선순위 큐를 위하여 만들어진 자료구조이다.
• 힙에서는 항상 루트 노드를 제거한다.
• 최소 힙 ✅
  • 루트 노드가 가장 작은 값을 가진다.
  • 값이 작은 데이터가 우선적으로 제거된다.
• 최대 힙
  • 루트 노드가 가장 큰 값을 가진다.
  • 값이 큰 데이터가 우선적으로 제거된다.
• 위 그림처럼 배열을 이용하여 힙을 표현할 수 있는데, 규칙이 보인다.
  • 어떤 값의 인덱스(i)를 기준하여
    • 왼쪽 자식노드 = 2i
    • 오른쪽 자식노드 = 2i + 1
    • 부모노드 = i/2

구현

private let sortFunction: (T, T) -> Bool

최대힙, 최소힙을 구별해주는 상수이다. 나의 경우 최소힙을 구현해야 했으므로

var list = Heap<Int>.init { a, b in
    a < b
}

이렇게 초기화를 시켜주었다. a < b 가 true 이면 while 문을 돌며 맞춰지도록 !

- 삽입

• 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입
• 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.

위로 올라가며 부모의 값과 자신의 값을 비교하며 힙의 성질에 맞게 옮기는 작업을 수행하는 메서드swimUp()을 이용하여 삽입 기능을 수행할 수 있다.

mutating func insert(node: T) {
    if self.elements.isEmpty {
        self.elements.append(node)
        return
    }
    self.elements.append(node)
    self.swimUp(from: self.elements.endIndex - 1)
}

mutating func swimUp(from index: Int) {
    var index = index
    while index != 1 && self.sortFunction(self.elements[index], self.elements[self.parent(of: index)]) {
        self.elements.swapAt(index, self.parent(of: index))
        index = self.parent(of: index)
    }
}

- 제거

• 루트 노드가 삭제된다.
• 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
• heapify 를 한다 (힙의 성질에 맞게 옮기는 작업)

아래로 내려가며 자식의 값과 자신의 값을 비교하며 힙의 성질에 맞게 옮기는 작업을 수행하는 메서드 diveDown() 을 이용하여 제거기능을 수행할 수 있다.

mutating func remove() -> T? {
    if self.isEmpty { return nil }
    self.elements.swapAt(1, elements.endIndex - 1)
    let deleted = elements.removeLast()
    self.diveDown(from: 1)

    return deleted
}

mutating func diveDown(from index: Int) {
    var higherPriority = index
    let leftIndex = self.leftChild(of: index)
    let rightIndex = self.rightChild(of: index)

    if leftIndex < self.elements.endIndex && self.sortFunction(self.elements[leftIndex], self.elements[higherPriority]) {
        higherPriority = leftIndex
    }

    if rightIndex < self.elements.endIndex && self.sortFunction(self.elements[rightIndex], self.elements[higherPriority]) {
        higherPriority = rightIndex
    }

    if higherPriority != index {
        self.elements.swapAt(higherPriority, index)
        self.diveDown(from: higherPriority)
    }
}

> 코드는 개발하는 훈이 님의 블로그에서 발췌하였습니다.

나의 최종 제출 코드이다.

let n = Int(readLine()!)!
var list = Heap<Int>.init { a, b in
    a < b
}
list.add(element: 0) // 0번째 인덱스를 채워주기 위한 작업
(1...n).forEach { _ in
    let num = Int(readLine()!)!
    switch num {
    case let x where x < 0:
        return
    case let x where x == 0:
        print(list.remove() ?? 0)
    case let x where x > 0:
        list.insert(node: x)
    default:
        return
    }
}

struct Heap<T: Comparable> {
    private var elements: [T] = []
    private let sortFunction: (T, T) -> Bool
    var isEmpty: Bool {
        return self.elements.count == 1
    }
    var peek: T? {
        if self.isEmpty { return nil }
        return elements[1]
    }
    var count: Int {
        return self.elements.count - 1
    }
    
    init(elements: [T] = [], sortFunction: @escaping (T, T) -> Bool) {
        if !elements.isEmpty {
            self.elements = [elements.first!] + elements
        } else {
            self.elements = elements
        }
        self.sortFunction = sortFunction
        if elements.count > 1 {
            self.buildHeap()
        }
    }
    
    func leftChild(of index: Int) -> Int {
        return index * 2
    }
    
    func rightChild(of index: Int) -> Int {
        return index * 2 + 1
    }
    
    func parent(of index: Int) -> Int {
        return index / 2
    }
    
    mutating func add(element: T) {
        self.elements.append(element)
    }
    
    mutating func insert(node: T) {
        if self.elements.isEmpty {
            self.elements.append(node)
            return
        }
        self.elements.append(node)
        self.swimUp(from: self.elements.endIndex - 1)
    }
    
    mutating func remove() -> T? {
        if self.isEmpty { return nil }
        self.elements.swapAt(1, elements.endIndex - 1)
        let deleted = elements.removeLast()
        self.diveDown(from: 1)
        
        return deleted
    }
    
    mutating func swimUp(from index: Int) {
        var index = index
        while index != 1 && self.sortFunction(self.elements[index], self.elements[self.parent(of: index)]) {
            self.elements.swapAt(index, self.parent(of: index))
            index = self.parent(of: index)
        }
    }
    
    mutating func diveDown(from index: Int) {
        var higherPriority = index
        let leftIndex = self.leftChild(of: index)
        let rightIndex = self.rightChild(of: index)
        
        if leftIndex < self.elements.endIndex &&
            self.sortFunction(self.elements[leftIndex], self.elements[higherPriority]) {
            higherPriority = leftIndex
        }
        
        if rightIndex < self.elements.endIndex &&
            self.sortFunction(self.elements[rightIndex], self.elements[higherPriority]) {
            higherPriority = rightIndex
        }
        
        if higherPriority != index {
            self.elements.swapAt(higherPriority, index)
            self.diveDown(from: higherPriority)
        }
    }
    
    mutating func buildHeap() {
        for index in (1...(self.elements.count / 2)).reversed() {
            self.diveDown(from: index)
        }
    }
}

---

References

• 참조 블로그
  • 개발하는 훈이
  • HeeJeong Kwon
• 위키백과
  • 우선순위 큐
  • 힙
• 참조 유튜브
  • 동빈나 - 우선순위 큐