Priority Queue

[qwerty3345]

10/4 link

[stealmh]

우선순위 큐

pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐

연습문제

1927 최소힙

코드

```swift class PriorityQueue { private var heap: [Int] = [0] private var heapCount: Int = 0 private var idx: Int = 0 func push(_ value: Int) { heap.append(value) heapCount += 1 idx = heapCount while idx != 1 { let parent = idx / 2 if heap[parent] <= heap[idx] { break } heap.swapAt(parent, idx) idx = parent } } func pop() -> Int { var removeMinValue = 999 if heapCount == 0 { return 0 } removeMinValue = heap[1] heap[1] = heap[heapCount] heap.remove(at: heapCount) heapCount -= 1 var idx = 1 while 2 * idx <= heapCount { let left = 2 * idx let right = 2 * idx + 1 var min = left if right <= heapCount && heap[right] < heap[left] { min = right } if heap[idx] <= heap[min] { break } heap.swapAt(idx, min) idx = min } return removeMinValue } } let n = Int(readLine()!)! var priv = PriorityQueue() for _ in 0..

11286 절대값 힙

코드

```swift class MinPriv { var heap: [Int] = [0] var heapCount: Int = 0 var idx = 0 func push(_ value: Int) { heap.append(value) heapCount += 1 idx = heapCount while idx != 1 { let parent = idx / 2 if heap[parent] <= heap[idx] { break } heap.swapAt(parent, idx) idx = parent } } func pop() -> Int { var removeValue = 0 removeValue = heap[1] heap[1] = heap[heapCount] heap.remove(at: heapCount) heapCount -= 1 var idx = 1 while 2 * idx <= heapCount { var left = 2 * idx var right = 2 * idx + 1 var min = left if right <= heapCount && heap[right] < heap[left] { min = right } if heap[idx] <= heap[min] { break } heap.swapAt(idx, min) idx = min } return removeValue } } class MaxPriv { var heap: [Int] = [0] var heapCount: Int = 0 var idx = 0 func push(_ value: Int) { heap.append(value) heapCount += 1 idx = heapCount while idx != 1 { let parent = idx / 2 if heap[parent] >= heap[idx] { break } heap.swapAt(parent, idx) idx = parent } } func pop() -> Int { var removevalue = 0 removevalue = heap[1] heap[1] = heap[heapCount] heap.remove(at: heapCount) heapCount -= 1 var idx = 1 while 2 * idx <= heapCount { var left = 2 * idx var right = 2 * idx + 1 var max = left if right <= heapCount && heap[right] > heap[left] { max = right } if heap[idx] >= heap[max] { break } heap.swapAt(idx, max) idx = max } return removevalue } } var minPriv = MinPriv() var maxPriv = MaxPriv() let n = Int(readLine()!)! for _ in 0.. 0: minPriv.push(x) /// 0일 때 default: if maxPriv.heapCount == 0 && minPriv.heapCount == 0 { print(0) } else if maxPriv.heapCount == 0 && minPriv.heapCount != 0 { print(minPriv.pop()) } else if maxPriv.heapCount != 0 && minPriv.heapCount == 0 { print(maxPriv.pop()) } else { if abs(maxPriv.heap[1]) <= abs(minPriv.heap[1]) { print(maxPriv.pop()) } else { print(minPriv.pop()) } } } } ```

[MUKER-WON]

우선순위 큐 (Priority Queue)

• 일반적인 큐는 선입선출 방식으로 작동하지만, 우선순위 큐는 머저 들어온 순서가 아니라 우선순위가 높은 요소가 먼저 처리된다.
• 만약 여러 요소가 같은 우선순위를 가진다면, 그 중에서는 일반적인 큐처럼 선입선출 방식이 적용된다.
• 보통 Heap 자료구조로 구현된다. 특히 Max Heap 이나 Min Heap을 사용해 우선순위가 높은 요소나 낮은 요소를 빠르게 접근할 수 있다.

사용 사례

