Heap

Heap 이란?

힙은 루트에 가장 힙한 녀석을 두는 이진 트리이다. (응?)
루트에 항상 최대 또는 최소값을 두기 때문에 최대 최소값을 빠르게 얻을 수 있다. O(1)

힙은 완전 이진트리의 모습을 띄는데, 부모 노드가 자식 노드보다 크거나(최대힙) 작은지(최소힙) 만을 보장한다.
즉, 자식노드 끼리는 큰지 작은지를 비교할 수가 없다.
힙은 배열로 구현하면 공간, 시간 복잡도 측면에서 좋기 때문에 배열로 많이 구현한다.

배열로 구현했을 때 다음과 같이 인덱스를 구할 수 있다.

parent: floor((i-1) / 2) 
left:       2i + 1
right:     2i + 2

인덱스를 1부터 시작하면 parent: i/2, left: 2i, right: 2i+1 로 구할 수도 있다.
잘 보면 오른쪽 노드 = 왼쪽노드 + 1 로 옆에 차곡차곡 쌓이는 이진트리임을 다시 한번 확인할 수 있다.

따라서 마찬가지로

이진트리의 원리들이 적용된다.

힙의 높이:  floor(log2(n)),
노드가 가득 차 있고 층의 높이를 k 라고 한다면 (층: 0~k)
특정 층의 노드의 개수:              2^(k),
해당 층을 제외한 노드의 개수:   2^(k) - 1
모든 노드의 개수:                      2^(k+1) - 1

 

삽입/삭제 O(log n)

삽입 삭제를 살펴보기 전에 근본이 되는 개념부터 알아보자.

힙은 모두 정렬되어 있는 것이 아니라 루트 노드만 최대/최소인지를 보장하면 된다.
삽입/삭제 역시 문제가 되는 녀석과 부모 혹은 자식 노드와 비교해 제 자리를 찾아주기만 하면 된다.
따라서 시간 복잡도는 O(log n)이다.

제 자리를 찾아주는 방법은 두 가지가 있다.
shiftUp, shiftDown 이라고 부르는데,

\

shiftUp 이란 자식 노드가 부모 노드와 비교해서 바꿔야 하는지 보고 바꾸는 것이다.
shiftDown 이란 부모 노드가 자식노드 (left, right) 노드와 비교해서 바꿔야 하는지 보고 바꾸는 것이다.

\

 

이제 본격적으로 힙의 삽입 삭제는 어떻게 이뤄지는지 살펴보자.

힙의 삽입 삭제는 모두 마지막 노드와 관련되어 있다.

 

힙을 삽입할 때는

마지막 노드에 삽입한 뒤 shifhtUp을 통해서 부모 노드와 자리를 바꿔야 할 지 확인한다.
삽입: 삽입 —> 자식 shiftUp

 

힙을 삭제할 때는

마지막 노드와 부모 노드를 바꾼 뒤에 shiftDown을 통해서 자식 노드와 바꿔야 할 지를 확인한다.
삭제: 마지막 ↔ 루트 —> 마지막 삭제 —> 루트 shiftDown

먼저 루트를 제거하고 마지막 노드를 루트로 올려도 된다.

 

그럼 중간에 특정 노드를 삭제하고 싶다면?
역시 마지막 노드와 해당 노드를 바꿔주고 shiftDown, shiftUp을 해주면 된다.

 

구현

import Foundation

public struct Heap<T> {
    
    var nodes = [T]()
    
    private var orderCriteria: (T, T) -> Bool
    
    public init(sort: @escaping (T, T) -> Bool) {
        // 최대 힙인지 최소 힙인지 기준을 잡는다.
        self.orderCriteria = sort
    }
    
    public init(array: [T], sort: @escaping (T, T) -> Bool) {
        self.orderCriteria = sort
        configureHeap(from: array)
    }
    
    // 변수를 직접 변경해야 하기 때문에 mutating 을 사용한다.
    private mutating func configureHeap(from array: [T]) {
        nodes = array
        
        /**
         * 힙 트리에서 n/2 - 1 은 하나 위 층위가 된다.
         * shiftDown을 하면서 자리를 잡을 것이기 때문에
         * 마지막 leaf 노드들은 할 필요가 없다.
         */
        for i in stride(from: nodes.count/2 - 1, through: 0, by: -1) {
            shiftDown(i)
        }
    }
    
    func parentIndex(ofIndex i: Int) -> Int {
        return (i - 1) / 2
    }
    
    func leftChildIndex(ofIndex i: Int) -> Int {
        return 2*i + 1
    }
    
    func rightChildIndex(ofIndex i: Int) -> Int {
        return 2*i + 2
    }
    
    public func peek() -> T? {
        return nodes.first
    }
    
    public mutating func insert(_ value: T) {
        nodes.append(value)
        shiftUp(nodes.count - 1)
    }
    
    public mutating func remove() -> T? {
        guard !nodes.isEmpty else { return nil }
        
        if nodes.count == 1 {
            return nodes.removeLast()
        } else {
            let value = nodes[0]
            nodes[0] = nodes.removeLast()
            shiftDown(0)
            return value
        }
    }
    
    public mutating func remove(at index: Int) -> T? {
        guard index < nodes.count else { return nil }
        
        let lastIndex = nodes.count-1
        if index != lastIndex {
            nodes.swapAt(index, lastIndex)
            shiftDown(from: index, until: lastIndex)
            shiftUp(index)
        }
        
        return nodes.removeLast()
    }
    
    /**
     * shiftUp은 자신과 부모를 비교해 바꿔준다.
     */
    mutating func shiftUp(_ index: Int) {
        var childIndex = index
        let child = nodes[childIndex] // 처음에 노드를 저장해두고 인덱스를 구한 후 바꿔준다.
        var parentIndex = self.parentIndex(ofIndex: index)
        
        while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) {
            nodes[childIndex] = nodes[parentIndex]
            childIndex = parentIndex
            parentIndex = self.parentIndex(ofIndex: childIndex)
        }
        
        nodes[childIndex] = child
    }
    
    /**
     * shiftDown은 left, right 자식 중 적합한 녀석이 있으면 바꾸면서 바닥까지 내려간다.
     */
    mutating func shiftDown(from index: Int, until endIndex: Int) {
        let leftChildIndex = self.leftChildIndex(ofIndex: index)
        let rightChildIndex = leftChildIndex + 1
        
        var first = index
        if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) {
            first = leftChildIndex
        }
        if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) {
            first = rightChildIndex
        }
        if first == index { return }
        
        nodes.swapAt(index, first)
        shiftDown(from: first, until: endIndex)
    }
    
    mutating func shiftDown(_ index: Int) {
        shiftDown(from: index, until: nodes.count)
    }
    
}

extension Heap where T: Equatable {
    
    /** 특정 노드의 index 얻기. O(n) */
    public func index(of node: T) -> Int? {
        return nodes.firstIndex(where: { $0 == node })
    }
    
    public mutating func remove(node: T) -> T? {
        if let index = index(of: node) {
            return remove(at: index)
        }
        return nil
    }
}