⭐ Swift Heap 구현

//
//  main.swift
//  BOJPractice
//
//  Created by 바견규 on 9/15/25.
//

import Foundation

//maxHeap + minHeap

struct Heap<T: Comparable> { // Comparable: <, >, == 같은 비교 연산이 가능하다는 의미.
    private var elements: [T]
    private let compare: (T, T) -> Bool
    
    init(comparator: @escaping (T, T) -> Bool, elements: [T] = [] ){ // @escaping: 함수 범위를 벗어나서 클로저를 사용할 수 있도록 저장/지연 실행할 수 있도록 하는 것
        self.compare = comparator
        self.elements = elements
    }
    
    var isEmpty: Bool {
        return elements.isEmpty
    }
    
    var peek: T? {
        return elements.first
    }
    
    mutating func insert(_ element: T){
        elements.append(element)
        siftUp(from: elements.count - 1)
    }
    
    mutating func remove() -> T?{
        guard !elements.isEmpty else { return nil }
        if elements.count == 1 {
            return elements.removeLast()
        } else {
            let value = elements[0]
            elements[0] = elements[elements.count - 1]
            elements.removeLast()
            siftDown(from: 0)
            return value
        }
    }
    
    mutating private func siftUp(from index: Int){
        var childIndex = index
        let child = elements[index]
        var parentIndex = (childIndex - 1) / 2
        
        while childIndex > 0  && compare(child, elements[parentIndex]){
            elements[childIndex] = elements[parentIndex]
            
            childIndex = parentIndex
            parentIndex = (childIndex - 1) / 2
        }
        
        elements[childIndex] = child
    }
    
    mutating func siftDown(from index: Int) {
            var parentIndex = index
            let count = elements.count
            
            while true {
                let leftChildIndex = parentIndex*2 + 1
                let rightChildIndex = parentIndex*2 + 2
                var swapIndex:Int? = nil
                
                if leftChildIndex < count && compare(elements[leftChildIndex], elements[parentIndex]) {
                    swapIndex = leftChildIndex
                }
                
                if rightChildIndex < count && compare(elements[rightChildIndex], elements[swapIndex ?? parentIndex]) {
                    swapIndex = rightChildIndex
                }
                
                guard let swap = swapIndex else {return}
                
                elements.swapAt(swap, parentIndex)
                parentIndex = swap
            }
        
        }
}

🧩 핵심 1: 배열로 트리 표현 - 인덱스 정리

구조

          [0]
         /   \
       [1]   [2]
       / \   / \
     [3][4] [5][6]

공식

// 부모 인덱스
let parentIndex = (childIndex - 1) / 2

// 자식 인덱스
let leftChildIndex = parentIndex * 2 + 1
let rightChildIndex = parentIndex * 2 + 2

검증

노드	왼쪽 자식	오른쪽 자식	부모
0	0×2+1=1	0×2+2=2	-
1	1×2+1=3	1×2+2=4	(1-1)/2=0
2	2×2+1=5	2×2+2=6	(2-1)/2=0
3	3×2+1=7	3×2+2=8	(3-1)/2=1

경계 조건

// siftUp: 루트에서 멈춤
while childIndex > 0 { ... }

// siftDown: 자식이 범위 안에 있는지 확인
if leftChildIndex < count { ... }
if rightChildIndex < count { ... }

사용 예시

// siftUp - 아래에서 위로
var childIndex = index
var parentIndex = (childIndex - 1) / 2

// siftDown - 위에서 아래로
var parentIndex = index
let leftChildIndex = parentIndex * 2 + 1
let rightChildIndex = parentIndex * 2 + 2

🧩 핵심 2: Heap 구현 시 insert, remove 방법

insert (삽입)

1. 배열 맨 끝에 추가
2. siftUp으로 위로 올림

mutating func insert(_ element: T) {
    elements.append(element)      // 맨 끝에 추가
    siftUp(from: elements.count - 1)  // 위로 올림
}

최소힙에 2 삽입:

      5              5              2
     / \    추가    / \   siftUp   / \
    7   8   →     7   8    →     7   8
                 /              /
                2              5

remove (삭제)