• 운영 체제의 작업 스케줄링
• 네트워크 트래픽 제어
• 다익스트라 알고리즘 등의 그래프 알고리즘

시간 복잡도 (힙 구현 기준)

• 삽입: O(log n)
• 삭제: O(log n)
• 최대/최소 요소 조회: O(1)
• 힙 정렬: O(log n)

힙 (Heap)

• 불균형이 발생하지 않고 늘 균형이 잘 맞는 이진 트리
• 최소 힙 (Min Heap)
  • 부모가 자식보다 작아야 함 (root값이 최소값)
• 최대 힙 (Max Heap)
  • 부모가 자식보다 커야 함 (root값이 최대값)

힙 구현

• 힙은 1차원 배열에 표현이 가능하다. 앞서 배운 이진 탐색 트리는 1차원 배열로 나타내기엔 특성상 균형이 맞지 않아 많은 부분이 비효율적인 메모리 사용을 하게 되고 노드의 삽입 삭제가 빈번하여 연결 리스트 형태의 노드 구조를 사용하는게 더 올바르다.

struct Heap<T: Comparable> {
    /// 힙의 요소를 저장하는 배열
    var elements = [T]()
    /// 최대힙, 최소힙을 결정 짓는, 힙의 정렬 기준을 결정하는 클로저
    private let sort: (T, T) -> Bool

    var count: Int { return elements.count }
    var peek: T? { return elements.first }

    init(
        elements: [T] = [T](),
        sort: @escaping (T, T) -> Bool
    ) {
        self.elements = elements
        self.sort = sort

        // 초기 요소가 있다면 힙으로 변환
        if !elements.isEmpty {
            for i in stride(from: elements.count / 2 - 1, through: 0, by: -1) {
                siftDown(index: i)
            }
        }
    }
    /// 새 요소를 힙에 추가
    mutating func push(_ element: T) {
        elements.append(element)
        siftUp(index: count - 1)
    }
    /// 최상위 요소를 pop 하고 반환
    mutating func pop() -> T? {
        guard !elements.isEmpty else { return nil }
        elements.swapAt(0, count - 1)

        let element = elements.removeLast()
        siftDown(index: 0)
        return element
    }
    /// 요소를 위로 이동시켜 힙 속성 유지
    private mutating func siftUp(index: Int) {
        var child = index
        var parent = parentIndex(child)

        while child > 0 && sort(elements[child], elements[parent]) {
            elements.swapAt(child, parent)
            child = parent
            parent = parentIndex(child)
        }
    }
    /// 요소를 아래로 이동시켜 힙 속성 유지
    private mutating func siftDown(index: Int) {
        var parent = index

        while true {
            let leftChild = leftChildIndex(parent)
            let rightChild = rightChildIndex(parent)
            var candidate = parent

            if leftChild < count &&
                sort(elements[leftChild], elements[candidate]) {
                candidate = leftChild
            }
            if rightChild < count &&
                sort(elements[rightChild], elements[candidate]) {
                candidate = rightChild
            }
            if candidate == parent { return }

            elements.swapAt(parent, candidate)
            parent = candidate
        }
    }

    private func parentIndex(_ index: Int) -> Int {
        return (index - 1) / 2
    }

    private func leftChildIndex(_ index: Int) -> Int {
        return index * 2 + 1
    }

    private func rightChildIndex(_ index: Int) -> Int {
        return index * 2 + 2
    }

}

var minHeap = Heap<Int>(sort: <) // 최소힙으로 초기화
minHeap.push(27)
minHeap.push(8)
minHeap.push(20)
minHeap.push(16)
minHeap.push(14)
minHeap.push(21)
minHeap.push(12)

print(minHeap.elements) // [8, 14, 12, 27, 16, 21, 20]
print(minHeap.pop()) // pop 8
print(minHeap.elements) // [12, 14, 20, 27, 16, 21]

문제 풀이

백준 절대값 힙

import Foundation

struct Heap {
    /// 0: 절대값, 1: 원래값
    var elements = [(Int, Int)]()

