[Swift]实现优先队列PriorityQueue
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/ ）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10964064.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
助力理解优先队列：LeetCode347. 前K个高频元素 | Top K Frequent Elements
你是否在刷题的过程中遇到这样的情况？在一个循环中插入数组元素，同时需要对数组进行排序，在当前循环中按优先级获取数组的元素进行相关操作，如果将插入和排序分为两个步骤，很可能得到这样的结果：Time Limit Exceeded[超出时间限制]。这就需要有一种数据结构：在插入操作的过程中，元素已被放置在正确的排序位置上，插入元素后后可以直接按优先级获取数组的元素。优先队列PriorityQueue可以实现这种功能。在优先队列中，元素被赋予优先级。最大值或最小值都可以被定义为优先级。当优先队列的元素并非简单的Int类型，而是多维数组或元组等其他数据结构，可以自定义优先级。
在C++、C#、Java等一些经典编程语言的工具包中，工程师已经帮你创建PriorityQueue的数据结构，只需要简单导入调用，立马可以一顿操作猛如虎。但是，如果你正在使用类似于Swift这种2014年发布的编程语言，刷题的时候，你发现有些数据结构需要自己实施。数据结构万变不离其宗，追本溯源，请即刻上车，并且系好安全带。现在发车，先从源头回顾一些概念。
1、满二叉树。
定义：一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上。
2、完全二叉树。
定义：对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。
3、二叉堆
二叉堆本质上是一种完全二叉树。
最大堆：任何一个父节点的值，都大于等于它左、右孩子节点的值。
最小堆：任何一个父节点的值，都小于等于它左、右孩子节点的值。
堆顶：二叉堆的根节点叫堆顶。
最大堆的堆顶是整个堆中的最大元素，
最小堆的堆顶是整个堆中的最小元素。
4、二叉堆的操作
（1）插入节点：上浮。
二叉堆插入节点时，插入位置是完全二叉树的最后一个位置。
此时，比较新节点和其父节点，是否符合最大堆或最小堆的定义。
若不符合则和父节点交换位置，即上浮。
重复这样的过程，直到不需要交换位置。
（2）删除节点：下沉。
二叉堆删除节点的过程和插入节点的过程正好相反。
删除的是堆顶的节点。删除堆顶后，堆顶空缺。
为了继续维持完全二叉树的结构，
把堆的最后一个节点，替补到堆顶空缺的位置。
让堆顶节点和其左右孩子进行比较，是否符合最大堆或最小堆的定义。
若不符合则和左右孩子交换位置，即下沉。
两种二叉堆的比较方法：
最小堆：取左右孩子节点中最小的一个交换下沉。
最大堆：取左右孩子节点中最大的一个交换下沉。
（3）构建二叉堆：
把一个无序的完全二叉树调整为二叉堆，
本质是：让所有非叶子节点依次执行下沉操作。
5、二叉堆操作的时间复杂度
二叉堆的插入操作是单一节点的上浮。
二叉堆的删除操作是单一节点的下沉。
这两个操作的平均交换次数都是堆高的一半。
二叉堆操作的时间复杂度：
插入：O(logn)
删除：O(logn)
构建：O(n)
6、二叉堆的物理存储。
二叉堆虽然是一个完全二叉树，但是其用顺序存储。
二叉堆的所有节点都存储在数组当中。
假设父节点的下标是p,则：
左孩子下标：2p + 1
右孩子下标：2p + 2
铺垫一大堆，我想你已经想要关闭本界面。
但这些都是优先队列知其然知其所以然，现在开始编代码。
在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。最高的优先级，即是堆顶节点。
根据二叉堆具有最大堆和最小堆。相应的优先队列也有两种：
最大优先队列：由最大堆实现，当前最大元素优先出队。
最小优先队列：由最小堆实现，当前最小元素优先出队。
简单的PriorityQueue示例：
1 /*
2 Created by 山青咏芝 on 2019/6/2
3 */
4 //Mark:最大优先队列
5 class PriorityQueue
6 {
7 //用于存储优先队列数据
8 var array:[Int]
9 //优先队列数据大小
10 var size:Int
11
12 //初始化优先队列
13 init()
14 {
15 //数组初始长度32
16 self.array = [Int](repeating: 0, count: 32)
17 //队列初始大小为0
18 self.size = 0
19 }
20
21 //MARK:队列扩容为原来的2倍
22 func resize()
23 {
24 self.array += self.array
25 }
26
27 //Mark:入队
28 func enQueue(_ key:Int)
29 {
30 //队列长度超出范围，扩容
31 if size >= array.count
32 {
33 resize()
34 }
35 array[size] = key;
36 size += 1
37 //上浮
38 upAdjust()
39 }
40
41 //Mark:出队
42 func deQueue() -> Int
43 {
44 //获取堆顶元素
45 let head:Int = array[0]
46 size -= 1
47 //最后一个元素移动到堆顶
48 array[0] = array[size]
49 downAdjust()
50 return head
51 }
52
53 //Mark:上浮操作
54 func upAdjust()
55 {
56 var childIndex:Int = size - 1
57 var parentIndex:Int = (childIndex - 1)/2
58 // temp保存插入的叶子节点值，用于最后的赋值
59 let temp:Int = array[childIndex]
60 while(childIndex > 0 && temp > array[parentIndex])
61 {
62 //无需真正交换，单向赋值即可
63 array[childIndex] = array[parentIndex]
64 childIndex = parentIndex
65 parentIndex = parentIndex / 2
66 }
67 array[childIndex] = temp
68 }
69
70 //Mark:下沉操作
71 func downAdjust()
72 {
73 // temp保存父节点值，用于最后的赋值
74 var parentIndex:Int = 0
75 let temp:Int = array[parentIndex]
76 var childIndex:Int = 1
77 while (childIndex < size)
78 {
79 // 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
80 if childIndex + 1 < size && array[childIndex + 1] > array[childIndex]
81 {
82 childIndex += 1
83 }
84 // 如果父节点大于任何一个孩子的值，直接跳出
85 if temp >= array[childIndex] {break}
86 //无需真正交换，单向赋值即可
87 array[parentIndex] = array[childIndex]
88 parentIndex = childIndex
89 childIndex = 2 * childIndex + 1
90 }
91 array[parentIndex] = temp
92 }
93 }测试：
1 let queue:PriorityQueue = PriorityQueue() 2 queue.enQueue(0) 3 queue.enQueue(9) 4 queue.enQueue(1) 5 queue.enQueue(8) 6 queue.enQueue(3) 7 print(queue.deQueue()) 8 print(queue.deQueue()) 9 print(queue.deQueue()) 10 print(queue.deQueue()) 11 print(queue.deQueue()) 12 //Print 9 13 //Print 8 14 //Print 3 15 //Print 1 16 //Print 9
上面实现的是最大优先队列，我们想把优先队列是最大优先队列或最小的控制权限牢牢掌控在自己手中。甚至数组元素并非是Int类型。
一、自定义优先队列1:【PriorityQueue】。特别注意T可以为任何的数据结构。
1 public struct PriorityQueue<T> {
2 fileprivate var heap: Heap<T>
3 public init(sort: @escaping (T, T) -> Bool) {
4 heap = Heap(sort: sort)
5 }
6
7 public var isEmpty: Bool {
8 return heap.isEmpty
9 }
10
11 public var count: Int {
12 return heap.count
13 }
14
15 public func peek() -> T? {
16 return heap.peek()
17 }
18
19 public mutating func push(_ element: T) {
20 heap.insert(element)
21 }
22
23 public mutating func pop() -> T? {
24 return heap.remove()
25 }
26
27 public mutating func changePriority(index i: Int, value: T) {
28 return heap.replace(index: i, value: value)
29 }
30 }
31
32 extension PriorityQueue where T: Equatable {
33 public func index(of element: T) -> Int? {
34 return heap.index(of: element)
35 }
36 }
37
38 public struct Heap<T> {
39 var nodes = [T]()
40
41 private var orderCriteria: (T, T) -> Bool
42
43 public init(sort: @escaping (T, T) -> Bool) {
44 self.orderCriteria = sort
45 }
46
47 public init(array: [T], sort: @escaping (T, T) -> Bool) {
48 self.orderCriteria = sort
49 configureHeap(from: array)
50 }
51
52 private mutating func configureHeap(from array: [T]) {
53 nodes = array
54 for i in stride(from: (nodes.count/2-1), through: 0, by: -1) {
55 shiftDown(i)
56 }
57 }
58
59 public var isEmpty: Bool {
60 return nodes.isEmpty
61 }
62
63 public var count: Int {
64 return nodes.count
65 }
66
67 @inline(__always) internal func parentIndex(ofIndex i: Int) -> Int {
68 return (i - 1) / 2
69 }
70
71 @inline(__always) internal func leftChildIndex(ofIndex i: Int) -> Int {
72 return 2*i + 1
73 }
74
75 @inline(__always) internal func rightChildIndex(ofIndex i: Int) -> Int {
76 return 2*i + 2
77 }
78
79 public func peek() -> T? {
80 return nodes.first
81 }
82
83 public mutating func insert(_ value: T) {
84 nodes.append(value)
85 shiftUp(nodes.count - 1)
86 }
87
88 public mutating func insert<S: Sequence>(_ sequence: S) where S.Iterator.Element == T {
89 for value in sequence {
90 insert(value)
91 }
92 }
93
94 public mutating func replace(index i: Int, value: T) {
95 guard i < nodes.count else { return }
96
97 remove(at: i)
98 insert(value)
99 }
100
101 @discardableResult public mutating func remove() -> T? {
102 guard !nodes.isEmpty else { return nil }
103
104 if nodes.count == 1 {
105 return nodes.removeLast()
106 } else {
107 let value = nodes[0]
108 nodes[0] = nodes.removeLast()
109 shiftDown(0)
110 return value
111 }
112 }
113
114 @discardableResult public mutating func remove(at index: Int) -> T? {
115 guard index < nodes.count else { return nil }
116
117 let size = nodes.count - 1
118 if index != size {
119 nodes.swapAt(index, size)
120 shiftDown(from: index, until: size)
121 shiftUp(index)
122 }
123 return nodes.removeLast()
124 }
125
126 internal mutating func shiftUp(_ index: Int) {
127 var childIndex = index
128 let child = nodes[childIndex]
129 var parentIndex = self.parentIndex(ofIndex: childIndex)
130
131 while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) {
132 nodes[childIndex] = nodes[parentIndex]
133 childIndex = parentIndex
134 parentIndex = self.parentIndex(ofIndex: childIndex)
135 }
136
137 nodes[childIndex] = child
138 }
139
140 internal mutating func shiftDown(from index: Int, until endIndex: Int) {
141 let leftChildIndex = self.leftChildIndex(ofIndex: index)
142 let rightChildIndex = leftChildIndex + 1
143
144 var first = index
145 if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) {
146 first = leftChildIndex
147 }
148 if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) {
149 first = rightChildIndex
150 }
151 if first == index { return }
152
153 nodes.swapAt(index, first)
154 shiftDown(from: first, until: endIndex)
155 }
156
157 internal mutating func shiftDown(_ index: Int) {
158 shiftDown(from: index, until: nodes.count)
159 }
160
161 }
162
163 extension Heap where T: Equatable {
164
165 public func index(of node: T) -> Int? {
166 return nodes.firstIndex(where: { $0 == node })
167 }
168
169 @discardableResult public mutating func remove(node: T) -> T? {
170 if let index = index(of: node) {
171 return remove(at: index)
172 }
173 return nil
174 }
175 }示例代码：
1 var pq = PriorityQueue<Int> { $0 > $1 }
2 pq.push(1)
3 pq.push(2)
4 pq.push(3)
5 dump(pq)
6 /*
7 ▿ prog.PriorityQueue<Swift.Int>
8 ▿ heap: prog.Heap<Swift.Int>
9 ▿ nodes: 3 elements
10 - 3
11 - 1
12 - 2
13 - orderCriteria: (Function)
14 */
15 print(pq.pop())
16 //Print Optional(3)二、自定义优先队列2:【PriorityQueue】
1 public struct PriorityQueue<T: Comparable> {
2 fileprivate var heap = [T]()
3 private let ordered: (T, T) -> Bool
4
5 //创建具有给定顺序的新PriorityQueue。
6 //order：true:降序 | false：升序
7 //StartingValues:用于初始化PriorityQueue的元素数组。
8 public init(_ ascending: Bool = false,_ startingValues: [T] = []) {
9 self.init(order: ascending ? { $0 > $1 } : { $0 < $1 }, startingValues: startingValues)
10 }
11
12 public init(order: @escaping (T, T) -> Bool, startingValues: [T] = []) {
13 ordered = order
14 //堆构造
15 heap = startingValues
16 var i = heap.count/2 - 1
17 while i >= 0 {
18 sink(i)
19 i -= 1
20 }
21 }
22
23 //优先级队列存储了多少个元素
24 public var count: Int { return heap.count }
25
26 //如果且仅当优先级队列为空时为true
27 public var isEmpty: Bool { return heap.isEmpty }
28
29 // 在优先级队列中添加新元素,复杂度：O(lg n)
30 // element: 要插入优先级队列的元素.
31 public mutating func push(_ element: T) {
32 heap.append(element)
33 swim(heap.count - 1)
34 }
35
36 //移除并返回具有最高优先级的元素（如果升序，则为最低优先级）。复杂度： O(lg n)
37 //returns:优先级队列中优先级最高的元素，如果优先级队列为空，则为零。
38 public mutating func pop() -> T? {
39 if heap.isEmpty { return nil }
40 //增加了Swift 2兼容性
41 if heap.count == 1 { return heap.removeFirst() }
42 //以便不使用同一位置的两个实例调用swap()
43 heap.swapAt(0, heap.count - 1)
44 let temp = heap.removeLast()
45 sink(0)
46 return temp
47 }
48
49 private mutating func sink(_ index: Int) {
50 var index = index
51 while 2 * index + 1 < heap.count {
52 var j = 2 * index + 1
53 if j < (heap.count - 1) && ordered(heap[j], heap[j + 1]) { j += 1 }
54 if !ordered(heap[index], heap[j]) { break }
55 heap.swapAt(index, j)
56 index = j
57 }
58 }
59
60 private mutating func swim(_ index: Int) {
61 var index = index
62 while index > 0 && ordered(heap[(index - 1) / 2], heap[index]) {
63 heap.swapAt((index - 1) / 2, index)
64 index = (index - 1) / 2
65 }
66 }
67 }示例代码：
1 var pq: PriorityQueue<Int> = PriorityQueue<Int>(false,[Int]()) 2 pq.push(1) 3 pq.push(2) 4 pq.push(3) 5 dump(pq) 6 /* 7 ▿ prog.PriorityQueue<Swift.Int> 8 ▿ heap: 3 elements 9 - 3 10 - 1 11 - 2 12 - ordered: (Function) 13 */ 14 print(pq.pop()) 15 //Print Optional(3)
三、自定义优先队列3:【Heap】
1 public struct Heap {
2 var elements: [Int] = []
3 let sort: (Int, Int) -> Bool
4 var isEmpty: Bool {
5 return self.elements.isEmpty
6 }
7
8 var count: Int {
9 return self.elements.count
10 }
11
12 func peek() -> Int? {
13 return elements.first
14 }
15
16 init(sort: @escaping (Int, Int) -> Bool, elements: [Int] = []) {
17 self.sort = sort
18 self.elements = elements
19
20 if !elements.isEmpty {
21 for i in stride(from: elements.count/2 - 1, through: 0, by: -1) {
22 siftDown(from: i)
23 }
24 }
25 }
26
27 mutating func siftDown(from index: Int) {
28 var parent = index
29 while true {
30 let left = leftIndex(of: parent)
31 let right = rightIndex(of: parent)
32 var candidate = parent
33 if left < count && sort(elements[left], elements[candidate]) {
34 candidate = left
35 }
36 if right < count && sort(elements[right], elements[candidate]) {
37 candidate = right
38 }
39 if candidate == parent {
40 return
41 }
42 elements.swapAt(parent, candidate)
43 parent = candidate
44 }
45 }
46
47 mutating func siftUp(from index: Int) {
48 var child = index
49 var parent = parentIndex(of: child)
50 while child > 0 && sort(elements[child], elements[parent]) {
51 elements.swapAt(child, parent)
52 child = parent
53 parent = parentIndex(of: child)
54 }
55 }
56
57 mutating func push(_ element: Int) {
58 elements.append(element)
59 siftUp(from: count-1)
60 }
61
62 mutating func pop() -> Int? {
63 guard !isEmpty else { return nil }
64 elements.swapAt(0, count-1)
65 defer {
66 siftDown(from: 0)
67 }
68 return elements.popLast()
69 }
70
71 func leftIndex(of index: Int) -> Int {
72 return (2 * index) + 1
73 }
74
75 func rightIndex(of index: Int) -> Int {
76 return (2 * index) + 2
77 }
78
79 func parentIndex(of index: Int) -> Int {
80 return (index - 1) / 2
81 }
82 }示例代码：
1 var pq:Heap = Heap(sort: >) 2 pq.push(1) 3 pq.push(2) 4 pq.push(3) 5 dump(pq) 6 /* 7 ▿ prog.Heap 8 ▿ elements: 3 elements 9 - 3 10 - 1 11 - 2 12 - sort: (Function) 13 */ 14 print(pq.pop()) 15 //Print Optional(3)
四、自定义优先队列4:【Heap】
1 class Heap {
2 var arr = [0]
3 var count: Int {
4 return arr.count-1
5 }
6 var top: Int {
7 return arr[1]
8 }
9 func push(_ num: Int) -> Void {
10 arr.append(num)
11 var i = arr.count-1
12 while i > 1 {
13 if arr[i] > arr[i/2] {
14 (arr[i], arr[i/2]) = (arr[i/2], arr[i])
15 } else {
16 break
17 }
18 i /= 2
19 }
20 }
21
22 func pop() -> Int {
23 var ret = self.top
24 var last = arr.removeLast()
25 if self.count == 0 {
26 return ret
27 }
28 arr[1] = last
29 var i = 1
30 while i < arr.count {
31 let left = i*2
32 let right = i*2+1
33 var next = i
34 if left < arr.count && arr[left] > arr[next] {
35 next = left
36 }
37 if right < arr.count && arr[right] > arr[next] {
38 next = right
39 }
40 if i != next {
41 (arr[i], arr[next]) = (arr[next], arr[i])
42 i = next
43 } else {
44 break
45 }
46 }
47 return ret
48 }
49 }示例代码：
1 var pq:Heap = Heap() 2 pq.push(1) 3 pq.push(2) 4 pq.push(3) 5 dump(pq) 6 /* 7 ▿ prog.Heap #0 8 ▿ arr: 4 elements 9 - 0 10 - 3 11 - 1 12 - 2 13 */ 14 print(pq.pop()) 15 //Print 3
五、自定义优先队列5:【Heap】
1 struct Heap<Element>
2 {
3 var elements : [Element]
4 let priorityFunction : (Element, Element) -> Bool
5
6 init(elements: [Element] = [], priorityFunction: @escaping (Element, Element) -> Bool) {
7 self.elements = elements
8 self.priorityFunction = priorityFunction
9 buildHeap()
10 }
11
12 mutating func buildHeap() {
13 for index in (0 ..< count / 2).reversed() {
14 siftDown(elementAtIndex: index)
15 }
16 }
17
18 var isEmpty : Bool { return elements.isEmpty }
19 var count : Int { return elements.count }
20
21 func peek() -> Element? {
22 return elements.first
23 }
24
25 mutating func push(_ element: Element) {
26 elements.append(element)
27 siftUp(elementAtIndex: count - 1)
28 }
29
30 mutating func siftUp(elementAtIndex index: Int) {
31 let parent = parentIndex(of: index)
32 guard !isRoot(index),
33 isHigherPriority(at: index, than: parent)
34 else { return }
35 swapElement(at: index, with: parent)
36 siftUp(elementAtIndex: parent)
37 }
38
39 mutating func pop() -> Element? {
40 guard !isEmpty
41 else { return nil }
42 swapElement(at: 0, with: count - 1)
43 let element = elements.removeLast()
44 if !isEmpty {
45 siftDown(elementAtIndex: 0)
46 }
47 return element
48 }
49
50 mutating func siftDown(elementAtIndex index: Int) {
51 let childIndex = highestPriorityIndex(for: index)
52 if index == childIndex {
53 return
54 }
55 swapElement(at: index, with: childIndex)
56 siftDown(elementAtIndex: childIndex)
57 }
58
59 // Helper functions
60 func isRoot(_ index: Int) -> Bool {
61 return index == 0
62 }
63
64 func leftChildIndex(of index: Int) -> Int {
65 return (2 * index) + 1
66 }
67
68 func rightChildIndex(of index: Int) -> Int {
69 return (2 * index) + 2
70 }
71
72 func parentIndex(of index: Int) -> Int {
73 return (index - 1) / 2
74 }
75
76 func isHigherPriority(at firstIndex: Int, than secondIndex: Int) -> Bool {
77 return priorityFunction(elements[firstIndex], elements[secondIndex])
78 }
79
80 func highestPriorityIndex(of parentIndex: Int, and childIndex: Int) -> Int {
81 guard childIndex < count && isHigherPriority(at: childIndex, than: parentIndex)
82 else { return parentIndex }
83 return childIndex
84 }
85
86 func highestPriorityIndex(for parent: Int) -> Int {
87 return highestPriorityIndex(of: highestPriorityIndex(of: parent, and: leftChildIndex(of: parent)), and: rightChildIndex(of: parent))
88 }
89
90 mutating func swapElement(at firstIndex: Int, with secondIndex: Int) {
91 guard firstIndex != secondIndex
92 else { return }
93 elements.swapAt(firstIndex, secondIndex)
94 }
95 }
96
97 extension Heap where Element : Equatable {
98 mutating func remove(_ element: Element) {
99 guard let index = elements.index(of: element)
100 else { return }
101 swapElement(at: index, with: count - 1)
102 elements.remove(at: count - 1)
103 siftDown(elementAtIndex: index)
104 }
105
106 mutating func boost(_ element: Element) {
107 guard let index = elements.index(of: element)
108 else { return }
109 siftUp(elementAtIndex: index)
110 }
111 }示例代码：
1 var pq = Heap<Int>(elements: [], priorityFunction: >) 2 pq.push(1) 3 pq.push(2) 4 pq.push(3) 5 dump(pq) 6 /* 7 ▿ prog.Heap<Swift.Int> 8 ▿ elements: 3 elements 9 - 3 10 - 1 11 - 2 12 - priorityFunction: (Function) 13 */ 14 print(pq.pop()) 15 //Print Optional(3)