[Data Structure] Heap

오늘 알아볼 데이터 구조는 Heap(힙) 입니다.

 

Heap 또한 이전 시간에 알아본 Trie 처럼 기본 구조는 Tree(트리) 형태입니다.

Heap의 경우 모든 노드가 두개의 자식노드만 갖는 Complete Binary Tree(완전이진트리)입니다.

주로 최대값, 최소값을 구하는 연산에 주로 사용됩니다.

출처: https://en.wikipedia.org/wiki/Heap_(data_structure)

특징

- 모든 부모 Node와 자식 Node 간의 Key 값은 항상 대소관계를 갖습니다.

- 대소관계에 따라 부모 Node의 Key 값이 자식 Node보다 큰 Heap을 Max Heap(최대 힙),

반대로 자식 Node의 Key 값이 부모 Node보다 큰 Heap을 Min Heap(최소 힙)이라고 합니다.

- 검색 및 삽입 Time Complexity는 Binary Tree의 속성에 따라 O(logN)입니다.

- 모든 노드들이 부모, 자식 간의 대소관계 규칙만 따를뿐이기 때문에 단순 순회를 통해서 정렬된 값을 얻을 수는 없습니다.

 

구현(Tree)

Tree 구조의 형태로 Max Heap을 구현해봅시다.

1. HeapNode 클래스 구현

class HeapNode<T: Comparable> {
    var key: T
    var leftNode: HeapNode?
    var rightNode: HeapNode?
    var parentNode: HeapNode?

    init(_ key: T) {
        self.key = key
    }
}

 

Key 타입으로는 Generic을 사용합니다.

대소비교가 가능해야하기 때문에 Comparable 프로토콜을 준수해야합니다.

2. 삽입(Insert) 구현

class Heap<T: Comparable> {
    var root: HeapNode<T>?
    var count = 0
    var lastInsertedNode: HeapNode<T>?  // 삽입된 마지막 노드를 추적
    
    // MaxHeap에 값을 삽입하는 함수
    func insert(_ value: T) {
        let newNode = HeapNode(value)
        guard let root = root else {
            root = newNode
            lastInsertedNode = newNode
            count += 1
            return
        }
        
        // Find Insert Position
        var queue: [HeapNode<T>] = [root]
        var queuePointer = 0
        while !queue.isEmpty {
            let node = queue[queuePointer]
            queuePointer += 1
            if node.leftNode == nil {
                node.leftNode = newNode
                newNode.parentNode = node
                lastInsertedNode = newNode
                break
            }
            if node.rightNode == nil {
                node.rightNode = newNode
                newNode.parentNode = node
                lastInsertedNode = newNode
                break
            }
            queue.append(node.leftNode!)
            queue.append(node.rightNode!)
        }
        
        // Max Heap
        var currentNode: HeapNode? = newNode
        while currentNode!.key > currentNode!.parentNode!.key {
            swap(&currentNode!.key, &currentNode!.parentNode!.key)
            currentNode = currentNode?.parentNode
            if currentNode?.parentNode == nil {
                break
            }
        }
        
        count += 1
    }
}

 

Heap의 크기가 2 이상이라면, 노드가 들어갈 자리를 먼저 찾고, Max Heap의 규칙에 맞게 노드를 swap합니다.

3. 삭제

// in Heap Class
func remove() -> T? {
    guard let root = root else { return nil }
    let maxValue = root.key
    if count == 1 {
        self.root = nil
    } else {
        if let lastNode = lastInsertedNode {
            root.key = lastNode.key
            
            if let parent = lastNode.parentNode {
                if parent.rightNode === lastNode { parent.rightNode = nil }
                else { parent.leftNode = nil }
                
                var queue: [HeapNode<T>] = [root]
                var queuePointer = 0
                var lastNode: HeapNode<T>? = root
                
                while queuePointer < queue.count {
                    let node = queue[queuePointer]
                    queuePointer += 1
                    lastNode = node
                    if let left = node.leftNode { queue.append(left) }
                    if let right = node.leftNode { queue.append(right) }
                }
                
                lastInsertedNode = lastNode
            }
            
            var currentNode: HeapNode? = root
             while currentNode?.leftNode != nil {
                 var largerChild = currentNode!.leftNode
                 if let rightNode = currentNode?.rightNode {
                     if rightNode.key > currentNode!.leftNode!.key {
                         largerChild = currentNode!.rightNode
                     }
                 }
                 if largerChild!.key <= currentNode!.key { break }
                 swap(&largerChild!.key, &currentNode!.key)
                 currentNode = largerChild
             }
        }
    }
    count -= 1
    return maxValue
}

 

Max Heap이기 때문에 remove시에 최대값을 반환합니다.

최대값의 경우 root의 key입니다.

이후 마지막에 삽입된 노드(lastInsertedNode)를 root로 이동시키고, lastInsertedNode를 갱신시킵니다.

마지막으로 Max Heap의 규칙에 맞게 트리를 수정합니다.

4. 최대값 조회

// in Heap Class
func peek() -> T? {
    root?.key
}

테스트

상단에 예제 이미지의 데이터로 준비했습니다.

var heap = Heap<Int>()
let data = [2, 7, 19, 3, 100, 36, 25, 1]
data.forEach {
    heap.insert($0)
    if let maxValue = heap.peek() {
        print(maxValue, terminator: ", ")
    }
}
print()
// 2, 7, 19, 19, 100, 100, 100, 100, 

var sortedData: [Int] = []
while heap.count > 0 {
    if let maxValue = heap.remove() {
        sortedData.append(maxValue)
    }
}
print(sortedData)
// [100, 36, 25, 19, 7, 3, 2, 1]

 

데이터를 추가할 때마다 최대값을 확인할 수 있도록 했습니다.

또한 데이터를 순차적으로 뽑으면, 값을 정렬한 데이터를 얻을 수도 있습니다.

Conclusion

실제로는 Heap 자체를 구현하기보단 Heap의 특징을 활용하여 문제를 해결하는 경우가 많습니다.

또한 Heap은 Array를 이용해서도 구현이 가능합니다.

구조의 특성을 잘 이해한 후에 Array를 이용한 Heap도 꼭 구현해보면 좋을거같습니다.