티스토리 뷰
Swift같은 개발 언어 중에는 힙, 큐, 덱같이 기본적으로 다른 언어에서 제공해주는 라이브러리가 따로 있지 않다. 따라서 직접 구현해줘야 한다.
알아야 될 것
1. 완전 이진트리로 부모 노드를 탐색하려면, 시작 인덱스를 1부터 시작해야 한다.
2. 힙은 우선순위 큐를 위한 자료형이다.
3. 우선순위 큐의 목적은 값을 추가할 때 부모 노드에 최댓값 or 최솟값을 넣기 위함이다.
4. 따라서 입, 출력을 할 때만 연산이 수행되고, 전체 힙의 값을 확인하면 오름차순이나 내림차순으로 정렬되지 않을 수 있다.
struct Heap {
var heap: Array<Int> = []
// 초기화 1. 아무 것도 넣지 않을 때
init() { }
// 초기화 2. 시작부터 넣을 때
init(_ data: [Int]) {
heap.append(0)
heap += data
}
// 더하기, 해당 값이 최대일 때 idx 1에 도달, 아닐 때는 중간에 멈춤
mutating func add(_ i: Int) {
heap.append(i)
var idx = heap.count - 1
while idx > 1 && heap[idx] > heap[idx/2] {
heap.swapAt(idx, idx/2)
idx /= 2
}
}
// 빼기, 최댓값을 마지막값과 swap후 삭제 + idx 1 요소만 정렬
mutating func delete() {
if heap.count <= 1 {
print(0) // 힙이 비어 있으면 0을 로그에 출력(선택 사항)
return
}
heap.swapAt(1, heap.count - 1)
print(heap.removeLast()) // 삭제 값 출력(선택 사항)
sort(1)
}
// 정렬
mutating func sort(_ i: Int) {
var root = i
let left = i * 2
let right = i * 2 + 1
// 완전 이진 트리이므로, 자식 노드의 왼쪽부터 판단
if left < heap.count && heap[left] > heap[root] {
root = left
}
// 오른쪽 자식 노드가 있으면 왼쪽 노드와 비교
if right < heap.count && heap[right] > heap[root] && heap[right] > heap[left] {
root = right
}
// 바꿀 경우가 없을 때(이미 최대일 때)를 제외하고는 재귀로 해당 함수 반복
if i != root {
heap.swapAt(i, root)
sort(root)
}
}
}
'Data Structures and Algorithms' 카테고리의 다른 글
[Algorithm] Divide and conquer - Maximum Subarray (0) | 2024.04.03 |
---|---|
[Algorithm] Divide and Conquer - Merge sort (1) | 2024.04.03 |
[Algorithm] Analysis - time complexity, big & small notations (0) | 2024.04.01 |
[Algorithm] Basics 2 (0) | 2024.03.13 |
[Algorithm] Basics 1 (0) | 2024.03.07 |
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- CSS
- 백준
- SVG
- DP
- HTML
- Array
- 곱셈의 역원
- how to remove border of tabbarcontroller
- 파이썬
- TIP
- pyrebase
- how to start without storyboard
- SceneDelegate
- DFS
- Javascript
- BOJ
- xcode
- swift
- PS
- 정보시각화
- D3
- ios
- 알고리즘
- 하노이탑이동순서
- 백트래킹
- Python
- 보라매사옥
- c++
- 자료구조
- CSV
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
글 보관함