1927 최소 힙

Today 3/31

Heap

[자료구조] 그림으로 쉽게 보는 힙(Heap) 개념과 코드

힙은 일종의 트리로 수의 집합에서 가장 작은 수나 가장 큰 수만을 꺼내올 때 유용한 자료구조이다.

완전이진트리를 베이스로 구성된다.

배열로 구현될 수 있는데, 자식은 {자신의 인덱스 2}, {자신의 인덱스 2 + 1}로 구성된다.

반대로 부모 또한 자신의 인덱스/2로 구할 수 있다.

Insert

배열의 가장 마지막에 수를 추가하고, /2를 계속 해서 자신의 부모노드보다 작은지 반복문을 돈다. (부모노드가 더 클 때까지 || 자신의 현재 노드가 Root 노드가 될 때까지)

Delete

Root 노드의 값을 제거하고 Root 노드에 배열의 가장 마지막 값을 넣는다. 그리고 자식 노드와 계속 비교해가면서 반복문을 돈다. 이 때, Right, Left 노드의 유무, 크기, 부모 노드와의 대소에 따라 여러 조건으로 나뉠 수 있는데, 가장 간단하게 표현하는 방법은 이것인 것 같았다.

첫 번째 조건문에서는 자식 노드가 두 개일 때 어떤 노드가 작은지를 결정한다. (작은 노드를 자식 노드로)

두 번째 조건문에서는 Swap이 일어나지 않는 두 조건일 때 break를 구현한다.

1. 자식 노드가 하나도 없을 때
2. 1번에서 고른 작은 노드가 부모노드보다 커서 swap이 필요하지 않을 때

이렇게 두 조건문에서 조건을 모두 거른 다음 swap을 통해 위치변화를 반복해준다.

최소힙 (My Code)

var heap = [Int]()

func insert(_ num: Int) {
    if heap.isEmpty {
        heap.append(-1)
        heap.append(num)
    } else {
        heap.append(num)
    }
    var index = heap.count-1
    while index != 1 && num < heap[index/2] {
        heap.swapAt(index, index/2)
        index /= 2
    }
}

func delete() {
    if heap.isEmpty || heap.count == 1 {
        print("0")
    } else if heap.count == 2 {
        print(heap.removeLast())
    } else {
        print(heap[1])
        heap[1] = heap.removeLast()
        var parent = 1
        var child: Int
        while true {
            child = parent*2
            if child+1 <= heap.count-1 && heap[child] > heap[child+1] {
                child += 1
            }
            if child > heap.count-1 || heap[parent] < heap[child] { break }
            heap.swapAt(parent, child)
            parent = child
        }
    }
}

let N = Int(readLine()!)!
for _ in 0..<N {
    let input = Int(readLine()!)!
    if input == 0 {
        delete()
    } else {
        insert(input)
    }
}