문제: 힙 - 이중우선순위큐
| 힙 문제 목록 링크 / 문제 링크 / Github 링크 (준비중) |
|---|
 |
import Foundation
func solution(_ operations:[String]) -> [Int] {
return []
}문제 접근 1
- 이중 우선순위 큐 구현 옵션
- 두 개의 힙 사용 (Min-Heap + Max-Heap) ✅
- Min-Max Heap 사용
- Balanced Binary Search Tree (균형 이진 탐색 트리)
- 명령어 데이터 입력 구현
- 큐가 비어있으면 [0, 0] 반환
- 큐가 비어있으면 삭제 연산 무시
- 최댓값/최솟값 연산의 대상이 둘 이상인 경우 하나만 삭제
import Foundation
func solution(_ operations: [String]) -> [Int] {
return []
}
struct Heap {
private var maxHeap: [Int] = []
private var minHeap: [Int] = []
mutating func insertToMaxHeap(_ value: Int) -> Int {
maxHeap.append(value)
var currentIndex = maxHeap.count - 1
while currentIndex > 0 {
let parentIndex = (currentIndex - 1) / 2
if maxHeap[currentIndex] > maxHeap[parentIndex] {
maxHeap.swapAt(currentIndex, parentIndex)
currentIndex = parentIndex
} else { break }
}
return currentIndex
}
mutating func insertToMinHeap(_ value: Int) -> Int {
minHeap.append(value)
var currentIndex = minHeap.count - 1
while currentIndex > 0 {
let parentIndex = (currentIndex - 1) / 2
if minHeap[currentIndex] < minHeap[parentIndex] {
minHeap.swapAt(currentIndex, parentIndex)
currentIndex = parentIndex
} else { break }
}
return currentIndex
}
mutating func extractMax() -> Int? {
guard !maxHeap.isEmpty else { return nil }
if maxHeap.count == 1 {
return maxHeap.removeFirst()
}
let maxValue = maxHeap[0]
maxHeap[0] = maxHeap.removeLast()
var currentIndex = 0
while currentIndex < maxHeap.count {
let leftChildIndex = currentIndex * 2 + 1
let rightChildIndex = currentIndex * 2 + 2
var largestIndex = currentIndex
if leftChildIndex < maxHeap.count && maxHeap[leftChildIndex] > maxHeap[largestIndex] {
largestIndex = leftChildIndex
}
if rightChildIndex < maxHeap.count && maxHeap[rightChildIndex] > maxHeap[largestIndex] {
largestIndex = rightChildIndex
}
if largestIndex == currentIndex { break }
maxHeap.swapAt(currentIndex, largestIndex)
currentIndex = largestIndex
}
return maxValue
}
mutating func extractMin() -> Int? {
guard !minHeap.isEmpty else { return nil }
if minHeap.count == 1 {
return minHeap.removeFirst()
}
let minValue = minHeap[0]
minHeap[0] = minHeap.removeLast()
var currentIndex = 0
while currentIndex < minHeap.count {
let leftChildIndex = currentIndex * 2 + 1
let rightChildIndex = currentIndex * 2 + 2
var smallestIndex = currentIndex
if leftChildIndex < minHeap.count && minHeap[leftChildIndex] < minHeap[smallestIndex] {
smallestIndex = leftChildIndex
}
if rightChildIndex < minHeap.count && minHeap[rightChildIndex] < minHeap[smallestIndex] {
smallestIndex = rightChildIndex
}
if smallestIndex == currentIndex { break }
minHeap.swapAt(currentIndex, smallestIndex)
currentIndex = smallestIndex
}
return minValue
}
}두 힙의 동기화
1. Lazy Deletion (지연 삭제)
2. Index Synchronization (인덱스 동기화)
Max Heap과 Min Heap을 각각 만들고나니, 두 힙 사이의 동기화를 이루는 게 무척 까다로워 보였다.
Lazy Deletion은 구현은 간단하지만 고려해야 할 예외 처리가 있고, Index Synchronization은 그 구현이 매우 복잡해보였다.
문제 접근 2
- 이중 우선순위 큐 구현 옵션
- 두 개의 힙 사용 (Min-Heap + Max-Heap) ❌
- Min-Max Heap 사용 ✅
- Balanced Binary Search Tree (균형 이진 탐색 트리)
- 명령어 데이터 입력 구현
- 큐가 비어있으면 [0, 0] 반환
- 큐가 비어있으면 삭제 연산 무시
- 최댓값/최솟값 연산의 대상이 둘 이상인 경우 하나만 삭제
※ 다음 글에서 계속
What I've learned:
힙(Heap) 자료구조
힙(Heap)은 완전 이진 트리(Complete Binary Tree) 형태로 이루어진 특수한 트리 기반 자료구조이다. 힙은 최대값 또는 최소값을 빠르게 찾아야 하는 상황에서 유용하며, 우선순위 큐(Priority Queue) 를 구현하는 데 주로 사용된다.
힙의 종류
-
최대 힙(Max Heap)
- 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같음.
- 루트 노드(root)는 힙에서 가장 큰 값을 가짐.
-
최소 힙(Min Heap)
- 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같음.
- 루트 노드(root)는 힙에서 가장 작은 값을 가짐.
힙의 특징
- 완전 이진 트리를 기반으로 하며, 마지막 레벨을 제외하면 모든 노드가 채워져 있어야 한다.
- 특정 노드의 부모와 자식 간의 대소 관계는 보장하지만, 왼쪽 자식과 오른쪽 자식 간의 대소 관계는 보장하지 않는다.
주요 연산
-
삽입(Insertion)
- 새로운 데이터를 마지막 노드에 삽입한 후, 힙의 속성을 유지하기 위해 부모 노드와 비교하여 자리를 바꾼다(상향식 조정, Heapify Up).
-
삭제(Deletion)
- 루트 노드(최대값 또는 최소값)를 제거한 후, 마지막 노드를 루트로 이동시킨다.
- 그런 다음 자식 노드와 비교하여 자리를 바꾼다(하향식 조정, Heapify Down).
-
조회(Access)
- 최대 힙에서는 루트 노드가 최대값.
- 최소 힙에서는 루트 노드가 최소값.
시간 복잡도
- 삽입, 삭제:
O(log n) (트리의 높이가 log n이기 때문) - 최댓값/최솟값 조회:
O(1) (루트 노드를 바로 확인)
힙의 활용
-
우선순위 큐(Priority Queue) 구현
- 우선순위가 높은 요소를 빠르게 삽입/삭제할 수 있음.
-
힙 정렬(Heap Sort)
- 힙을 이용하여 정렬을 수행할 수 있으며, 시간 복잡도는 O(n log n).
-
최대값 또는 최소값의 빠른 접근이 필요한 경우
- 예: 작업 스케줄링, 다익스트라 알고리즘(최단 경로 탐색) 등.
간단한 예시 (Swift)
Max Heap 구조체
struct MaxHeap {
private var heap: [Int] = []
mutating func insert(_ value: Int) {
heap.append(value)
var currentIndex = heap.count - 1
while currentIndex > 0 {
let parentIndex = (currentIndex - 1) / 2
if heap[currentIndex] > heap[parentIndex] {
heap.swapAt(currentIndex, parentIndex)
currentIndex = parentIndex
} else {
break
}
}
}
mutating func extractMax() -> Int? {
guard !heap.isEmpty else { return nil }
if heap.count == 1 {
return heap.removeFirst()
}
let maxValue = heap[0]
heap[0] = heap.removeLast()
var currentIndex = 0
while currentIndex < heap.count {
let leftChildIndex = currentIndex * 2 + 1
let rightChildIndex = currentIndex * 2 + 2
var largestIndex = currentIndex
if leftChildIndex < heap.count && heap[leftChildIndex] > heap[largestIndex] {
largestIndex = leftChildIndex
}
if rightChildIndex < heap.count && heap[rightChildIndex] > heap[largestIndex] {
largestIndex = rightChildIndex
}
if largestIndex == currentIndex { break }
heap.swapAt(currentIndex, largestIndex)
currentIndex = largestIndex
}
return maxValue
}
}이진 트리(Binary Tree)
이진 트리(Binary Tree) 는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조이다. 트리의 구조는 계층적(hierarchical)으로, 루트 노드에서 시작하여 각 자식 노드로 연결된다.
이진 트리의 기본 구성 요소
-
노드(Node)
- 데이터를 저장하는 기본 단위.
- 각 노드는 최대 두 개의 자식 노드를 가짐.
-
루트 노드(Root Node)
- 트리의 시작점에 위치한 노드.
-
자식 노드(Child Node)
- 부모 노드에 연결된 하위 노드.
- 왼쪽 자식 노드(Left Child)와 오른쪽 자식 노드(Right Child)로 구분.
-
부모 노드(Parent Node)
- 특정 노드에 연결된 상위 노드.
-
리프 노드(Leaf Node)
- 자식 노드가 없는 노드.
-
서브트리(Subtree)
- 특정 노드를 루트로 하는 부분 트리.
이진 트리의 종류
-
포화 이진 트리(Full Binary Tree)
- 모든 노드가 0개 또는 2개의 자식 노드를 가짐.
- 리프 노드가 아닌 모든 노드는 반드시 두 개의 자식 노드를 가짐.
1 / \ 2 3 / \ 4 5 -
완전 이진 트리(Complete Binary Tree)
- 모든 레벨이 가득 차 있어야 하지만, 마지막 레벨은 왼쪽부터 순서대로 채워짐.
- 마지막 레벨의 오른쪽 일부는 비어 있을 수 있음.
1 / \ 2 3 / \ / 4 5 6 -
정 이진 트리(Perfect Binary Tree)
- 모든 레벨이 꽉 차 있는 포화 상태의 이진 트리.
- 모든 리프 노드는 같은 깊이에 있고, 모든 내부 노드는 정확히 두 개의 자식 노드를 가짐.
1 / \ 2 3 / \ / \ 4 5 6 7 -
이진 탐색 트리(Binary Search Tree, BST)
- 왼쪽 서브트리의 모든 노드는 부모 노드보다 작고, 오른쪽 서브트리의 모든 노드는 부모 노드보다 큼.
- 이진 탐색이 효율적으로 가능.
8 / \ 3 10 / \ \ 1 6 14
차이점 요약
| 구분 | 포화 이진 트리 | 완전 이진 트리 | 정 이진 트리 | 이진 탐색 트리 |
|---|---|---|---|---|
| 정의 | 모든 노드가 0개 또는 2개의 자식 노드를 가짐 | 마지막 레벨을 제외한 모든 레벨이 꽉 차 있음, 마지막 레벨은 왼쪽부터 채움 | 모든 레벨이 꽉 차 있고 리프 노드가 동일 깊이 | 왼쪽 서브트리는 부모보다 작고, 오른쪽은 부모보다 큼 |
| 리프 노드 깊이 | 동일하지 않을 수 있음 | 동일하지 않을 수 있음 | 동일 | 동일하지 않을 수 있음 |
| 노드 배치 | 노드가 정확히 0개 또는 2개의 자식 | 마지막 레벨은 왼쪽부터 채움 | 모든 레벨이 가득 채워짐 | 값에 따라 배치 |
| 활용 사례 | 특정 구조 트리 설계에 활용 | 힙(Heap) 구현 | 완벽히 균형 잡힌 트리 필요 | 효율적인 데이터 검색과 삽입 |
이진 트리의 순회(Traversal)
트리 구조에서 데이터를 탐색하는 방법은 순회(Traversal) 방식을 따른다.
1
/ \
2 3
/ \
4 5-
전위 순회(Preorder Traversal)
- 순서: 루트 → 왼쪽 서브트리 → 오른쪽 서브트리
- 예시:
1 → 2 → 4 → 5 → 3
-
중위 순회(Inorder Traversal)
- 순서: 왼쪽 서브트리 → 루트 → 오른쪽 서브트리
- 예시:
4 → 2 → 5 → 1 → 3 - 이진 탐색 트리의 경우 오름차순 정렬된 결과를 얻음.
-
후위 순회(Postorder Traversal)
- 순서: 왼쪽 서브트리 → 오른쪽 서브트리 → 루트
- 예시:
4 → 5 → 2 → 3 → 1
-
레벨 순서 순회(Level Order Traversal)
- 순서: 루트 → 같은 레벨의 노드들을 왼쪽에서 오른쪽으로 순서대로 탐색
- 예시:
1 → 2 → 3 → 4 → 5
이진 트리의 주요 활용
-
이진 탐색 트리(BST)
- 탐색, 삽입, 삭제가 O(log n)의 시간 복잡도로 가능.
- 효율적인 데이터 검색 및 정렬에 사용.
-
힙(Heap)
- 우선순위 큐(Priority Queue) 구현에 사용.
-
허프만 코딩(Huffman Coding)
- 데이터 압축 알고리즘에서 최소 비용의 이진 트리 생성에 사용.
간단한 예시 (Swift)
이진 탐색 트리의 삽입과 탐색
class BinarySearchTree {
class Node {
var value: Int
var left: Node?
var right: Node?
init(_ value: Int) {
self.value = value
}
}
var root: Node?
func insert(_ value: Int) {
root = insert(from: root, value)
}
private func insert(from node: Node?, _ value: Int) -> Node {
guard let node = node else {
return Node(value)
}
if value < node.value {
node.left = insert(from: node.left, value)
} else {
node.right = insert(from: node.right, value)
}
return node
}
func search(_ value: Int) -> Bool {
return search(from: root, value)
}
private func search(from node: Node?, _ value: Int) -> Bool {
guard let node = node else {
return false
}
if value == node.value {
return true
} else if value < node.value {
return search(from: node.left, value)
} else {
return search(from: node.right, value)
}
}
}이진 트리는 효율적인 데이터 관리와 탐색에 필수적인 자료구조이다.
Min-Max Heap
Min-Max Heap의 주요 속성
- 짝수 레벨 (Min 레벨): 루트는 전체 최솟값
- 홀수 레벨 (Max 레벨): 루트의 자식들 중 하나가 전체 최댓값
- 완전 이진 트리: 모든 노드가 왼쪽부터 순서대로 채워짐
- 삽입과 삭제는
O(log n)시간 복잡도를 가짐
핵심 연산
1. 삽입 (Insert)
삽입 시 다음 규칙을 따라:
1. 새 노드를 맨 끝에 추가
2. 부모 노드와 비교하여 자신의 레벨(Min/Max)에 따라 위로 올라가며 정렬:
- 짝수 레벨에서는 부모와 비교하여 최솟값 유지
- 홀수 레벨에서는 부모와 비교하여 최댓값 유지
- 재귀적으로 상위 레벨로 이동하며 정렬 유지
2. 삭제 (Delete Min, Delete Max)
-
최솟값 삭제:
- 루트(최솟값)를 제거
- 마지막 노드를 루트로 이동
- Min-Heap 속성 유지:
- 자식 노드 중 더 작은 노드와 교환하며 내려감
- 교환 시 홀수 레벨이라면 Max-Heap 성질도 확인
-
최댓값 삭제:
- 루트의 자식 중 최댓값을 찾아 제거
- 마지막 노드를 해당 위치로 이동
- Max-Heap 속성 유지:
- 자식 노드 중 더 큰 노드와 교환하며 내려감
- 교환 시 짝수 레벨이라면 Min-Heap 성질도 확인
Balanced Binary Search Tree (균형 이진 탐색 트리)
- Balanced BST는 트리의 높이를 로그 범위로 제한하여 효율적인 데이터 탐색, 삽입, 삭제가 가능하도록 설계된 구조이다.
- 대표적인 구현으로 AVL Tree, Red-Black Tree, B-Trees가 있으며, 각각의 균형 조건과 회전/색상 변경을 통해 트리를 유지한다.
- 그러나 일반적인 BST는 데이터가 편향되면 최악의 경우 선형 구조(Linked List처럼)로 변할 수 있다. 이로 인해 탐색, 삽입, 삭제 연산의 시간 복잡도가 O(n)으로 저하된다.
- 데이터베이스 인덱스 (예: B-Tree, B+ Tree)
- 셋(Set)과 맵(Map) 구현 (예: Swift의
Set,Dictionary는 내부적으로 해시를 사용하지만 일부 언어에서는 Red-Black Tree 사용) - 우선순위 큐 또는 스케줄링 알고리즘
- 네트워크 라우팅 및 검색 엔진의 데이터 관리
Reciprocity lies in knowing enough