1927 최소 힙

Today 8/30

HEAP

최단경로를 풀다가 힙을 먼저 알고 가야겠다 싶어서 heap을 공부했다.

heap은 우선순위 queue를 구현하는 한 가지 방법이다. (하지만 시간복잡도가 가장 빨라서 heap = priority queue라고 봐도 될듯)

heap은 배열로 구성되고, 배열 자체가 반정렬상태이다. 또한, 완전이진트리이다.

배열로 트리를 어떻게 구현하나 했는데, /2를 이용해서 몫이 같은 index들이 몫의 child가 된다.

또한, 중요한 점은 편의를 위해 첫번째 index인 0을 비워두고(다른 수로 채워두고) index 1에 rootNode를 넣는다.

HEAP INSERT

새로운 요소가 들어오면 힙의 마지막에 일단 삽입한다.

root노드가 될 때까지 부모노드와 비교하며 교환으로 위치를 찾아간다.

func insert(_ num: Int) {
    heap.append(num)
    var node = heap.count-1
    while node != 1 {
        let parent = node/2
        if heap[parent] > heap[node] {
            heap.swapAt(parent, node)
            node /= 2
        } else {
            break
        }
    }
}

HEAP DELETE

heap의 root 노드가 삭제되면, 가장 마지막 노드가 root노드를 대체한다.

insert와 마찬가지로 child노드와 비교하며 교환하며 정렬하는 것은 맞지만, 경우의 수를 나누어야 한다.

1) child가 없을 때 2) leftChild만 존재할 때 3) 두 child 모두 존재할 때

이 때, 3번에서는 둘 중 큰/작은 child와 비교해야 정렬이 꼬이지 않는다.

-이렇게 찾은 child와 parent노드를 비교하여 교환하여 정렬한다.

func delete() {
    print(heap[1])
    heap.swapAt(1, heap.count-1)
    heap.removeLast()
    var node = 1
    while true {
        var child = 0
        if node*2 == heap.count-1 {
            child = node*2
        }
        if node*2 > heap.count-1 {
            break
        }
        if node*2 < heap.count-1 {
            if heap[node*2] > heap[node*2+1] {
                child = node*2+1
            } else {
                child = node*2
            }
        }
        
        if heap[child] < heap[node] {
            heap.swapAt(child, node)
            node = child
        } else {
            break
        }
    }
}

최소 힙 (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)
    }
}

최소 힙을 예전에 풀어보았는데, 지금 보니까 조금 문제점이 있었다.

일단 index 0을 가만히 두지 않고 자꾸 넣었다 뺐다 하는 것이 번거롭게 느껴졌다.

또, delete에서 child를 판별할 때, 조건이 간결하지 않고 너무 축약해서 가독성과 이해가 떨어졌다.

let N = Int(readLine()!)!
var heap = [0]

func insert(_ num: Int) {
    heap.append(num)
    var node = heap.count-1
    while node != 1 {
        let parent = node/2
        if heap[parent] > heap[node] {
            heap.swapAt(parent, node)
            node /= 2
        } else {
            break
        }
    }
}

func delete() {
    print(heap[1])
    heap.swapAt(1, heap.count-1)
    heap.removeLast()
    var node = 1
    while true {
        var child = 0
        if node*2 == heap.count-1 {
            child = node*2
        } else if node*2 > heap.count-1 {
            break
        } else {
            if heap[node*2] > heap[node*2+1] {
                child = node*2+1
            } else {
                child = node*2
            }
        }
        
        if heap[child] < heap[node] {
            heap.swapAt(child, node)
            node = child
        } else {
            break
        }
    }
}

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

보완해서 이번에 만든 코드, delete에서 parent와 비교는 나중에 하고, 일단 child를 선택하고, 그 다음 parent와 비교하는 식으로 if문을 간결화시켰다.