[Data Structure / Algorithms] Priority Queues

전성훈·2023년 11월 11일

Algorithms datastructure swift

Data Structure-Algorithm

목록 보기

19/35

주제: FIFO을 적용한 우선순위

우선순위 큐란

큐는 요소들의 순서를 먼저 들어온 순서대로(FIFO) 유지하는 리스트이다. 우선순위 큐는 FIFO 순서 대신 우선순위 순서로 요소가 제거되는 큐의 다른 버전이다.
리스트 요소들 중에서 최대 혹은 최소 값을 찾는 경우에는 우선순위 큐가 특히 유용하다.

응용 분야

최소 비용을 계산하기 위해 우선순위 큐를 사용하는 Dijkstra의 알고리즘
출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는 A* Pathfinding 알고리즘
우선순위 큐를 사용하여 구현할 수 있는 힙 정렬
압축 트리(compression tree)를 빌드하는 Huffman 코딩.
시뮬레이션이나 네트워크 트래픽 제어, 운영 체제의 작업 스케줄링, 수치 해석적인 계산 등에서 활용된다.

구현

Queue Protocol

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

Heap

Heap 참고

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

Priority Queue

struct PriortyQueue<Element: Equtable>: Queue { 
	private var heap: Heap<Element> 
	
	init(sort: @escaping (Element, Element) -> Bool, elements: [Element] = []) { 
		heap = Heap(sort: sort, elements: elements)
	}
	
	var isEmpty: Bool { 
		heap.isEmpty
	} 
	
	var peek: Element? { 
		heap.peek()
	} 
	
	mutating func enqueue(_ element: Element) -> Bool { 
		heap.insert(element)
		return ture
	}
	
	mutating func dequeue() -> Element? { 
		heap.remove() 
	}
}

Array-based Priority Queue

public struct PriorityQueueArray<T: Equatable>: Queue {
    private var elements:[T] = []
    
    let sort: (Element, Element) -> Bool
    
    public init(sort: @escaping (Element,Element) -> Bool, elements: [Element] = []) {
        self.sort = sort
        self.elements = elements
        self.elements.sort(by: sort)
    }
    
    public var isEmpty: Bool {
        elements.isEmpty
    }
    
    public var peek: T? {
        elements.first
    }
    
    public mutating func enqueue(_ element: T) -> Bool {
        for (index, otherElement) in elements.enumerated() {
            if sort(element, otherElement) {
                elements.insert(element, at: index)
                return true
            }
        }
        elements.append(element)
        return true
    }
    
    public mutating func dequeue() -> T? {
        isEmpty ? nil : elements.removeFirst()
    }
}

extension PriorityQueueArray: CustomStringConvertible {

  public var description: String {
    String(describing: elements)
  }
}

var priorityQueue = PriorityQueue(sort: >, elements: [1,12,3,4,1,6,8,7]) 

while !priorityQueue.isEmpty {  
	print(priorityQueue.dequeue()!) 
}

12 
8 
7 
6 
4 
3 
1 1