[자료구조] Heap
자료구조 06 / Heap
정의
정의
Heap : 데이터에서 최대값과 최소값을 빠르게 찾는 완전 이진트리 구조 (Complete Binary Tree)
* 완전 이진트리 : Node를 삽입 할때 최하단 왼쪽 Node 부터 차례대로 삽입
힙의 기능
일반적으로 최대값, 최소값을 찾을때 기대값 O(n)
힙에 데이터를 넣는다면 O(logn)
최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현등에 활용
구조
Max Heap 구조
1) 각 노드의 값은 해당 노드의 자식노드가 가진 값 보다 크거나 같음
2) 완전 이진트리 형태
Min Heap 구조
1) 각 노드의 값은 해당노드의 자식노드가 가진 값보다 작거나 같음
2) 완전 이진트리 형태
구현
배열을 이용한 Heap 구현
일반적으로 배열로 구현 (완전 이진트리 형태라서 가능)
부모Node index = 자식Node index - 1 / 2
Left자식 index = 부모Node index * 2 + 1
Right 자식 index = 부모Node index * 2 + 2
Implementing a Swift Heap
struct Heap<Element> {
var elements : [Element]
let priorityFunction : (Element, Element) -> Bool
}힙을 배열(완전이진트리)로 표현, 두 요소중 앞에 요소가 더 큰경우 true
Simple functions
extension Heap<Element> {
var isEmpty : Bool {
return elements.isEmpty
}
var count : Int {
return elements.count
}
func peek() -> Element? {
return elements.first
}
func isRoot(_ index: Int) -> Bool {
return (index == 0)
}
func leftChildIndex(of index: Int) -> Int {
return (2 * index) + 1
}
func rightChildIndex(of index: Int) -> Int {
return (2 * index) + 2
}
func parentIndex(of index: Int) -> Int {
return (index - 1) / 2
}
}Comparing priority
extension Heap<Element> { // Comparing priority
func isHigherPriority(at firstIndex: Int, than secondIndex: Int) -> Bool {
return priorityFunction(elements[firstIndex], elements[secondIndex])
}
func highestPriorityIndex(of parentIndex: Int, and childIndex: Int) -> Int {
guard childIndex < count && isHigherPriority(at: childIndex, than: parentIndex)
else { return parentIndex }
return childIndex
}
func highestPriorityIndex(for parent: Int) -> Int {
let higherBetweenParentAndLeft = highestPriorityIndex(of: parent, and: leftChildIndex(of: parent))
return highestPriorityIndex(of: higherBetweenParentAndLeft, and: rightChildIndex(of: parent))
}
mutating func swapElement(at firstIndex: Int, with secondIndex: Int) {
guard firstIndex != secondIndex else { return }
swap(&elements[firstIndex], &elements[secondIndex])
}
}Enqueueing a new element
mutating func enqueue(_ element: Element) {
elements.append(element)
siftUp(elementAtIndex: count - 1)
}
mutating func siftUp(elementAtIndex index: Int) {
let parent = parentIndex(of: index) // 1
guard !isRoot(index), isHigherPriority(at: index, than: parent) else { return } // 2, 3
swapElement(at: index, with: parent) // 4
siftUp(elementAtIndex: parent) // 5
}1. 부모 인덱스 / 2. 해당 인덱스가 루트 (0) 인지 확인 / 3. 부모노드 보다 수가 크면 return
4. 자식노드가 더 크므로 부모노드와 자식노드 Swap -> 5. 부모노드에서 다시 확인
Dequeueing the highest priority element
mutating func dequeue() -> Element? {
guard !isEmpty else { return nil }
swapElement(at: 0, with: count - 1) // 2
let element = elements.removeLast() // 3
if !isEmpty { // 4
siftDown(elementAtIndex: 0) // 5
}
return element // 6
}
mutating func siftDown(elementAtIndex index: Int) {
let childIndex = highestPriorityIndex(for: index) // 1
if index == childIndex { return } // 2
swapElement(at: index, with: childIndex) // 3
siftDown(elementAtIndex: childIndex)
}Main
var heap = Heap(elements: [3, 2, 8, 5, 0], priorityFunction: >)'>' Maxheap / '<' Minheap
Build()
extension Heap<Element> {
init(elements: [Element] = [],
priorityFunction: @escaping (Element, Element) -> Bool) {
self.elements = elements
self.priorityFunction = priorityFunction // 3
buildHeap() // 4
}
mutating func buildHeap() {
for index in (0 ..< count / 2).reversed() { // 5
siftDown(elementAtIndex: index) // 6
}
}
결론
이진 탐색 트리 (Binary Search Tree) & Heap (완전 이진 트리)
공통점 : 모두 Binary Tree
차이점 : Heap <> Binart Search Tree
1. 자식노드가 어떤게 클지 알 수 없음 (추가되는 순서) <> 자식노드 왼쪽이 오른쪽 보다 작은 값
2. 최대 / 최소값 검색을 위한 구조 <> 탐색을 위한 구조
시간 복잡도
트리의 높이 death, h
n개의 노드를 가지는 Heap에 데이터 삽입 또는 삭제 시,
최악 root 노드에서 leaf 노드까지 비교 h = log₂n -> O(logn)
구현 코드 : raywenderlich.com