1. 루트(첫 번째)를 반환값으로 저장
2. 마지막 원소를 루트로 이동
3. 마지막 원소 제거
4. siftDown으로 아래로 내림

mutating func remove() -> T? {
    guard !elements.isEmpty else { return nil }
    if elements.count == 1 {
        return elements.removeLast()
    } else {
        let value = elements[0]               // 루트 저장
        elements[0] = elements.removeLast()   // 마지막 → 루트
        siftDown(from: 0)                     // 아래로 내림
        return value
    }
}

최소힙에서 루트(2) 삭제:

      2              8              5
     / \   마지막   / \   siftDown  / \
    5   7  루트로  5   7     →     8   7
   /
  8

siftUp (위로 올림)

mutating func siftUp(from index: Int) {
    var childIndex = index
    let child = elements[childIndex]
    var parentIndex = (childIndex - 1) / 2
    
    while childIndex > 0 && compare(child, elements[parentIndex]) {
        elements[childIndex] = elements[parentIndex]
        childIndex = parentIndex
        parentIndex = (childIndex - 1) / 2
    }
    elements[childIndex] = child
}

siftDown (아래로 내림)

mutating func siftDown(from index: Int) {
    var parentIndex = index
    let count = elements.count
    
    while true {
        let leftChildIndex = parentIndex * 2 + 1
        let rightChildIndex = parentIndex * 2 + 2
        var swapIndex: Int? = nil
        
        // 왼쪽 자식과 비교
        if leftChildIndex < count && compare(elements[leftChildIndex], elements[parentIndex]) {
            swapIndex = leftChildIndex
        }
        
        // 오른쪽 자식과 비교 (swapIndex ?? parentIndex와 비교)
        if rightChildIndex < count && compare(elements[rightChildIndex], elements[swapIndex ?? parentIndex]) {
            swapIndex = rightChildIndex
        }
        
        guard let swap = swapIndex else { return }
        
        elements.swapAt(swap, parentIndex)
        parentIndex = swap
    }
}

시간복잡도

연산	시간복잡도
insert	O(log n)
remove	O(log n)
peek	O(1)

⭐ BOJ 7662

//
//  main.swift
//  BOJPractice
//
//  Created by 바견규 on 9/15/25.
//

import Foundation

//maxHeap + minHeap

struct Heap<T: Comparable> { // Comparable: <, >, == 같은 비교 연산이 가능하다는 의미.
    private var elements: [T]
    private let compare: (T, T) -> Bool
    
    init(comparator: @escaping (T, T) -> Bool, elements: [T] = [] ){ // @escaping: 함수 범위를 벗어나서 클로저를 사용할 수 있도록 저장/지연 실행할 수 있도록 하는 것
        self.compare = comparator
        self.elements = elements
    }
    
    var isEmpty: Bool {
        return elements.isEmpty
    }
    
    var peek: T? {
        return elements.first
    }
    
    mutating func insert(_ element: T){
        elements.append(element)
        siftUp(from: elements.count - 1)
    }
    
    mutating func remove() -> T?{
        guard !elements.isEmpty else { return nil }
        if elements.count == 1 {
            return elements.removeLast()
        } else {
            let value = elements[0]
            elements[0] = elements[elements.count - 1]
            elements.removeLast()
            siftDown(from: 0)
            return value
        }
    }
    
    mutating private func siftUp(from index: Int){
        var childIndex = index
        let child = elements[index]
        var parentIndex = (childIndex - 1) / 2
        
        while childIndex > 0  && compare(child, elements[parentIndex]){
            elements[childIndex] = elements[parentIndex]
            
            childIndex = parentIndex
            parentIndex = (childIndex - 1) / 2
        }
        
        elements[childIndex] = child
    }
    
