힙(Heap) – 자료구조 (Swift)

heap은 일종의 바이너리트리로, 단일 배열을 이용해서 구현하며, 각 노드간의 포인터를 가지지 않는다. 트리는 내부적으로 부분적으로 정렬된 상태를 유지한다. 따라서 루트 요소를 꺼내면 정렬된 상태를 얻을 수 있다. 힙은 흔히 최대힙과 최소힙으로 구분하는데 이는 동일한 것이며 단지 정렬 순서만 다르다.

힙으로 할 수 있는 일은 다음과 같다.

  1. 우선순위 큐를 만든다.
  2. 힙 정렬 수행
  3. 변경가능한 집합의 최소값(혹은 최대값)을 빈번히 계산해야 할 때 유용하다.

배열의 인덱스가 0부터 시작한다고 가정하면, 다음과 같은 방식으로 배열을 이진트리로 바꿀 수 있다.

  1. 인덱스 0인 요소가 루트가 된다.
  2. 루트의 왼쪽 자식의 인덱스는 1 (0 * 2 + 1), 오른쪽 자식은 오른쪽 자식은 2 (0 * 2 + 2)가 된다.
  3. 특정 인덱스의 부모요소의 인덱스는 (i – 1) / 2 로 구할 수 있다.

힙에 원소를 추가하면 배열의 맨 뒤에 원소를 붙이고, 해당 자리에서 부모보다 그 원소가 작으면 부모와 위치를 교환한다. 이 과정을 더 이상 올라갈 수 없을 때 까지 반복하면 된다.

힙에서 루트를 꺼내는 경우에는 배열의 맨 마지막 요소를 루트 자리에 넣는다. 그런다음 좌/우 자식 중에서 더 작은 요소가 자신보다 작으면 위치를 교환한다. 이 과정을 더 이상 계속할 수 없을 때까지 반복한다.

기본 구성

힙의 기본구성은 데이터를 저장할 배열과, 각 원소간의 순서를 비교할 평가함수이다. 이 둘은 외부에 노출될 필요는 없다. T가 Comparable 프로토콜을 따르는 타입이어도 되지만, 여기서는 커스텀한 비교 장치를 따로 가질 수 있도록 한다.


public struct Heap<T> {
    public typealias Comparator = (T, T) -> Bool
    private var __isOrderedBefor: Comparator
    private var elements: [T] = []

    init(comparator: Comparator) {
        __isOrderedBefor = comparator
    }
}

프로퍼티

힙이 비어있는지, 가장 상위에 올라와 있는 요소가 무엇인지와 같은 프로퍼티도 만들어준다. 물론 힙이 비어있는 경우 이 값은 nil이 될 수 있다.


var isEmpty: Bool { return elements.isEmpty }
var peak: T? { return elements.isEmpty ? nil : elements[0] }

그런데 위에서 정의했듯이 peak 은 그냥 배열의 .first 아닌가.


var peak: T? { return elements.first }

이렇게 수정한다.

노드 위치 계산

특정 요소가 추가/제거된 후 올바른 자리를 찾아가기 위해서는 주어진 위치에서의 부모노드의 위치, 왼쪽 자식 노드의 위치 및 오른쪽 자식 노드의 위치를 찾을 수 있어야 한다. 이 들을 구하는 내부 메소드를 정의해보자. (이 때의 위치는 배열에서의 인덱스이다.)


private func leftIndex(of i: Int) -> Int? {
    if case let l = i * 2 + 1 where l < elements.count {return l }
    return nil
}

private func rightIndex(of i: Int) -> Int? {
    if case let r = i * 2 + 2 where r < elements.count { return r }
    return nil
}

private func parent(of i: Int) -> Int? { return i > 0 ? i / 2 : nil }

이 들은 내부의 원소 이동 과정에서 매우 빈번히 호출될 수 있으므로, 가능한 인라인으로 컴파일되게 한다. 항상 인라인으로 컴파일 되게 하는 컴파일러 디렉티브는 @inline(__always) 이다.


@inline(__always) private func leftIndex(of i: Int) -> Int? {
    if case let l = i * 2 + 1 where l < elements.count {return l }
    return nil
}

@inline(__always) private func rightIndex(of i: Int) -> Int? {
    if case let r = i * 2 + 2 where r < elements.count { return r }
    return nil
}

@inline(__always) private func parent(of i: Int) -> Int? { return i > 0 ? i / 2 : nil }

노드 바꾸기

노드 교환 역시 빈번히 일어나기 때문에 인라인 함수로 하나 정의해서 쓰자.

@inline(__always) mutating func swapElements(_ a: Int, _ b: Int) {
    (elements[a], elements[b]) = (elements[b], elements[a])
}

또, 노드끼리 비교하는 부분도 그만큼 빈번히 계산되기 때문에 따로 정의한다.


@inline(__always) func isOrderedBefor(_ a: Int, _ b: Int) -> Bool {
    return __isOrderedBefor(elements[a], elements[b])
}

