21.06.26
공부한 것을 정리하는 용도의 글이므로 100% 정확하지 않을 수 있습니다.
참고용으로만 봐주시고, 내용이 부족하다고 느끼신다면 다른 글도 보시는 것이 좋습니다.
+ 틀린 부분, 수정해야 할 부분은 언제든지 피드백 주세요. 😊
by. ryalya
들어가기 전
자료구조(Data Structure)란?
- 컴퓨터상 자료를 효율적으로 저장하기 위해 만들어진 논리적인 구조.
- 자료 구조의 현명한 선택을 통해 효율적인 알고리즘을 사용할 수 있게 하여 성능을 향상시킴.
Heap이란?
- 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조.
- 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾을 때 유용한 자료구조.
장점
- 메모리 크기 제한 無
- 프로그램의 모든 함수에서 Access할 수 있음. ( 범위가 전역이기 때문 )
단점
- 할당 및 해제 작업으로 인한 속도 저하
- 힙 손상(이중 해제, 해제 후 사용 등)으로 인한 속도 저하
- 힙 경합(두 개 이상의 스레드가 동시에 접근할 때, Lock이 걸림)으로 인한 속도 저하
- 메모리를 직접 관리해야 함.
이진 트리란 → 차수(Degree)가 2이하의 노드로 구성되어 자식이 둘 이하로 구성된 트리.
완전 이진 트리란 → 이진 트리의 유형으로 마지막 레벨을 제외하고 노드가 채워진 트리.
아래 그림과 같은 형태를 가지고 있다.
Heap은 몇 가지 특징을 가지고 있다.
-
부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나(Max Heap) 항상 작다(Min Heap).
따라서 Heap의 트리는 항상 느슨한 정렬상태(반정렬 상태)를 유지하고 있다. -
Heap 트리는 중복값을 허용한다.
-
수행시간이 O(logN)
Heap 종류
최대힙 (Max Heap)
- 부모노드의 키 값이 자식노드의 키 값보다 항상 크거나 같다.
최소힙 (Min Heap)
- 부모노드의 키 값이 자식노드의 키 값보다 항상 작거나 같다.
Heap 구현
-
Heap은 대체적으로 배열로 구현이 된다.
-
왼쪽 자식의 index : (부모 index) * 2
-
오른쪽 자식의 index : (부모 index) * 2+1
-
특정 자식 노드에서 부모 index : (자식 index) / 2
Heap 연산
Heap에서 삽입이 일어나든 삭제가 일어나든 간에 최대힙/최소힙의 조건(성질)이 깨질 수 있다.
따라서 조건을 만족하는지 확인하는 과정과 조건을 만족할 때 까지 부모와 자식의 위치를 바꾸어야 한다.
아래 구현 코드들은 스위프트 힙 자료구조를 참고했다.
설명이 너무 잘 되어 있어서 이해가 쉽게 갔음.
Heap 구현 (코드)
struct Heap<Element: Comparable> {
// 값에 Comparable 프로토콜 채택하게한 건 sort 에 <,> 넣을 거라서
var elements: [Element] = []
// 배열로 구현할거야. 트리는 O(log n) / 배열은 O(1) random access
let sort: (Element, Element) -> Bool // 함수임 , < 이나 > 용도로 쓸거임
init(sort: @escaping (Element,Element) -> Bool, elements: [Element] = []) {
// sort 에 < , > 넣는거 개꿀딴지^^
// @escaping : 클로져가 함수의 매개변수로 쓰일 때 그 함수가 리턴한 후에도 클로져가 호출될때 escaping 필요
self.sort = sort
self.elements = elements
if !elements.isEmpty {
for i in stride(from: elements.count / 2 - 1, through: 0, by: -1){
// 랜덤한 배열을 Heap 구조로 바꿈
// stride 는 글로벌함수로 for 문의 반복 설정할때
siftDown(from: i)
}
}
}
var isEmpty: Bool {
return elements.isEmpty
}
var count: Int {
return elements.count
}
func peek() -> Element? {
return elements.first
}
func leftChildIndex(ofParentAt index: Int) -> Int {
return 2*index + 1
}
func rightChildIndex(ofParentAt index: Int) -> Int {
return 2*index + 2
}
func parentIndex(ofChildAt index: Int) -> Int {
return (index - 1) / 2
}삽입 연산
- 트리의 가장 마지막 위치에 노드를 삽입.
- 새로 삽입된 노드와 부모 노드가 힙의 성질(조건)을 만족하는지 확인.
- 만족하지 않는다면 부모와 자식의 키 값을 바꾼다.
- 조건에 만족하거나 추가된 노드가 루트에 도달할 때 까지 2~3을 반복.
(logn)
insert
mutating func insert(_ element: Element) {
// append 는 O(1), siftUp 은 O(log n) 이므로 전체 효율은 O(log n)
elements.append(element)
siftUp(from: elements.count - 1)
}
mutating func siftUp(from index: Int) {
var child = index // 마지막 인덱스
while true {
let parent = parentIndex(ofChildAt: child)
if child > 0 && sort(elements[child], elements[parent]) { // > 이니까
elements.swapAt(child, parent)
child = parent
}else {
return
}
}
/* // 이렇게도 작성할 수 있음.
var parent = parentIndex(ofChildAt: child)
while child > 0 && sort(elements[child], elements[parent]) {
elements.swapAt(child, parent)
child = parent
parent = parentIndex(ofChildAt: child)
}*/
}삭제 연산
- 항상 루트 노드를 삭제한다.
- 트리의 가장 마지막 노드를 루트 자리로 삽입시킨다.
- 노드가 힙 조건을 만족하는지 확인.
- 만족하지 않는다면 왼쪽 자식과 오른쪽 자식 중 적합한 노드와 키 값을 바꾼다.
- 조건을 만족하거나 리프 노드에 도달할 때 까지 3~4를 반복한다.
(logn)
Remove
mutating func remove() -> Element? {
// swap 은 O(1) 이고 sifhDown 은 O(log n) 이라서 전체 시간복잡도 O(log n)
guard !isEmpty else { // 비어있지 않으면 삭제 연산 진행할것
return nil
}
elements.swapAt(0, count - 1) // Array 의 swapAt 메소드 활용
defer {
// defer 키워드는 { } 실행구문 안의 로직을 가장 마지막에 실행하도록 순서를 보장해주는 역할
// 어디 위치에 있어서 실행 순서는 가장 마지막.
siftDown(from: 0) // 루트노드 sift Down
}
return elements.removeLast() // 삭제할 노드 삭제후 반환하기.
}
mutating func siftDown(from index: Int) {
// 이 메소드가 실행될 시점에선 배열의 가장 크거나 작은 놈이 루트노드가 되어있는 시점임.
var parent = index
while true {
let left = leftChildIndex(ofParentAt: parent)
let right = rightChildIndex(ofParentAt: parent)
// left, right 가 parent 가 변함에 따라 변하니까 var 라고 하기 쉬운데
// while 의 { } 입장에서는 변하지 않는 값이므로 let 임을 유의
var candidate = parent // 탐색할 아이 지정
if left < count , sort(elements[left], elements[candidate]) {
// 왼쪽 자식노드가 있고, 그 자식노드 값이 부모노드 값보다 크다면
candidate = left
}
if right < count , sort(elements[right], elements[candidate]) {
candidate = right
}
if candidate == parent { // 종료조건
// return 만날때까지 무한반복, 위의 조건에 부합하지 않는 순서일 때 return 하는 것.
return
}
elements.swapAt(parent, candidate)
parent = candidate
}
}remove(at:)
mutating func remove(at index: Int) -> Element? {
guard index < elements.count else { return nil }
// 위에 정의한 count 를 쓰지않은 이유는 count 는 Heap 인스턴스에서 count를 알려고 하는 거고
// 인스턴스의 메소드가 실행될떄마다 값이 바뀔 가능성 있음.
if index == elements.count - 1 {
return elements.removeLast()
}else {
elements.swapAt(index, elements.count-1) // 제거하려는 값은 맨 뒤로 보내기~
siftDown(from: index) // index 자리 기준으로 아랫쪽 재정렬
siftUp(from: index) // index 자리 기준으로 위쪽 재정렬
}
return elements.removeLast()
}index(of: , startingAt: ) : 주어진 값에 해당하는 인덱스 찾기, 범위 설정
// 모든 노드 한번씩 탐색해야 하기 때문에 O(n) 최악
// 탐색 메소드는 트리는 O(log n) 임. 배열이 더 안좋아.
func index(of element: Element, startingAt i:Int) -> Int? {
// 값, 시작 인덱스를 주고 , 값에 해당하는 인덱스 있으면 인덱스 반환 , 없으면 nil
// 모든 경우의 수 다 생각해야함 ㅠㅠ. 극혐
if i >= count {
return nil
}
if sort(element, elements[i]) {
// max heap 이면 > , min heap 이면 < 인데
// > 이면 elements[i] 이 max 인데 찾고자 하는 element 가 더 크므로 범위 초과
// < 이면 elements[i] 이 min 인데 찾고자 하는 element 가 더 작으므로 범위 초과
return nil
}
if element == elements[i] { // 값 찾았을 때
return i
}
if let j = index(of: element, startingAt: leftChildIndex(ofParentAt: i)) {
// 왼쪽으로 재귀호출 이진 트리 탐색이랑 원리가 같음.
return j
}
if let j = index(of: element, startingAt: rightChildIndex(ofParentAt: i)) {
// 오른쪽으로 재귀호출
return j
}
return nil
}Reference
자료구조, 완전 이진트리 정의 : 정보처리기사 필기 1
Heap 연산 출처 : 스위프트 힙 자료구조
자료구조 Heap : 스위프트 자료구조 힙
