[Swift]实现优先队列PriorityQueue

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/ ）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10964064.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

助力理解优先队列：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      
                       
                    
                     
                      



鲜花




握手




雷人




路过




鸡蛋