    mutating func push(_ element: (Int, Int)) {
        elements.append(element)
        var index = elements.count - 1

        while index > 0,
              compare(elements[index], elements[(index - 1) / 2]) {
            elements.swapAt(index, (index - 1) / 2)
            index = (index - 1) / 2
        }
    }

    mutating func pop() -> (Int, Int)? {
        guard !elements.isEmpty else { return nil }

        elements.swapAt(0, elements.count - 1)
        let result = elements.removeLast()
        var index = 0

        while index * 2 + 1 < elements.count {
            var child = index * 2 + 1

            if child + 1 < elements.count,
               compare(elements[child + 1], elements[child]) {
                child += 1
            }

            if compare(elements[index], elements[child]) { break }
            elements.swapAt(index, child)
            index = child
        }

        return result
    }

    private func compare(
        _ a: (Int, Int),
        _ b: (Int, Int)
    ) -> Bool {
        return a.0 == b.0 ? a.1 < b.1 : a.0 < b.0
    }
}

var heap = Heap()

for _ in 0..<Int(readLine()!)! {
    let n = Int(readLine()!)!
    if n == 0 {
        if let result = heap.pop() {
            print(result.1)
        } else {
            print(0)
        }
    } else {
        heap.push((abs(n), n))
    }
}

[qwerty3345]

BOJ 11286 - 절댓값 힙

let N = Int(readLine()!)!
var heap = Heap<Int>(elements: [], priorityFunction: {
    if abs($0) == abs($1) {
        return $0 < $1
    }
    return abs($0) < abs($1)
})
var numbers: [Int] = []
for _ in 0..<N {
    let input = Int(readLine()!)!
    if input == 0 {
        print(heap.dequeue() ?? 0)
    } else {
        heap.enqueue(input)
    }
}

/// Heap 구조체 정의
public struct Heap<Element> {
    /// 힙의 요소들을 저장하는 배열
    public private(set) var elements: [Element]

    /// 우선순위를 결정하는 함수
    /// 이 함수는 두 요소를 비교하여 첫 번째 요소가 더 높은 우선순위를 가지면 true를 반환합니다.
    public let priorityFunction: (Element, Element) -> Bool

    public var isEmpty: Bool { elements.isEmpty }
    public var count: Int { elements.count }

    /// 생성자: 초기 요소 배열과 우선순위 함수를 받아 힙을 생성합니다.
    public init(elements: [Element], priorityFunction: @escaping (Element, Element) -> Bool) {
        self.elements = elements
        self.priorityFunction = priorityFunction
        /// 힙 속성을 만족하도록 재구성합니다.
        /// 마지막 비-리프 노드부터 시작하여 루트까지 각 노드에 대해 siftDown을 수행합니다.
        /// 이는 O(n) 시간 복잡도로 전체 힙을 구성하는 효율적인 방법입니다.
        for index in (0..<(count / 2)).reversed() {
            siftDown(at: index)
        }
    }

    /// 새로운 요소를 힙에 추가하는 함수
    public mutating func enqueue(_ element: Element) {
        elements.append(element)
        siftUp(at: count - 1)
    }

    /// 최상위 요소를 제거하고 반환하는 함수
    public mutating func dequeue() -> Element? {
        guard isEmpty == false else { return nil }
        /// 루트 요소와 마지막 요소를 교환합니다.
        elements.swapAt(0, count - 1)
        /// 마지막 요소(원래의 루트)를 제거하고 저장합니다.
        let element = elements.removeLast()
        /// 힙이 비어있지 않다면, 새 루트 요소에 대해 siftDown을 수행하여 힙 속성을 유지합니다.
        if isEmpty == false {
            siftDown(at: 0)
        }
        return element
    }

