• Priority Queue는 FIFO 순서를 사용하고 우선 순위에 따라 Queue에 들어 있는 것을 말합니다.
• Priority Queue의 종류
  1. Max - priority : 가장 앞의 Element가 가장 큽니다.
  2. Min - priority : 가장 앞의 Element가 가장 작습니다.
• Priority Queue는 최대 값 또는 최소 값을 식별 해야 할 때 유용 합니다.

Priority Queue 생성.

생성 하기 전에 어떤 방식을 사용하면 Priority Queue를 만들수 있을까?

1. 정렬 된 배열
   • O(1)의 시간 안에 요소의 최대 값 또는 최소 값을 가져오는데 유용합니다. 그러나 삽입을 진행 할 때 순서대로 해야 하므로 O(n)의 시간이 걸리게 되어 느립니다.
2. Balanced Binary Search Tree
   • 최소 값과 최대 값을 O(log n) 시간 만큼 걸려 가져오는 double-ended priority queue를 만들 수 있습니다. 삽입은 O(log n)이기 때문에 정렬 된 배열보다 낫습니다.
   • 왜 O(log n)?
     • Binary Search Tree는 BST 규칙을 준수해야 합니다.
     1. left child의 값은 parents의 값보다 작아야 합니다.
     2. right child의 값은 parents의 값도가 크거나 같아야 합니다.
     • 위의 2가지 조건이 만족하기 때문에 Search Tree는 다음과 같은 결과를 예상할 수 있습니다.
     1. 검색하고자 하는 값이 현재 값보다 작은 경우 left subTree에 있습니다.
     2. 검색하고자 하는 값이 현재 값보다 큰 경우 right subTree에 있습니다.
     • 그렇기 때문에 삽입은 BST 규칙에 의해 모든 Element를 확인 할 필요가 없어서 O(log n)입니다.
3. Heap
   • Heap은 부분만 정렬하면 정렬에 있어서 되므로 정렬 된 배열보다 더 효율적입니다. min priority heap에서 최소 값을 가져오는 것은 O(1)이며, 그 외의 힙 작업은 O(log n)입니다. 마찬가지로 Max priority heap에서 최대 값을 가져오는 것도 O(1)입니다.

그래서 Heap을 사용해서 Priority Queue를 생성해야 합니다.

• 여기서 Heap과 메모리에서 Heap은 다릅니다.

// Queue Create
public protocol Queue {
  associatedtype Element
  mutating func enqueue(_ element: Element) -> Bool
  mutating func dequeue() -> Element?
  var isEmpty: Bool { get }
  var peek: Element? { get }
}

// Heap Create
public struct Heap<Element: Equatable> {
  
  var elements: [Element] = []
  let sort: (Element, Element) -> Bool
  
  public init(sort: @escaping (Element, Element) -> Bool, elements: [Element] = []) {
    self.sort = sort
    self.elements = elements
    
    if !elements.isEmpty {
      for i in stride(from: elements.count / 2 - 1, through: 0, by: -1) {
        siftDown(from: i)
      }
    }
  }
  
  public var isEmpty: Bool {
    elements.isEmpty
  }
  
  public var count: Int {
    elements.count
  }
  
  public func peek() -> Element? {
    elements.first
  }
  
  func leftChildIndex(ofParentAt index: Int) -> Int {
    (2 * index) + 1
  }
  
  func rightChildIndex(ofParentAt index: Int) -> Int {
    (2 * index) + 2
  }
  
  func parentIndex(ofChildAt index: Int) -> Int {
    (index - 1) / 2
  }
  
  public mutating func remove() -> Element? {
    guard !isEmpty else {
      return nil
    }
    elements.swapAt(0, count - 1)
    defer {
      siftDown(from: 0)
    }
    return elements.removeLast()
  }
  
  mutating func siftDown(from index: Int) {
    var parent = index
    while true {
      let left = leftChildIndex(ofParentAt: parent)
      let right = rightChildIndex(ofParentAt: parent)
      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
      }
      elements.swapAt(parent, candidate)
      parent = candidate
    }
  }
  
  public mutating func insert(_ element: Element) {
    elements.append(element)
    siftUp(from: elements.count - 1)
  }
  
  mutating func siftUp(from index: Int) {
    var child = index
    var parent = parentIndex(ofChildAt: child)
    while child > 0 && sort(elements[child], elements[parent]) {
      elements.swapAt(child, parent)
      child = parent
      parent = parentIndex(ofChildAt: child)
    }
  }
  
  mutating func remove(at index: Int) -> Element? {
    guard index < elements.count else {
      return nil
    }
    if index == elements.count - 1 {
      return elements.removeLast()
    } else {
      elements.swapAt(index, elements.count - 1)
      defer {
        siftDown(from: index)
        siftUp(from: index)
      }
      return elements.removeLast()
    }
  }
  
  func index(of element: Element, startingAt i: Int) -> Int? {
    if i >= count {
      return nil
    }
    if sort(element, elements[i]) {
      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
  }
}

struct PriorityQueue<Element: Equatable>: Queue { // 1

	private var heap: Heap<Element> // 2

	
	init(sort: @escaping (Element, Element) -> Bool, elements: [Element] = []) { // 3
		heap = Heap(sort: sort, elements: elements)
	}

	var isEmpty: Bool {
		heap.isEmpty
	}
	
	var peek: Element? {
		heap.peek()
	}
	
	mutating func enqueue(_ element: Element) -> Bool { // 4
		heap.insert(element)
		return true
	}
	
	mutating func dequeue() -> Element? { // 5
		heap.remove()
	}
}

1. PriorityQueue는 Queue Protocol을 준수합니다. Element는 비교가 가능해야 하므로 Equatable을 준수해야 합니다.
2. 이 Heap을 사용해서 priority queue를 구현합니다.
3. 이 initializer에 적절한 function을 전달해서 PriorityQueue를 사용하여 최소 및 최대 priority queue를 모두 작성 할 수 있습니다.
4. enqueue(:)를 호출하면 Heap에 삽입 되면서 vaildate itself(유효성 검사)를 하기 위해 sift up을 합니다. enqueue(:)의 전체 복잡도는 O(log n)입니다.
5. dequeue(_:)를 호출하면 Heap의 root element를 heap의 마지막 요소와 바꾸고 heap에서 제거하고 sift down을 합니다. dequeue의 전체적인 복잡성은 O(log n)입니다.

Priority Queue 테스트.