Heap

Heap

• 두개의 속성을 만족하는 트리
• 1) 형태 속성: 힙은 완전 이진트리(모든 노드가 채워져 있고 왼쪽에서 오른쪽으로 채워진 형태)
• 2) 힙 속성: 모든 노드의 데이터는 자식 노드들의 데이터 보다 크거나 같다
• 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조(최대힙 & 최소힙)
• 시간복잡도는 O(logN)
• 배열에 넣고 최대값 & 최소값을 찾으려면 O(n)이 걸리지만 힙으로 구현할 경우 O(logN)구현 가능(우선순위 큐)

최대힙과 최소힙

최대힙 : 내 자식 노드의 값은 내 값보다 작거나 같아야 한다(Root노드 최대 값)

최소힙 : 내 자식 노드의 값은 내 값보다 크거나 같아야 한다(Root노드 최소 값)

Index 계산

부모 index : 자식 index / 2

왼쪽자식: index * 2

오른쪽 자식 : index * 2 + 1

Heap 데이터 추가

1. 최대힙에서 40의 데이터를 추가

2. 추가된 데이터가 부모 노드의 값보다 작을 때까지 swap

Heap 데이터 추출

1. 루트노드 데이터 추출 및 삭제

2. 가장 마지막에 추가된 노드 Root노드로 이동

3. 이동된 Root노드와 자식노드를 비교하여 자식노드중 큰값을 가진 노드와 swap

 

Heap 구현 코드

import Foundation

struct Heap<T: Comparable> {
    var elements: [T] = []
    let sort: (T, T) -> Bool
    
    init(elements: [T] = [], sort: @escaping (T, T) -> Bool) {
        self.sort = sort
        
        if !elements.isEmpty {
            self.elements = [elements.first!] + elements // 초기
        } else {
            self.elements = elements
        }
        
        if elements.count > 0 {
            for i in stride(from: elements.count / 2 - 1, through: 1, by: -1) {
                self.shiftDown(i)
            }
        }
    }
    
    func leftChildIndex(of index: Int) -> Int {
        return index * 2
    }
    
    func rightChildIndex(of index: Int) -> Int {
        return index * 2 + 1
    }
    
    func parentIndex(of index: Int) -> Int {
        return index / 2
    }
    
    mutating func shiftDown(_ index: Int) {
        var parentIndex = index
        
        while true {
            let leftIndex = leftChildIndex(of: parentIndex)
            let rightIndex = rightChildIndex(of: parentIndex)
            var candidate = parentIndex
            
            if leftIndex < self.elements.count && self.sort(self.elements[leftIndex], self.elements[candidate]) {
                candidate = leftIndex
            }
            if rightIndex < self.elements.count && self.sort(self.elements[rightIndex], self.elements[candidate]) {
                candidate = rightIndex
            }
            if candidate == parentIndex {
                return
            }
            self.elements.swapAt(parentIndex, candidate)
            parentIndex = candidate
        }
    }
    
    mutating func shiftUp(_ index: Int) {
        var childIndex = index
        
        while true {
            let parentIndex = parentIndex(of: childIndex)
            
            if childIndex > 1 && sort(self.elements[childIndex], self.elements[parentIndex]) {
                elements.swapAt(childIndex, parentIndex)
                childIndex = parentIndex
            } else {
                return
            }
        }
    }
    
    mutating func insert(_ data: T) {
        if elements.count == 0 {
            elements.append(data)
            elements.append(data)
            return
        }
        
        elements.append(data)
        
        let insertIndex = elements.count - 1
        self.shiftUp(insertIndex)
    }
    
    mutating func pop() -> T? {
        if self.elements.count <= 1 { return nil }
        self.elements.swapAt(1, elements.count - 1)
        let data = elements.removeLast()
        self.shiftDown(1)
        
        return data
    }
}

var heap = Heap.init(elements: [50], sort: <)
heap.insert(100)
heap.insert(30)
heap.insert(20)
heap.insert(40)
heap.insert(10)

print(heap.pop()) // Optional(10)
print(heap.pop()) // Optional(20)
print(heap.pop()) // Optional(30)
print(heap.pop()) // Optional(40)
print(heap.pop()) // Optional(50)
print(heap.pop()) // Optional(100)