Fork me on GitHub

【译】Swift算法俱乐部-有界优先队列

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Clubraywenderlich.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的有界优先级队列,它具有以下值和优先级:

1
2
Value:    [ A,   B,   C,    D,    E   ]
Priority: [ 4.6, 3.2, 1.33, 0.25, 0.1 ]

在这里,我们认为具有最高优先级值的对象是最重要的(因此这是max-priority队列)。 优先级值越大,我们关注的对象就越多。 所以AB更重要,BC更重要,依此类推。

现在我们要将优先级为0.4的元素F插入到这个有界优先级队列中。 因为队列大小最大为5,所以这将插入元素F,然后逐出最低优先级元素(E),产生更新的队列:

1
2
Value:    [ A,   B,   C,    F,   D    ]
Priority: [ 4.6, 3.2, 1.33, 0.4, 0.25 ]

由于其优先级值,在CD之间插入F。它不如C重要,但比D更重要。

假设我们希望将优先级为0.1的元素G插入到此BPQ中。因为G的优先级值小于队列中的最小优先级元素,所以在插入G时它将立即被驱逐。换句话说,将元素插入优先级小于BPQ的最小优先级元素的BPQ中没有任何效果。

实施

虽然heap可能是优先级队列的一个非常简单的实现,但排序的链表允许 O(k) 插入和 O(1) 删除,其中 k 是元素的边界数。

以下是在Swift中的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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()方法中:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
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元素的优先级值,那么这个新元素没有空间,我们返回时不插入它。

如果新值是可接受的,那么我们搜索列表以找到正确的插入位置并更新nextprevious指针。

最后,如果队列现在已达到最大元素数,那么我们dequeue()具有最大优先级值。

通过将最重要的元素保留在列表的前面,它使得出列非常容易:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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元素并返回它。

作者:John Gill, Matthijs Hollemans
翻译:Andy Ron
校对:Andy Ron

坚持原创技术分享,您的支持将鼓励我继续创作!
0%