本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下,大概有一百左右个的算法和数据结构,基本上常见的都包含了,是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club,边学习边翻译的项目。由于能力有限,如发现错误或翻译不妥,请指正,欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️,🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Bounded Priority Queue
有界优先队列(Bounded Priority queue)
有界优先级队列类似于常规优先队列,除了可以存储的元素数量有固定的上限。在队列处于满容量时,将新元素添加到队列时,具有最高优先级值的元素将从队列中弹出。
例子
假设我们有一个最大大小为5的有界优先级队列,它具有以下值和优先级:
Value: [ A, B, C, D, E ]
Priority: [ 4.6, 3.2, 1.33, 0.25, 0.1 ]
在这里,我们认为具有最高优先级值的对象是最重要的(因此这是max-priority队列)。 优先级值越大,我们关注的对象就越多。 所以A
比B
更重要,B
比C
更重要,依此类推。
现在我们要将优先级为0.4
的元素F
插入到这个有界优先级队列中。 因为队列大小最大为5,所以这将插入元素F
,然后逐出最低优先级元素(E
),产生更新的队列:
Value: [ A, B, C, F, D ]
Priority: [ 4.6, 3.2, 1.33, 0.4, 0.25 ]
由于其优先级值,在C
和D
之间插入F
。它不如C
重要,但比D
更重要。
假设我们希望将优先级为0.1的元素G
插入到此BPQ中。因为G
的优先级值小于队列中的最小优先级元素,所以在插入G
时它将立即被驱逐。换句话说,将元素插入优先级小于BPQ的最小优先级元素的BPQ中没有任何效果。
实施
虽然heap可能是优先级队列的一个非常简单的实现,但排序的链表允许 O(k) 插入和 O(1) 删除,其中 k 是元素的边界数。
以下是在Swift中的实现:
public class BoundedPriorityQueue<T: Comparable> {
private typealias Node = LinkedListNode<T>
private(set) public var count = 0
fileprivate var head: Node?
private var tail: Node?
private var maxElements: Int
public init(maxElements: Int) {
self.maxElements = maxElements
}
public var isEmpty: Bool {
return count == 0
}
public func peek() -> T? {
return head?.value
}
BoundedPriorityQueue
类包含LinkedListNode
对象的双向链表。 这里没什么特别的。 有趣的东西发生在enqueue()
方法中:
public func enqueue(_ value: T) {
if let node = insert(value, after: findInsertionPoint(value)) {
// If the newly inserted node is the last one in the list, then update
// the tail pointer.
if node.next == nil {
tail = node
}
// If the queue is full, then remove an element from the back.
count += 1
if count > maxElements {
removeLeastImportantElement()
}
}
}
private func insert(_ value: T, after: Node?) -> Node? {
if let previous = after {
// If the queue is full and we have to insert at the end of the list,
// then there's no reason to insert the new value.
if count == maxElements && previous.next == nil {
print("Queue is full and priority of new object is too small")
return nil
}
// Put the new node in between previous and previous.next (if exists).
let node = Node(value: value)
node.next = previous.next
previous.next?.previous = node
previous.next = node
node.previous = previous
return node
} else if let first = head {
// Have to insert at the head, so shift the existing head up once place.
head = Node(value: value)
head!.next = first
first.previous = head
return head
} else {
// This is the very first item in the queue.
head = Node(value: value)
return head
}
}
/* Find the node after which to insert the new value. If this returns nil,
the new value should be inserted at the head of the list. */
private func findInsertionPoint(_ value: T) -> Node? {
var node = head
var prev: Node? = nil
while let current = node where value < current.value {
prev = node
node = current.next
}
return prev
}
private func removeLeastImportantElement() {
if let last = tail {
tail = last.previous
tail?.next = nil
count -= 1
}
// Note: Instead of using a tail pointer, we could just scan from the new
// node until the end. Then nodes also don't need a previous pointer. But
// this is much slower on large lists.
}
我们首先检查队列是否已经具有最大元素数。 如果是这样,并且新的优先级值小于tail
元素的优先级值,那么这个新元素没有空间,我们返回时不插入它。
如果新值是可接受的,那么我们搜索列表以找到正确的插入位置并更新next
和previous
指针。
最后,如果队列现在已达到最大元素数,那么我们dequeue()
具有最大优先级值。
通过将最重要的元素保留在列表的前面,它使得出列非常容易:
public func dequeue() -> T? {
if let first = head {
count -= 1
if count == 0 {
head = nil
tail = nil
} else {
head = first.next
head!.previous = nil
}
return first.value
} else {
return nil
}
}
这只是从列表中删除head
元素并返回它。
网友评论