Heap 구현해보기
Heap?
•
트리를 사용하고, 트리 중에서도 완전이진트리를 기본으로 한 자료구조
•
주로 최소값과 최대값을 빠르게 찾기 위해서 사용
•
루트 노드를 최대값으로 사용하면 최대힙 (MaxHeap)
•
루트 노드를 최소값으로 사용하면 최소힙 (MinHeap)
시간 복잡도
•
삽입 : O(logN)
•
삭제 : O(logN)
구현
•
Array 를 사용하여 구현
•
값을 비교하기 위해 Comparable 프로토콜을 채택한 자료형에 대해서만 요소를 사용할 수 있도록 구현
struct Heap<T: Comparable> {
private var elements: [T] = []
}
Swift
복사
삽입
1.
완전이진트리의 마지막 요소에 삽입 (append)
2.
삽입된 요소를 부모 노드와 비교
•
최대힙이라면, 부모노드 보다 더 크다면 swap
•
최소힙이라면, 부모노드 보다 더 작다면 swap
3.
루트노드가 될 때까지 반복
struct Heap<T: Comparable> {
private var elements: [T] = []
mutating func insert(element: T) {
// 첫 번째 삽입시 0번째에 요소 할당 (0번 인덱스 사용X)
if elements.isEmpty {
elements.append(element)
elements.append(element)
return
}
elements.append(element)
swimUp(index: elements.count - 1)
}
mutating private func swimUp(index: Int) {
var index = index
// 자식노드 > 부모노드 라면 swap
// 루트노드라면 반복문을 탈출
while index > 1 && elements[index] > elements[index/2] {
elements.swapAt(index, index/2)
index /= 2
}
}
}
Swift
복사
삭제
1.
힙의 루트노드와 마지막 노드와 swap
2.
마지막 노드를 삭제
3.
루트노드와 자식노드를 비교
•
최대힙이라면, 자식노드보다 더 작으면 swap
•
최소힙이라면, 자식노드보다 더 크다면 swap
4.
3번을 반복
mutating func pop() -> T? {
if elements.count < 2 { return nil }
// 루트노드와 가장 마지막 노드를 swap
elements.swapAt(1, elements.count - 1)
let deletedElement = elements.removeLast()
diveDown(index: 1)
return deletedElement
}
mutating private func diveDown(index: Int) {
var swapIndex = index
var isSwap = false
let leftIndex = index * 2 // 왼쪽 자식노드
let rightIndex = index * 2 + 1 // 오른쪽 자식노드
// 왼쪽 자식노드가 있고, 왼쪽 자식노드가 더 크다면, 왼쪽 노드를 바꿀 노드로 정함
if leftIndex < elements.endIndex && elements[swapIndex] < elements[leftIndex] {
swapIndex = leftIndex
isSwap = true
}
// 오른쪽 자식노드가 있고, 오른쪽 자식노드가 더 크다면, 오른쪽 노드를 바꿀 노드로 정함
if rightIndex < elements.endIndex && elements[swapIndex] < elements[rightIndex] {
swapIndex = rightIndex
isSwap = true
}
// 바꿀 노드가 있다면, Swap
// 바꾼 노드에 대해서 diveDown
if isSwap {
elements.swapAt(swapIndex, index)
diveDown(index: swapIndex)
}
}
Swift
복사
전체 코드
import Foundation
struct Heap<T: Comparable> {
private var elements: [T] = []
mutating func insert(element: T) {
// 첫 번째 삽입시 0번째에 요소 할당 (0번 인덱스 사용X)
if elements.isEmpty {
elements.append(element)
elements.append(element)
return
}
elements.append(element)
swimUp(index: elements.count - 1)
}
mutating private func swimUp(index: Int) {
var index = index
// 자식노드 > 부모노드 라면 swap
// 루트노드라면 반복문을 탈출
while index > 1 && elements[index] > elements[index/2] {
elements.swapAt(index, index/2)
index /= 2
}
}
mutating func pop() -> T? {
if elements.count < 2 { return nil }
// 루트노드와 가장 마지막 노드를 swap
elements.swapAt(1, elements.count - 1)
let deletedElement = elements.removeLast()
diveDown(index: 1)
return deletedElement
}
mutating private func diveDown(index: Int) {
var swapIndex = index
var isSwap = false
let leftIndex = index * 2 // 왼쪽 자식노드
let rightIndex = index * 2 + 1 // 오른쪽 자식노드
// 왼쪽 자식노드가 있고, 왼쪽 자식노드가 더 크다면, 왼쪽 노드를 바꿀 노드로 정함
if leftIndex < elements.endIndex && elements[swapIndex] < elements[leftIndex] {
swapIndex = leftIndex
isSwap = true
}
// 오른쪽 자식노드가 있고, 오른쪽 자식노드가 더 크다면, 오른쪽 노드를 바꿀 노드로 정함
if rightIndex < elements.endIndex && elements[swapIndex] < elements[rightIndex] {
swapIndex = rightIndex
isSwap = true
}
// 바꿀 노드가 있다면, Swap
// 바꾼 노드에 대해서 diveDown
if isSwap {
elements.swapAt(swapIndex, index)
diveDown(index: swapIndex)
}
}
}
Swift
복사