[자료구조/Swift] 힙(Heap)

Swift로 힙을 구현하기 전에, 우선 힙의 개념을 정리해보고자 한다.

 

힙(Heap) 이란?

1) 완전 이진 트리 (왼쪽에서 오른쪽으로 차례대로 채워진 이진 트리)

2) 
최소 힙 : 부모 노드의 값은 항상 자식 노드들의 값보다 작거나 같다. (보통 코딩테스트에서는 이걸 기본으로 하고, 최대를 구해야할 때는 음수로 치환해서 품. 다익스트라 알고리즘에서도 사용) -> 루트 노드가 최소값

최대 힙 : 부모 노드의 값은 항상 자식 노드들의 값보다 크거나 같다. -> 루트 노드가 최대값

* 우선순위 큐를 구현할 때 힙을 자주 쓰는 이유는, 노드의 값이 작아질수록 혹은 클수록 우선순위가 높아진다고 고려했을 때
힙에서 데이터를 추출할 때 우선순위가 높은 것(가장 작은것 혹은 가장 큰 것)부터 먼저 추출되므로 우선순위 큐의 특성에 적합하다.

* 리스트와 힙의 각각의 우선순위 큐 구현 시 시간 복잡도는 아래와 같다. 리스트로 구현할 수 있겠지만 힙이 실행속도가 더 빠르기 때문에 더 유리하다.

우선순위 큐 구현방식	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙(Heap)	O(logN)	O(logN)

  

보통 힙 자료구조는 다양한 언어에서 표준 라이브러리로 지원하지만, swift는 지원하지 않기때문에 힙을 직접 구현할 일이 많다.

Heap의 삽입/삭제 과정을 이해하고 Swift로 직접 구현해보도록 하자!

 

Swift로 힙 구현하기 (최소힙 기준)

1) 뼈대잡기

//최소힙 기준
struct Heap<T: Comparable> {
  //heap: 실제로 데이터들을 저장할 이진트리로 표현될 배열
  var heap: [T] = []
    
  var isEmpty: Bool {
    return heap.count <= 1
  }
  
  var count: Int {
    return heap.count - 1 //0을 추가했으므로 이걸 제외할 필요 있음
  }

  init() { }
  init(_ element: T) {
      heap.append(element) // 0번 index채우기 용
      heap.append(element) // 실제 Root Node 채우기
  }
  
  func leftChild(of index: Int) -> Int { //자식 인덱스 (부모 왼쪽에 있는 인덱스)
    return index * 2
  }
  
  func rightChild(of index: Int) -> Int { //형제 인덱스 (부모 오른쪽에 있는 인덱스)
    return index * 2 + 1
  }
  
  func parent(of index: Int) -> Int { //부모 인덱스
    return (index) / 2
  }

- 인덱스를 1부터 시작하게 하기 위해 맨 처음에는 원소를 2개 채워준다. (첫 아이템이 깍두기? 아이템)

- 부모노드 : 인덱스/2, 왼쪽 자식노드: 인덱스*2, 오른쪽 자식노드: 인덱스*2+1

 

2) 삽입 (insert)

 

- 최소힙에서 삽입할 때 일어나는 순서는 다음과 같다.

우선 맨 끝에 데이터를 추가함 -> 자기보다 작은 부모 노드의 인덱스를 찾아가면서, 해당 부모 노드 인덱스의 데이터와 자리를 바꿔나감 -> 자기 자신보다 작은 부모 노드를 찾을 수 없을 때까지 이를 반복

  mutating func insert(_ node: T) { //데이터 삽입
    if heap.isEmpty { //힙이 원래 비어있었다면 노드 자체가 힙이 됨
        heap.append(node)
        heap.append(node)
        return
    }
    heap.append(node) // 1. 일단 넣음(데이터 비교와는 상관없이)

    func isMoveUp(_ insertIndex: Int) -> Bool { // 2. 자기보다 큰 부모 노드의 인덱스를 찾는 과정
      if insertIndex <= 1 {  // 루트 노드일 때 -> 찾는 부모 노드가 없음
          return false
      }
      let parentIndex = insertIndex / 2
      return heap[insertIndex] < heap[parentIndex] ? true : false
    }
    
    var insertIndex = heap.count - 1
    while isMoveUp(insertIndex) { //2. 자기 자리를 찾아갈때까지 위로 감 (나의 부모노드가 더 작을때까지 계속 swap 함)
        let parentIndex = insertIndex / 2
        heap.swapAt(insertIndex, parentIndex)
        insertIndex = parentIndex
    }
  }

 