    mutating func siftDown(from index: Int) {
            var parentIndex = index
            let count = elements.count
            
            while true {
                let leftChildIndex = parentIndex*2 + 1
                let rightChildIndex = parentIndex*2 + 2
                var swapIndex:Int? = nil
                
                if leftChildIndex < count && compare(elements[leftChildIndex], elements[parentIndex]) {
                    swapIndex = leftChildIndex
                }
                
                if rightChildIndex < count && compare(elements[rightChildIndex], elements[swapIndex ?? parentIndex]) { // swapIndex가 nil이면 parent와 비교, nil이 아니라면 leftChild와 비교
                    swapIndex = rightChildIndex
                }
                
                guard let swap = swapIndex else {return}
                
                elements.swapAt(swap, parentIndex)
                parentIndex = swap
            }
        
        }
}

let T = Int(readLine()!)!

for _ in 1...T{
    let N = Int(readLine()!)!
    
    var maxHeap:Heap = Heap<Int>(comparator: >)
    var minHeap:Heap = Heap<Int>(comparator: <)
    var count:[Int:Int] = [:]
    var totalSize = 0
    
    for _ in 1...N{
        let input = readLine()!.split(separator: " ")
        let op = input[0]
        let num = Int(input[1])!

        if op == "I"{
            maxHeap.insert(num)
            minHeap.insert(num)
            count[num, default: 0] += 1
            totalSize += 1
        } else{
            if num == 1{
                while let top = maxHeap.remove() {
                    if count[top]! == 0{
                        continue
                    }else{
                        count[top]! -= 1
                        totalSize -= 1
                        break
                    }
                }
            }else{
                while let top = minHeap.remove() {
                    if count[top]! == 0{
                        continue
                    }else{
                        count[top]! -= 1
                        totalSize -= 1
                        break
                    }
                }
            }
        }
        
    }
    
    if totalSize == 0 {
        print("EMPTY")
    }else{
        var maxVal: Int?
        var minVal: Int?
        
        while let top = maxHeap.remove() {
            if count[top, default: 0] > 0 {
                maxVal = top
                break
            }
        }
        while let top = minHeap.remove() {
            if count[top, default: 0] > 0 {
                minVal = top
                break
            }
        }
        print(maxVal!, minVal!)
    }
    
}

🧩 문제 풀이 핵심

문제 핵심

최댓값, 최솟값 둘 다 빠르게 삭제해야 함

해결 아이디어: 두 개의 힙 + 지연 삭제

var maxHeap = Heap<Int>(comparator: >)  // 최대힙
var minHeap = Heap<Int>(comparator: <)  // 최소힙
var count: [Int: Int] = [:]  // 각 값의 유효 개수
var totalSize = 0            // 실제 유효한 원소 개수

왜 두 개의 힙?

자료구조	최댓값 삭제	최솟값 삭제
최대힙만	O(log n)	O(n) ❌
최소힙만	O(n) ❌	O(log n)
둘 다	O(log n) ✅	O(log n) ✅

지연 삭제 (Lazy Deletion)

양쪽 힙을 즉시 동기화하지 않고, Dictionary로 유효성만 추적

I 5, I 3, I 7  →  count = [5:1, 3:1, 7:1]
                  maxHeap = [7, 5, 3]
                  minHeap = [3, 5, 7]

D 1 (최댓값 삭제) → maxHeap에서 7 꺼냄
                   count[7] = 0 (무효 처리)
                   minHeap에는 7이 아직 있음!

나중에 minHeap에서 꺼낼 때:
→ 7 나옴 → count[7] == 0 → 무효니까 버림
→ 3 나옴 → count[3] == 1 → 유효! 사용

삭제 로직

while let top = maxHeap.remove() {
    if count[top]! == 0 {
        continue  // 이미 삭제된 값 → 건너뜀
    } else {
        count[top]! -= 1
        totalSize -= 1
        break     // 유효한 값 찾음 → 종료
    }
}

시간복잡도

연산	단순 배열	이중 힙 + 지연 삭제
삽입	O(1)	O(log n)
최댓값 삭제	O(n)	O(log n)
최솟값 삭제	O(n)	O(log n)
전체	O(n × k)	O(n log n) ✅

처음에는 배열을 이용하여 삭제 시마다 정렬하여 풀려고 했으니 시간 복잡도때문에 시간 초과가 계속 났다.

연산	시간복잡도
sort()	O(n log n)
삭제 연산 k번	O(k × n log n)
전체	O(k × n log n) ❌