Heap 자료구조

힙 자료구조는 트리의 일종으로, 여러 원소 중 최댓값 혹은 최솟값을 찾는데에 유용하게 사용할 수 있는 자료구조입니다. 오늘은 Heap의 원리와 그 구현을 한번 살펴보도록 하겠습니다.

Heap의 원리
힙은 다음 규칙을 만족하는 자료구조입니다.
1. 완전 이진 트리(Complete Binary Tree)입니다. 완전 이진 트리란, 마지막 레벨을 제외하고는 모두 채워져 있고, 마지막 레벨도 노드들이 왼쪽으로 모두 치우쳐져 사이에 빈 틈이 없는 트리를 의미합니다.
2. 모든 노드에 대해서 부모와 자식 간에 일정한 대소 관계가 성립합니다. 같은 레벨의 형제 노드는 대소관계 규칙이 적용되지 않습니다.
이러한 규칙을 가지면, 루트 노드에는 모든 하위 노드들과 대소관계 규칙을 만족하는 노드가 올라오게 됩니다. 힙의 핵심은 원소를 넣고 빼는 과정에서 이러한 규칙을 계속해서 만족시키도록 만드는 것입니다.

Heap의 구현
힙의 코드를 보면서, 힙의 원리를 더 살펴보도록 하겠습니다.

  struct Heap<T> {
      var nodes: [T] = []
      let comparer: (T,T) -> Bool

      var isEmpty: Bool {
          return nodes.isEmpty
      }

      init(comparer: @escaping (T,T) -> Bool) {
          self.comparer = comparer
      }  

      func peek() -> T? {
          return nodes.first
      }
  }

  var heap: Heap<Int> = Heap { $0 < $1 } // Max Heap 생성

힙은 완전 이진 트리이기 때문에 배열로 나타내면 저장공간을 효율적으로 사용하면서도, 인덱스를 통해서 손쉽게 트리를 탐색할 수 있습니다. 그리고 힙 전체가 공유하는 대소규칙을 의미하는 comparer를 추가적으로 가지고 있습니다. 이 comparer는 힙을 생성할 때 인자로 주어야 합니다.

less 연산자를 인자로 주었을 때, Max Heap이 되는 것은 이번에 보일 구현이 c++의 기본 구현을 참고했기 때문입니다.

nodes 배열의 첫번째 원소는 곧 힙의 루트기 때문에, 첫번째 원소가 있다면 첫번째 원소를, 없다면 nli을 반환합니다.

힙에 원소를 삽입하는 과정을 살펴보겠습니다. 힙은 원소를 삽입한 뒤에도 힙의 규칙을 준수해야 하기 때문에, 다음 과정을 통해 삽입이 이루어집니다.

만약 현재 트리가 포화 상태라면, 새로운 레벨에 노드를 넣고, 포화 상태가 아니라면 현재 레벨에 노드를 붙인다.
부모 노드가 있을 경우, 부모노드와의 대소관계 규칙을 만족하는 지 확인합니다. 만족하지 못하는 경우, 부모 노드와 자식 노드를 교환한 뒤, 부모노드로 이동한 뒤 이 과정을 반복합니다. 만족하는 경우는 삽입 과정을 종료합니다.

이때, 1번 과정은 이진 트리를 배열로 표현하기 때문에, 단순히 마지막에 새로운 노드를 삽입하는 것으로 완료됩니다.

  mutating func insert(_ element: T) {
      var index = nodes.count

      nodes.append(element) // 1번 과정

      // 2번 과정
      while index > 0, !comparer(nodes[index],nodes[(index-1)/2]) { 
          nodes.swapAt(index, (index-1)/2)
          index = (index-1)/2
      }
  }

삭제는 삽입보다 더 복잡합니다. 힙에서의 삭제는 루트노드를 힙에서 제거하는 것으로, 삭제가 이뤄진 다음에도 삽입과 마찬가지로 힙의 규칙을 유지해야 하기 때문에 다음과 같은 방법으로 삭제를 수행합니다.

