[Swift]自定义数据结构：优先队列PriorityQueue

概述优先队列【priority queue】 普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。 优先队列特点：在优先队列中，元素被赋予优先级。 当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。 优先队列通常采用堆数据结构来实现。 队列：先进先出（FIFO—first in first out） 堆栈：先

优先队列【priority queue】

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。

优先队列特点：在优先队列中，元素被赋予优先级。

当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in,largest out）的行为特征。

优先队列通常采用堆数据结构来实现。

队列：先进先出（FIFO—first in first out）

堆栈：先进后出 (FILO—First-In/Last-Out)

可以将优先级队列想象为已修改的队列，但是当一个人从队列中获取下一个元素时，将首先检索优先级最高的元素。

堆栈和队列可以被建模为特定类型的优先级队列。

自定义结构类【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 = startingValues16         var i = heap.count/2 - 117         while i >= 0 {18             sink(i)19             i -= 120         }21     }22     23     //优先级队列存储了多少个元素24     public var count: Int { return heap.count }25     26     //如果且仅当优先级队列为空时为true27     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 temp47     }48     49     private mutating func sink(_ index: Int) {50         var index = index51         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 = j57         }58     }59     60     private mutating func swim(_ index: Int) {61         var index = index62         while index > 0 && ordered(heap[(index - 1) / 2],heap[index]) {63             heap.swapAt((index - 1) / 2,index)64             index = (index - 1) / 265         }66     }67 }

示例代码1-升序：

 1 var pq: PriorityQueue<Int> = PriorityQueue<Int>(false,[Int]()) 2 pq.push(9) 3 pq.push(8) 4 pq.push(7) 5 pq.push(6) 6 pq.push(5) 7 pq.push(4) 8 pq.push(3) 9 pq.push(2)10 pq.push(1)11 pq.push(0)12 dump(pq)13 /*14 ? prog.PriorityQueue<Swift.Int>15   ? heap: 10 elements16     - 917     - 818     - 719     - 620     - 521     - 422     - 323     - 224     - 125     - 026   - ordered: (Function)27 */

示例代码2-降序：

 1 var pq: PriorityQueue<Int> = PriorityQueue<Int>(true,[Int]()) 2 pq.push(9) 3 pq.push(8) 4 pq.push(7) 5 pq.push(6) 6 pq.push(5) 7 pq.push(4) 8 pq.push(3) 9 pq.push(2)10 pq.push(1)11 pq.push(0)12 dump(pq)13 /*14 ? prog.PriorityQueue<Swift.Int>15   ? heap: 10 elements16     - 017     - 118     - 419     - 320     - 221     - 822     - 523     - 924     - 625     - 726   - ordered: (Function)27 */

示例代码3-升序：

 1 var pq: PriorityQueue<Int> = PriorityQueue<Int>(false,[Int]()) 2 pq.push(0) 3 pq.push(1) 4 pq.push(2) 5 pq.push(3) 6 pq.push(4) 7 pq.push(5) 8 pq.push(6) 9 pq.push(7)10 pq.push(8)11 pq.push(9)12 dump(pq)13 /*14 ? prog.PriorityQueue<Swift.Int>15   ? heap: 10 elements16     - 917     - 818     - 519     - 620     - 721     - 122     - 423     - 024     - 325     - 226   - ordered: (Function)27 */

示例代码4-降序：

 1 var pq: PriorityQueue<Int> = PriorityQueue<Int>(true,[Int]()) 2 pq.push(0) 3 pq.push(1) 4 pq.push(2) 5 pq.push(3) 6 pq.push(4) 7 pq.push(5) 8 pq.push(6) 9 pq.push(7)10 pq.push(8)11 pq.push(9)12 dump(pq)13 /*14 ? prog.PriorityQueue<Swift.Int>15   ? heap: 10 elements16     - 017     - 118     - 219     - 320     - 421     - 522     - 623     - 724     - 825     - 926   - ordered: (Function)27 */

总结

以上是内存溢出为你收集整理的[Swift]自定义数据结构：优先队列PriorityQueue全部内容，希望文章能够帮你解决[Swift]自定义数据结构：优先队列PriorityQueue所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。