(Swift) – 힙(Heap) – 자료구조에 대해

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) -> 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
}

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


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