위로 이동

새로 추가된 원소는 배열의 맨 끝에서부터 위로 올라간다고 했다. 부모에 해당하는 인덱스의 값과 비교하여 자신이 앞에 서야하면 자리를 바꾸고, 다시 부모와… 이 과정을 더 이상 나아갈 수 없을 때까지 반복한다.


private mutating func shiftUp(at: _i) {
    var i = _i
    while let p = parent(of: i) where isOrderedBefore(p, i)  {
        swapElements(p, i)
        i = p
    }
}

그러면 신규 원소 추가는 다음과 같이 배열의 맨 끝에 추가된 원소가 자신의 부모와 비교하여 자리를 바꿔 올라가는 작업을 반복해주면 된다. 여기까지는 매우 쉽다.

public mutating func add(_ e: T) {
    elements.append(e)
    shiftUp(at:elements.count - 1)
}

아래로 이동

아래로 이동하는 경우는 좀 복잡할 수 있다. 좌, 우 자식 노드와 교환하는데 몇 가지 제약이 있기 때문이다. 현재 노드가 왼쪽, 오른쪽 노드보다 큰지 비교해서 크면 위치를 바꾼다. 만약 두 자식노드 모두 자신보다 작으면 그 중에 작은 노드와 위치를 바꾼다. 문제는 자식노드가 있을 때도 있고 없을 때도 있다는 것이다. 하지만 이 때 한가지 팁은 어떤 임의의 한 노드의 두 자식의 관계는 상호간의 대소 관계와 아무런 상관이 없고, 그저 먼저 붙은쪽이 왼쪽, 그렇지 않은 쪽은 오른쪽에 온다는 것이다. 따라서 왼쪽 자식 노드 없이 오른쪽 자식 노드가 있을 수 없기 때문에 고려해야하는 케이스 하나가 줄어든다.

어쨌든 찾아야 하는 자식은 자신의 하위 노드중에서 가장 앞에 올 수 있는 노드이다. 이를 찾기 위해서는1

  1. 먼저 왼쪽 자식이 있는지 보고 (없으면 자식 노드가 아예 없음)
  2. 그런다음 오른쪽 자식이 있는지도 본다. 오른쪽 자식이 없으면 왼쪽 자식 낙점
  3. 두 자식 중에 더 작은(앞에와야 하는) 자식을 찾는다.
private func avaiableChild(of: i) -> Int? {
    guard let l = leftIndex(of: i) else { return nil }
    if let r = rightIndex(of: i) {
        let x = isOrderedBefore(l, r) ? l : r
        return isOrderedBefore(x, i) ? x : nil
    } 
    return isOrderedBefore(l, i) ? l : nil
}

혹은 다음과 같이 쓸 수도 있는데, switch 보다 위의 중첩 분기가 더 간결한 것 같다.

private func availableChild(of: i) -> Int? {
var result: Int?
switch (leftIndex(of: i), rightIndex(of: i) {
case (nil, _): return nil
case (let x, nil): return = x
case let (x, y):
result = isOrderedBefore(x, y) ? x : y
}
return isOrderedBefore(r, i) ? r : nil
}

제거

힙에서 가장 성가신 부분이 맨 위에 있는 요소를 빼낸 후의 처리이다. 힙은 내부가 부분적으로 정렬되어 있지, 그것이 항상 정렬된 상태는 아니다. 따라서 최상위에 있던 노드를 빼내면, 차상위노드가 루트로 올라와야 한다. 물론 한 번도 노드를 뺀적이 없다면 차상위 노드는 최상위 노드의 두 자식 중 하나일 것이다. 하지만 제3위, 제4위는 힙 내에 어디 있는지 알 수 없다. 따라서 위에서부터 뭔가를 내려보내면서 아래에 있는 잠룡(?)들을 위로 끌어올려야 한다. 이 때 쓸 유인책이 맨끝에 붙은 노드이다. 즉

  1. 맨 뒤의 요소를 떼어 루트 위치에 놓는다.
  2. 루트의 자식 중 교환할만한 자식이 있으면 교환한다.
  3. 이후 교환한 위치를 따라가면서 (원래 맨뒤의 요소)를 적절한 위치까지 내려가게끔한다.

를 시행하면 된다.

따라서 맨 요소를 때서 루트 위치에 놓은 다음, shiftDown을 이용해서 내려가도록 만든다.

public mutating func remove() -> T? {
    guard count > 0 else { return nil }
    let result = elements.first
    let last = elements.removeLast()
    if !elements.isEmpty {
        elements[0] = last
        shiftDown(at: 0)
    }
    return result
}

중요한 부분의 구현은 끝났고, 최종코드는 여기에 있다.

https://gist.github.com/sooop/67b8eb38b61bb53fdd5f369763e17296


  1. 이게 파이썬에서는 엄청 귀찮은 작업이었고, 코드도 제법 길고 복잡했는데, Swift에서는 엄청 간단하다….