Swift - 백준 1927 최소 힙

swift에서는 최소 힙에 관한 라이브러리가 없기 때문에 직접 구현해야 합니다

 

아이패드가 없어서 직접 push를 하는 과정

push 하는법

push 하는 법은 다음과 같습니다

• 현재 힙의 크기가 0보다 크고 현재 값이 부모 노드보다 작을 때까지 while 문을 반복합니다.
• while 문에서 반복되는 동안 현재 값의 노드와 부모 노드와 값을 바꾸고 부모 노드로 현재 위치(인덱스)를 이동시킵니다.
• while 문을 반복하다보면 현재 들어온 값은 자신보다 큰 부모 노드가 나올때까지 부모 노드와 계속 swap합니다.

func push(_ x: Int) {
    heap.append(x)
    
    var n = heap.count-1
    
    while n > 0 && x < heap[(n-1)/2] {
        heap.swapAt(n, (n-1)/2)
        n = (n - 1) / 2
    }
}

 

pop 하는법

pop 은 push 에 비해 코드는 길지만 원리는 비슷합니다.

• 만약 현재 힙이 비어있다면 0을 반환합니다.
• 비어있지 않다면 최소값인 heap[0]을 담아줍니다.
• 만약 힙에 한개만 들어있는 상황이라면 현재 첫번째 값을 반환합니다.
• 여기서 힙의 성질이 나타나는데 값이 heap의 크기가 1 이상이면 가장 마지막 값을 최솟값이 들어있는 첫 번째 위치로 옮깁니다.
• i * 2 + 1 은 자식 노드를 의미하며 오른쪽 자식 노드가 존재하고, 오른쪽 자식 노드가 더 작으면 인덱스 j를 오른쪽 자식으로 설정합니다. (더 작은 자식과 스왑을 해야합니다)
• 현재 노드가 자식 노드보다 작거나 같게 된다면 while 문을 멈춥니다.
• 아니면 계속해서 현재 값을 내려보냅니다.

func pop() -> Int {
    if heap.isEmpty { return 0 }
    let min = heap[0]
    
    if heap.count == 1 {
        heap.removeLast()
        return min
    } else {
        heap[0] = heap.removeLast()
    }
    
    var i = 0
    
    while i * 2 + 1 < heap.count {
        var j = i * 2 + 1
        if j+1 < heap.count && heap[j+1] < heap[j] { j += 1 }
        if heap[i] <= heap[j] { break }
        heap.swapAt(i, j)
        i = j
    }
    
    return min
}

 

전체 코드

import Foundation

let num = Int(readLine()!)!
var heap = [Int]()

func push(_ x: Int) {
    heap.append(x)
    
    var n = heap.count-1
    
    while n > 0 && x < heap[(n-1)/2] {
        heap.swapAt(n, (n-1)/2)
        n = (n - 1) / 2
    }
}

func pop() -> Int {
    
    if heap.isEmpty { return 0 }
    
    let min = heap[0]
    
    if heap.count == 1 {
        heap.removeLast()
        return min
    } else {
        heap[0] = heap.removeLast()
    }
    
    var i = 0
    
    while i * 2 + 1 < heap.count {
        var j = i * 2 + 1
        
        if j+1 < heap.count && heap[j+1] < heap[j] { j += 1 }
        
        if heap[i] <= heap[j] { break }
        
        heap.swapAt(i, j)
        
        i = j
    }
    
    return min
}

for _ in 1...num {
    let tmp = Int(readLine()!)!
    
    if tmp == 0 {
        print(pop())
    } else {
        push(tmp)
    }
}