3) 삭제 (pop)

- 일단 맨 마지막 노드를 루트노드와 맞바꾼다음, 마지막 노드를 지운다.

  mutating func pop() -> T? { //삭제
    if heap.count <= 1 { return nil }
    
    let poped = heap[1]
    heap.swapAt(1, heap.count - 1) //1. 부모노드랑 자리를 바꾼다음 마지막껄 지워냄
    heap.removeLast()

- 그리고 조건에 따라 swap을 먼저 해준다음에, 데이터를 return해주어야한다.  

  enum moveDownStatus { case none, left, right } //어떤 노드와 swap해야하는지 지정하기 위한 열거형

  mutating func pop() -> T? { //삭제
    if heap.count <= 1 { return nil }
    
    let poped = heap[1]
    heap.swapAt(1, heap.count - 1) //1. 부모노드랑 자리를 바꾼다음 마지막껄 지워냄
    heap.removeLast()
    
    func moveDown(_ poppedIndex: Int) -> moveDownStatus { // 어떻게 이동할 지에 대한 조건 지정
      let leftChildIndex = (poppedIndex * 2)
      let rightChildIndex = leftChildIndex + 1
      
      // case 1. 모든(왼쪽) 자식 노드가 없는 경우 (완전이진트리는 왼쪽부터 채워지므로, 이게 없으면 다 없는것임)
      if leftChildIndex >= heap.count {
          return .none
      }
      
      // case 2. 왼쪽 자식 노드만 있는 경우
      if rightChildIndex >= heap.count {
          return heap[leftChildIndex] < heap[poppedIndex] ? .left : .none //왼쪽 자식노드와 비교하여 왼쪽 자식노드가 작다면 그와 스와핑 해야함
      }
      
      // case 3. 왼쪽 & 오른쪽 자식 노드 모두 있는 경우
      // case 3-1. 자식들이 자신보다 모두 작은 경우
      if (heap[leftChildIndex] > heap[poppedIndex]) && (heap[rightChildIndex] > heap[poppedIndex]) {
          return .none
      }
      
      // case 3-2. 자식들이 자신보다 모두 큰 경우 (왼쪽과 오른쪽 자식 중 더 큰 자식 선별)
      if (heap[leftChildIndex] < heap[poppedIndex]) && (heap[rightChildIndex] < heap[poppedIndex]) {
          return heap[leftChildIndex] < heap[rightChildIndex] ? .left : .right
      }
      
      // case 3-3. 왼쪽 & 오른쪽 중 한 자식만 자신보다 큰 경우
      if (heap[leftChildIndex] < heap[poppedIndex]) || (heap[rightChildIndex] < heap[poppedIndex]) {
        return heap[leftChildIndex] < heap[poppedIndex] ? .left : .right
      }
        
      return .none
    }
    
    var poppedIndex = 1
    while true { //2. 이동한 루트 노드가 왼쪽, 오른쪽 자식 노드보다 작을 때까지 바꾸는 작업 진행
      switch moveDown(poppedIndex) {
      case .none: //바꿀 노드가 없음
          return poped
      case .left: //왼쪽 자식 노드와 바꿀 경우
          let leftChildIndex = poppedIndex * 2
          heap.swapAt(poppedIndex, leftChildIndex)
          poppedIndex = leftChildIndex
      case .right: //오른쪽 자식 노드와 바꿀경우
          let rightChildIndex = (poppedIndex * 2) + 1
          heap.swapAt(poppedIndex, rightChildIndex)
          poppedIndex = rightChildIndex
      }
    }

 

1️⃣ 자신의 왼쪽 자식 노드가 없는 경우

- *2를 했는데 그 인덱스가 비어있는 경우에는, 왼쪽/오른쪽 자식노드 둘다 없는것이기 때문에 비교할 대상이 없어서 자기 자신을 반환하면 된다.

- 자기 자신을 삭제된 원소로 가져오고 swap하는 작업을 더이상 진행할 필요가 없다.

    func moveDown(_ poppedIndex: Int) -> moveDownStatus { // 어떻게 이동할 지에 대한 조건 지정
      let leftChildIndex = (poppedIndex * 2)
      let rightChildIndex = leftChildIndex + 1
      
      // case 1. 모든(왼쪽) 자식 노드가 없는 경우 (완전이진트리는 왼쪽부터 채워지므로, 이게 없으면 다 없는것임)
      if leftChildIndex >= heap.count {
          return .none
      }

 

2️⃣ 현재 노드에서 왼쪽 자식 노드만 있고, 오른쪽 자식 노드가 없는 경우

- 자기 자신과 그 왼쪽 자식 노드만 비교해서, 왼쪽 자식노드가 더 작으면, 왼쪽 자식노드를 위로 올려야하므로 바꾸고 그렇지 않다면 멈춤

      // case 2. 왼쪽 자식 노드만 있는 경우
      if rightChildIndex >= heap.count {
          return heap[leftChildIndex] < heap[poppedIndex] ? .left : .none //왼쪽 자식노드와 비교하여 왼쪽 자식노드가 작다면 그와 스와핑 해야함
      }

 

3️⃣ 현재 노드에서 왼쪽 자식/오른쪽 자식 노드 둘 다 있을 때

- 자식 노드 2개가 둘다 현재보다 큰 경우, 둘중 하나가 큰 경우 3가지로 나누어 판단한다.

      // case 3. 왼쪽 & 오른쪽 자식 노드 모두 있는 경우
      // case 3-1. 자식들이 자신보다 모두 큰 경우 -> 바꿀 필요 없이 멈춤
      if (heap[leftChildIndex] > heap[poppedIndex]) && (heap[rightChildIndex] > heap[poppedIndex]) {
          return .none
      }
      
      // case 3-2. 자식들이 자신보다 모두 작은 경우 (왼쪽과 오른쪽 자식 중 더 큰 자식 선별)
      if (heap[leftChildIndex] < heap[poppedIndex]) && (heap[rightChildIndex] < heap[poppedIndex]) {
          return heap[leftChildIndex] < heap[rightChildIndex] ? .left : .right
      }
      
      // case 3-3. 왼쪽 & 오른쪽 중 한 자식만 자신보다 작은 경우
      if (heap[leftChildIndex] < heap[poppedIndex]) || (heap[rightChildIndex] < heap[poppedIndex]) {
        return heap[leftChildIndex] < heap[poppedIndex] ? .left : .right
      }

 

4️⃣ 바꿀 노드가 없을때까지 swap 반복

    var poppedIndex = 1
    while true { //2. 이동한 루트 노드가 왼쪽, 오른쪽 자식 노드보다 작을 때까지 바꾸는 작업 진행
      switch moveDown(poppedIndex) {
      case .none: //바꿀 노드가 없음 -> 멈추고 원소 반환
          return poped
      case .left: //왼쪽 자식 노드와 바꿀 경우
          let leftChildIndex = poppedIndex * 2
          heap.swapAt(poppedIndex, leftChildIndex)
          poppedIndex = leftChildIndex
      case .right: //오른쪽 자식 노드와 바꿀경우
          let rightChildIndex = (poppedIndex * 2) + 1
          heap.swapAt(poppedIndex, rightChildIndex)
          poppedIndex = rightChildIndex
      }

 

 

https://chanhuiseok.github.io/posts/ds-4/

https://jeonyeohun.tistory.com/325

https://babbab2.tistory.com/109