大佬教程收集整理的这篇文章主要介绍了[Swift]自定义数据结构:优先队列PriorityQueue,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
优先队列【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 = 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-升序:
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 elements 16 - 9 17 - 8 18 - 7 19 - 6 20 - 5 21 - 4 22 - 3 23 - 2 24 - 1 25 - 0 26 - 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 elements 16 - 0 17 - 1 18 - 4 19 - 3 20 - 2 21 - 8 22 - 5 23 - 9 24 - 6 25 - 7 26 - 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 elements 16 - 9 17 - 8 18 - 5 19 - 6 20 - 7 21 - 1 22 - 4 23 - 0 24 - 3 25 - 2 26 - 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 elements 16 - 0 17 - 1 18 - 2 19 - 3 20 - 4 21 - 5 22 - 6 23 - 7 24 - 8 25 - 9 26 - ordered: (Function) 27 */
以上是大佬教程为你收集整理的[Swift]自定义数据结构:优先队列PriorityQueue全部内容,希望文章能够帮你解决[Swift]自定义数据结构:优先队列PriorityQueue所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。