힙(Heap)

저희가 여러 개의 값을 담기 위해 주로 배열을 사용하잖아요?

그리고 이 배열에서 값들을 넣었다가 뺏다가 하면서 사용하죠.

그럼 Heap은 왜 쓰냐? -> 최댓값 또는 최솟값을 효율적으로 알아내기 위해 사용합니다.

 

힙(Heap)이란?

힙은 완전 이진트리의 형태로 만들어진 자료구조입니다.

완전 이진 트리

완전 이진트리란 노드를 삽입할 때 왼쪽부터 순차적으로 삽입하는 트리입니다.

예를 들면 위의 완전 이진트리에서 G노드를 삽입시키려면 D 아래에 G노드가 생기는 게 아니라 C아래에 G가 생깁니다.

ABCDEF순으로 노드 삽입

 

그런데 아까 제까 힙은 최댓값 or 최솟값을 효율적으로 구하기 위해 사용하는 자료구조 라고 했는데,

새로운 값을 삽입하면 어떻게 배열 전체를 살펴보지 않고도 최댓값 또는 최솟값을 구할 수 있는 걸까요?

 

최대 힙의 특징 중 하나는 부모 노드는 자식 노드보다 항상 큽니다. 그러므로 만약 자식 노드가 부모 노드보다 더 큰 노드가 삽입되면

부모 노드와 자식 노드의 값을 서로 바꾸는 작업 해서 A 자리 항상 최댓값이 되도록 유지합니다. 

A 자리가 항상 최댓값이 되도록 유지하는 작업O(logN)이 전체 배열을 찾아보는 것(O(n))보다 연산을 덜 하기 때문에 훨씬 효율적으로 최댓값을 구할 수 있는 것이지요.

 

힙의 종류

힙의 종류는 최대힙과 최소 힙이 있습니다.

최대 힙이면 A 자리 항상 최댓값이 자리하고 있고, 최소 힙이면 최솟값이 자리하고 있습니다.

 

힙 구현

힙 삽입

최대힙 삽입

1. 일단 새롭게 들어온 값을 넣어준다.
2.  부모노드와 비교해서 자리를 바꾼다.

// 최대힙
class Heap {
    var arr: [Int] = [0]
    
    func insert(_ element: Int) {
        heap.append(element)

        var currentIndex = heap.count - 1
        var parentsIndex = currentIndex / 2
        
        while canSwap() {
            heap.swapAt(currentIndex, parentsIndex)
            currentIndex = parentsIndex
            parentsIndex = currentIndex / 2
        }
        
        func canSwap() -> Bool {
            guard currentIndex > 1 else { return false }
            
            // < 이면 최소힙
            return heap[currentIndex] > heap[parentsIndex] ? true : false
        }
    }
}

var heap = Heap()
heap.insert(4)
heap.insert(3)
heap.insert(2)
heap.insert(5)
print(heap.arr) // [0, 5, 4, 2, 3] 0은 구현을 쉽게 하기 위한 요소

 

힙 꺼내기

1. 첫번째 노드와 마지막 노드를 바꾸고, 마지막 노드를 제거합니다.
2. 최댓값 자리의 왼쪽 자식노드와 오른쪽 자식 노드를 비교합니다.
3. 3번에서 비교한 것을 가지고 힙 삽입할 때와 마찬가지로 최댓값 자리로 옮겨온 노드와 비교 후 자리를 바꿉니다.

힙 꺼내기

 

// MARK: - 최대힙

class Heap {
    var heap: [Int] = [0, 6 , 5 ,4, 3, 2]
    
    func insert(_ element: Int) {
        heap.append(element)

        var currentIndex = heap.count - 1
        var parentsIndex = currentIndex / 2
        
        while canSwap() {
            heap.swapAt(currentIndex, parentsIndex)
            currentIndex = parentsIndex
            parentsIndex = currentIndex / 2
        }
        
        func canSwap() -> Bool {
            guard currentIndex > 1 else { return false }
            
            // < 이면 최소힙
            return heap[currentIndex] > heap[parentsIndex] ? true : false
        }
    }
    
    func pop() -> Int? {
          heap.swapAt(1, heap.count - 1)
          let out = heap.removeLast()
          
          var parentsIndex = 1
          var leftIndex = parentsIndex * 2
          var rightIndex = leftIndex + 1
          var childIndex = 0
          
          while parentsIndex < heap.count {
              
              // 왼쪽노드만 있을 경우
              if rightIndex >= heap.count && leftIndex < heap.count {
                  childIndex = leftIndex
              }
              // 둘 다 없을 경우
              else if rightIndex >= heap.count && leftIndex >= heap.count {
                  return out
              }
              // 둘 다 있을 경우
              else if rightIndex < heap.count && leftIndex < heap.count {
                  // < 이면 최소힙
                  childIndex = heap[leftIndex] > heap[rightIndex] ? leftIndex : rightIndex
              }
              
              // < 이면 최소힙
              if heap[childIndex] > heap[parentsIndex] {
                  heap.swapAt(childIndex, parentsIndex)
                  
                  parentsIndex = childIndex
                  leftIndex = parentsIndex * 2
                  rightIndex = leftIndex + 1
              } else {
                  return out
              }
          }
        
        return out
    }
}

var heapObject = Heap()

heapObject.insert(8)
print(heapObject.heap) // [0, 8, 5, 6, 3, 2, 4]
heapObject.pop()
print(heapObject.heap) // [0, 6, 5, 4, 3, 2]

 

힙을 공부 했으니 스스로 생각해서 짤 수 있는지 알고리즘 문제를 통해 연습합시다!!!

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

우선순위 큐 문제로 최소 힙을 이용하여 풀 수 있는 기본적인 문제입니다.

 

<풀이 보러 가기>