힙의 루트 노드와 힙의 마지막 레벨의 가장 오른쪽 노드를 맞바꿉니다.
힙의 마지막 레벨의 가장 오른쪽 노드(원래의 루트노드)를 제거합니다.
루트노드에서 시작해서 자식 노드와 대소 관계를 비교합니다. 이때 자식이 둘일 경우는 부모 노드와 바꿨을 때 자식 노드와 대소관계 규칙을 유지할 수 있도록 바꿔줍니다.

완전 이진 트리의 특성상, 왼쪽 자식 노드 없이, 오른쪽 자식 노드만 존재하는 경우는 불가능합니다.

  mutating func delete() -> T? {
      guard !nodes.isEmpty else {
          return nil
      }

      if nodes.count == 1 {
          return nodes.removeFirst()
      }

      let result = nodes.first
      nodes.swapAt(0, nodes.count-1)
      nodes.popLast()

      var index = 0

      while index < nodes.count {
          let left = index * 2 + 1
          let right = left + 1

          if right < nodes.count { // 오른쪽 노드가 존재하는 경우
              if comparer(nodes[left], nodes[right]),
                  !comparer(nodes[right], nodes[index]) {
                  nodes.swapAt(right, index)
                  index = right
              } else if !comparer(nodes[left], nodes[index]){
                  nodes.swapAt(left, index)
                  index = left
              } else {
                  break
              }
          } else if left < nodes.count { // 왼쪽 노드만 존재하는 경우
              if !comparer(nodes[left], nodes[index]) {
                  nodes.swapAt(left, index)
                  index = left
              } else {
                  break
              }
          } else {
              break
          }
      }

      return result
  }

Heap의 시간복잡도
힙의 원소 삽입의 경우, 힙 내의 전체 원소의 수를 N이라고 하면, 원소를 힙에 넣는 데에는 O(1), 힙의 규칙을 만족하도록 조정하는 과정에는 O(log N)의 시간복잡도를 가집니다.

삭제 역시 마찬가지로 루트 노드를 트리의 마지막 노드와 교환하는데 O(1), 마지막 노드를 트리에서 제거하는 데 O(1), 힙의 규칙을 유지하도록 조정하는데 O(N)의 시간복잡도를 가집니다.

Heap 전체 구현
아래는 Heap 구현 전체 코드입니다. 필요에 따라서 추가적으로 모듈화하거나 새로운 기능을 추가하셔서 사용하시면 됩니다.

struct Heap<T> {
  var nodes: [T] = []
  let comparer: (T,T) -> Bool

  var isEmpty: Bool {
      return nodes.isEmpty
  }

  init(comparer: @escaping (T,T) -> Bool) {
      self.comparer = comparer
  }

  func peek() -> T? {
      return nodes.first
  }

  mutating func insert(_ element: T) {
      var index = nodes.count

      nodes.append(element)

      while index > 0, !comparer(nodes[index],nodes[(index-1)/2]) {
          nodes.swapAt(index, (index-1)/2)
          index = (index-1)/2
      }
  }

  mutating func delete() -> T? {
      guard !nodes.isEmpty else {
          return nil
      }

      if nodes.count == 1 {
          return nodes.removeFirst()
      }

      let result = nodes.first
      nodes.swapAt(0, nodes.count-1)
      nodes.popLast()

      var index = 0

      while index < nodes.count {
          let left = index * 2 + 1
          let right = left + 1

          if right < nodes.count { 
              if comparer(nodes[left], nodes[right]),
                  !comparer(nodes[right], nodes[index]) {
                  nodes.swapAt(right, index)
                  index = right
              } else if !comparer(nodes[left], nodes[index]){
                  nodes.swapAt(left, index)
                  index = left
              } else {
                  break
              }
          } else if left < nodes.count {
              if !comparer(nodes[left], nodes[index]) {
                  nodes.swapAt(left, index)
                  index = left
              } else {
                  break
              }
          } else {
              break
          }
      }

      return result
  }
}

힙은 특정 데이터에서 최댓값 혹은 최솟값을 찾는데에 매번 배열을 검색하는 것보다 훨씬 적은 시간을 소모하기 때문에 우선순위 큐의 구현에 많이 사용됩니다.