    /// 요소를 위로 이동시키는 함수 (힙 속성을 유지하기 위해)
    /// 새로 추가된 요소를 부모 노드와 비교하며 필요한 경우 위치를 교환합니다.
    /// 이 과정은 요소가 올바른 위치에 도달하거나 루트에 도달할 때까지 계속됩니다.
    mutating func siftUp(at index: Int) {
        let parent = parentIndex(of: index)
        guard index != 0, isHigherPriority(at: index, than: parent) else { return }

        elements.swapAt(index, parent)
        siftUp(at: parent)
    }

    /// 요소를 아래로 이동시키는 함수 (힙 속성을 유지하기 위해)
    /// 현재 노드를 자식 노드들과 비교하여 필요한 경우 위치를 교환합니다.
    /// 이 과정은 요소가 올바른 위치에 도달하거나 리프 노드에 도달할 때까지 계속됩니다.
    mutating func siftDown(at index: Int) {
        let childIndex = highestPriorityIndex(for: index)
        guard index != childIndex else { return }
        elements.swapAt(index, childIndex)
        siftDown(at: childIndex)
    }
}

// MARK: - Private Methods

private extension Heap {
    /// 힙의 최상위 요소를 반환하는 함수 (제거하지 않고 조회만 함)
    func peek() -> Element? {
        elements.first
    }

    /// 주어진 인덱스의 왼쪽 자식 노드 인덱스를 계산하는 함수
    func leftChildIndex(of index: Int) -> Int {
        (index * 2) + 1
    }

    /// 주어진 인덱스의 오른쪽 자식 노드 인덱스를 계산하는 함수
    func rightChildIndex(of index: Int) -> Int {
        (index * 2) + 2
    }

    /// 주어진 인덱스의 부모 노드 인덱스를 계산하는 함수
    func parentIndex(of index: Int) -> Int {
        (index - 1) / 2
    }

    /// 두 인덱스의 요소 중 우선순위가 더 높은지 비교하는 함수
    func isHigherPriority(at firstIndex: Int, than secondIndex: Int) -> Bool {
        priorityFunction(elements[firstIndex], elements[secondIndex])
    }

    /// 부모 인덱스와 자식 인덱스 중 우선순위가 더 높은 인덱스를 반환하는 함수
    func highestPriorityIndex(parent: Int, child: Int) -> Int {
        guard child < count,
              isHigherPriority(at: child, than: parent) else {
            return parent
        }
        return child
    }

    /// 부모와 그 자식들 중 가장 우선순위가 높은 인덱스를 반환하는 함수
    /// 이 함수는 재귀적으로 호출되어 부모와 왼쪽 자식을 먼저 비교한 후,
    /// 그 결과와 오른쪽 자식을 비교합니다.
    func highestPriorityIndex(for parent: Int) -> Int {
        let leftChild = leftChildIndex(of: parent)
        let rightChild = rightChildIndex(of: parent)

        var highestPriority = highestPriorityIndex(parent: parent, child: leftChild)
        highestPriority = highestPriorityIndex(parent: highestPriority, child: rightChild)
        return highestPriority
    }
}

[shippingpark]

우선순위 큐 (Priority Queue)

• 일반적인 큐는 먼저 들어온 순서대로 처리되지만, 우선순위 큐는 순서가 아닌 우선순위에 따라 먼저 처리된다.
• 만약 여러 항목이 같은 우선순위를 가지고 있다면, 먼저 들어온 항목이 먼저 처리된다.
• 주로 Heap 자료구조를 사용하며, Max Heap이나 Min Heap을 이용해 높은 우선순위의 항목을 빠르게 찾고 처리할 수 있다.

사용 예시

• 운영 체제의 작업 스케줄
• 네트워크 트래픽 관리
• 그래프 알고리즘 (예: 다익스트라 알고리즘)

시간 복잡도 (Heap 기준)

• 삽입: O(log n)
• 삭제: O(log n)
• 최댓값/최솟값 조회: O(1)

힙 (Heap)

