The queue described earlier is a first-in, first-out linear data structure. The priority queue is determined by its priority.

Priority queues have the following types:

  • Maximum priority, always the biggest first team to exit;

  • Minimum priority, always the smallest first to leave the team.

Like binary heaps, priority queues can be used to find maximum and minimum values in lists of data, as well as problems such as minimum cost calculation, shortest path determination, and heap sorting.

implementation

Priority queues can be implemented in sorted arrays, balanced binary search trees, and binary heaps.

The time complexity of enqueue and dequeue operations is O(n), mainly because the memory space allocated by arrays is continuous, so deletion and insertion operations need to move.

The time complexity of enqueue and dequeue operations is O(log n), which is somewhat similar to sorted number array, in which the data are all sorted;

The time complexity of enqueue and dequeue operations is O(log n), and the sorting rules are not as strict as balanced binary search tree.

The following uses a binary heap-based priority queue. The protocols that a queue needs to implement are:

protocol Queue {
    associatedtype Element
    mutating func enqueue(_ element: Element) -> Bool
    mutating func dequeue() -> Element?
    var isEmpty: Bool { get }
    var peek: Element? { get }
}
Copy the code

It contains the basic functions used by a queue.

Priority queue implementation:

Struct PriorityQueue<Element: Equatable>: Queue {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()} // Time complexity O(log n) mutating func enqueue(_ element: Element) -> Bool {heap.insert(Element) return true} O(log n) mutating func dequeue() -> Element? { heap.remove() } } extension PriorityQueue: CustomStringConvertible { var description: String { heap.elements.description } }Copy the code

Since the binary heap has been implemented before, the code to implement the queue protocol on top of the binary heap is actually quite simple.

test

Here is a priority queue test with the maximum priority (the maximum is first queued) :

// sort: > var queue = PriorityQueue(sort: >, elements: [1, 23, 34, 3, 43, 32, 3, 44, 442]) print(queue) print("\n start dequeue: \n") while! queue.isEmpty { print(queue.dequeue()!) }Copy the code

Output:

[442, 44, 34, 23, 43, 32, 3, 1, 3]

开始 dequeue 出队：

442
44
43
34
32
23
3
3
1
Copy the code

The minimum priority queue looks like this (the minimum is queued first) :

// sort: <, var queue = PriorityQueue(sort: <, elements: [1, 23, 34, 3, 43, 32, 3, 44, 442]) print(queue) print("\n start dequeue: \n") while! queue.isEmpty { print(queue.dequeue()!) }Copy the code

Output:

[1, 3, 3, 23, 43, 32, 34, 44, 442]

开始 dequeue 出队：

1
3
3
23
32
34
43
44
442
Copy the code