Heap

오늘은 자료구조 Heap에 대해서 알아보자.

Heap

Heap의 특징에 대해 먼저 알아보자.

• Heap은 완전 이진 트리로 구성되어 있다.
• Heap은 값들 중에서 최댓값이나 최솟값을 빠르게 찾을 수 있는 자료구조이다.
• Heap은 중복된 값을 허용한다.

Heap 그림으로 위의 특징들을 이해해보자.

위의 그림을 보면 완전 이진 트리로 구성되어 있고 중복된 값을 허용함을 알 수 있다.
root에서부터 내려오다보면 한 가지 규칙을 알 수 있는데 부모 노드 값 <= 자식 노드 값임을 알 수 있다.
이처럼 부모 노드 값이 자식 노드 값보다 값이 작은 형태의 Heap을 최소 힙(min Heap)이라고 한다.
반대로 부모 노드 값이 자식 노드 값보다 값이 큰 형태의 Heap을 최대 힙(max Heap)이라고 한다.

---

Heap의 삽입

Heap의 삽입이 어떻게 이뤄지는지 확인해보자.

1. Heap에 새로운 노드가 들어오면 Heap의 마지막 노드 뒤에 삽입한다.
2. 새로운 노드를 부모 노드들과 비교하면서 Heap이 되도록 교환해나간다.

위와 같은 최소힙에 2를 추가해보자.

1. 힙은 완전 이진 트리로 구성되어 있으므로 가장 마지막 노드 뒤에 2를 추가한다.

2. 최소힙은 부모 노드 값 <= 자식 노드 값 조건을 만족시켜야하므로 2의 부모 노드인 6과 비교한다.
   비교 결과 부모 노드 값이 자식 노드 값보다 크므로 둘을 swap한다.

3. 2의 부모 노드인 5와 비교한다.
   비교 결과 부모 노드 값이 자식 노드 값보다 크므로 둘을 swap한다.

4. 2의 부모 노드인 1과 비교한다.
   비교 결과 부모 노드 값이 자식 노드 값보다 작으므로 Heap 구성을 마친다.

---

Heap의 삭제

Heap의 삭제가 어떻게 이뤄지는지 확인해보자.
(위에서 구성한 Heap에서 삭제를 해보자.)
Heap의 삭제는 Heap의 루트를 삭제하는 것이다.
즉, 최대 힙에서의 삭제는 최대 값을 삭제하는 것이고, 최소 힙에서의 삭제는 최소 값을 삭제하는 것이다.

위와 같이 구성된 Heap에서 루트인 1을 삭제해보자.

1. 루트 노드 1을 삭제한다.
   삭제한 자리에는 최소 힙의 마지막 노드를 가져온다.

2. 삽입된 노드와 자식 노드를 비교한다.
   최소힙은 부모 노드 값 <= 자식 노드 값 조건을 만족시켜야하므로 자식 노드 중 더 작은 값과 교환한다.
   삽입 노드 6의 자식 노드 2, 3은 6보다 작은 값을 가지지만 그 중 더 작은 값인 2와 swap한다.

3. 삽입 노드 6의 자식 노드 5가 5보다 작은 값을 가지므로 swap한다.

---

Heap with Swift

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

extension Heap where T: Comparable {
    init() {
        self.init(comparer: <)
    }
}

(출처: https://gist.github.com/JCSooHwanCho/a3f070c2160bb8c0047a5ddbb831f78e)

---

마무리

오늘은 자료구조 힙에 대해서 알아봤다.
역시... 코드로 자료구조 구현은 어려워..
그럼 이만👋