• 균형이 잘 유지되는 이진 트리 형태로, 항상 효율적으로 작동한다.
• 최소 힙(Min Heap): 부모 노드의 값이 자식 노드의 값보다 작다. (루트가 가장 작은 값)
• 최대 힙(Max Heap): 부모 노드의 값이 자식 노드보다 크다. (루트가 가장 큰 값)

Heap 구현

• Heap은 배열로 표현할 수 있으며, 균형을 유지하기 때문에 이진 탐색 트리보다 메모리를 효율적으로 사용할 수 있다.
• 삽입과 삭제가 자주 일어날 경우 연결 리스트보다 배열 기반의 Heap이 더 적합하다.

[stealmh]

11286 절대값 힙

/// 최소가 우선순위가 더 높은 큐
class PriorityQueue_MIN {
    private var heap: [Int] = [0]
    private var heapCount: Int = 0

    var isEmpty: Bool { heapCount == 0 }
    var top: Int? { heapCount > 0 ? heap[1] : nil }

    func push(_ value: Int) {
        heap.append(value)
        heapCount += 1
        var idx: Int = heapCount

        while idx != 1 {
            let parent: Int = idx / 2
            if heap[parent] <= heap[idx] { break }
            heap.swapAt(parent, idx)
            idx = parent
        }
    }

    func pop() -> Int {
        var removeMinValue: Int = 0
        removeMinValue = heap[1]

        heap[1] = heap[heapCount]
        heap.remove(at: heapCount)
        heapCount -= 1

        var idx: Int = 1
        while 2 * idx <= heapCount {
            let left: Int = 2 * idx
            let right: Int = 2 * idx + 1
            var minValue: Int = left

            if right <= heapCount && heap[right] < heap[left] {
                minValue = right
            }

            if heap[idx] <= heap[minValue] { break }
            heap.swapAt(idx, minValue)
            idx = minValue
        }

        return removeMinValue
    }
}
/// 최대가 우선순위가 더 높은 큐
class PriorityQueue_MAX {
    private var heap: [Int] = [0]
    private var heapCount: Int = 0

    var isEmpty: Bool { heapCount == 0 }
    var top: Int? { heapCount > 0 ? heap[1] : nil }

    func push(_ value: Int) {
        heap.append(value)
        heapCount += 1
        var idx: Int = heapCount

        while idx != 1 {
            let parent: Int = idx / 2
            if heap[parent] >= heap[idx] { break }
            heap.swapAt(parent, idx)
            idx = parent
        }
    }

    func pop() -> Int {
        var removeMaxValue: Int = 0
        removeMaxValue = heap[1]

        heap[1] = heap[heapCount]
        heap.remove(at: heapCount)
        heapCount -= 1

        var idx: Int = 1

        while 2 * idx <= heapCount {
            let left: Int = 2 * idx
            let right: Int = 2 * idx + 1
            var maxValue: Int = left

            if right <= heapCount && heap[right] > heap[left] {
                maxValue = right
            }

            if heap[idx] >= heap[maxValue] { break }
            heap.swapAt(idx, maxValue)
            idx = maxValue
        }

        return removeMaxValue
    }
}

var minQueue: PriorityQueue_MIN = PriorityQueue_MIN()
var maxQueue: PriorityQueue_MAX = PriorityQueue_MAX()

let n = Int(readLine()!)!

for _ in 0..<n {
    let input = Int(readLine()!)!

    switch input {
    /// 음수일 때
    case let x where x < 0:
        maxQueue.push(x)
    /// 양수일 때
    case let x where x > 0:
        minQueue.push(x)
    /// 0일 때
    default:
        if minQueue.isEmpty && maxQueue.isEmpty {
            print(0)
            continue
        }

        if minQueue.isEmpty && !maxQueue.isEmpty {
            print(maxQueue.pop())
            continue
        }

        if !minQueue.isEmpty && maxQueue.isEmpty {
            print(minQueue.pop())
            continue
        }

        guard let min = minQueue.top,
              let max = maxQueue.top else { continue }

        abs(min) < abs(max)
        ? print(minQueue.pop())
        : print(maxQueue.pop())
    }
}