This article is a translation of Swift Algorithm Club. Swift Algorithm Club is an open source project produced by Raywenderlich.com to realize algorithms and data structures by Swift. Currently, there are 18000+⭐️ on GitHub. I have made a brief statistics, and there are about 100 algorithms and data structures. It’s basically a good resource for iOSer learning algorithms and data structures. 🐙andyRon/ swift-algorithm-club-CN is my project of learning and translating for Swift Algorithm Club. Due to the limited capacity, if you find any errors or improper translation, please correct them. Welcome to Pull Request. Also welcome interested, have time partners to participate in translation and learning 🤓. Of course, we welcome ⭐️, 🤩🤩 ️ ⭐ ⭐. A translation of the text and code for this article can be found at 🐙swift-algorithm-club-cn/Bounded Priority Queue

Bounded Priority Queues

A bounded priority queue is similar to a regular priority queue, except that there is a fixed upper limit to the number of elements that can be stored. When a queue is at full capacity, the element with the highest priority value is ejected from the queue when a new element is added to the queue.

example

Suppose we have a bounded priority queue with a maximum size of 5, which has the following values and priorities:

Value: [A, B, C, D, E] Priority: [4.6, 3.2, 1.33, 0.25, 0.1]Copy the code

Here, we consider the object with the highest priority value to be the most important (hence the max-priority queue). The higher the priority value, the more objects we care about. So A is more important than B, B is more important than C, and so on.

Now we will insert the element F with priority 0.4 into the bounded priority queue. Since the queue size is 5 at most, this inserts element F and then ejects the lowest-priority element (E), producing an updated queue:

Value: [A, B, C, F, D] Priority: [4.6, 3.2, 1.33, 0.4, 0.25]Copy the code

Insert F between C and D because of its priority value. It is less important than C, but more important than D.

Suppose we want to insert element G of priority 0.1 into this BPQ. Because the priority value of G is less than the minimum priority element in the queue, it is immediately expelled when G is inserted. In other words, inserting an element into BPQ of the smallest priority element with a lower priority than BPQ has no effect.

The implementation of

While heap may be a very simple implementation of a priority queue, sorted linked lists allow O(k) inserts and O(1) deletes, where K is the number of edges of an element.

Here is the implementation in 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(a) -> T? {
    returnhead? .value }Copy the code

The BoundedPriorityQueue class contains a bidirectional list of LinkedListNode objects. There’s nothing special here. The interesting thing happens in the enqueue() method:

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 = previousreturn 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 = headreturn 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(a) {
  if letlast = 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.
}
Copy the code

We first check if the queue already has the maximum number of elements. If so, and the new priority value is less than the priority value of the tail element, then there is no space for the new element and we will not insert it when we return.

If the new value is acceptable, we search the list for the correct insertion location and update the next and Previous Pointers.

Finally, if the queue has now reached the maximum number of elements, then we dequeue() has the maximum priority value.

It makes listing very easy by keeping the most important elements first in the list:

public func dequeue(a) -> 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}}Copy the code

This simply removes the head element from the list and returns it.

Translated by Andy Ron and proofread by Andy Ron