How does PriorityQueue work in EK9?

← Collections and Data Structures · Ref: Q121

EK9 provides a generic PriorityQueue type that maintains elements in sorted order. It supports bounded size for top-N patterns and integrates with stream pipelines.

CREATION

Create a PriorityQueue with an initial element:

  pq <- PriorityQueue("first")

Or create an empty typed queue:

  pq <- PriorityQueue() of String

COMPARATOR SETUP

With no comparator a PriorityQueue orders its elements by their own <=>, so the element type must be orderable (String, Integer, a type with <=>); a queue of a type with no <=> is E07620 - build it with a comparator instead, in the same expression as the construction. A comparator decides the order explicitly:

  comparator <- () extends Comparator of String as pure function (r:=? t1 <=> t2)
  pq <- PriorityQueue("Bill").withComparator(comparator)

The comparator is a pure function using the <=> operator, and it must order every two set values: one that can answer unset for them is E07188 (Q2283), and one that answers unset at run time stops the queue with an Exception naming the two values - the queue never puts its natural order in place of the comparator you gave.

ADDING ELEMENTS

Use += to add elements:

  pq += "Ted"
  pq += "Excellent"

Elements are automatically maintained in priority order.

BOUNDED QUEUES

Create a bounded queue that keeps only the top N items:

  topThree <- pq.withSize(3)

When more than N elements are added, the lowest-priority element is dropped. This is the efficient top-N pattern.

ACCESSING ORDERED RESULTS

Get elements as a sorted list:

  items <- pq.list()

Or reverse the order:

  reversed <- pq.list().reverse()

STREAM INTEGRATION

Use PriorityQueue as a pipeline terminal:

  cat items | filter by isGood | collect as PriorityQueue of String

Or as a pipeline source:

  cat pq | map with transform > stdout

See Q45 for List basics. See Q120 for sorting. See Q122 for collect as custom aggregation. See Q126 for choosing the right collection type.

Example

#!ek9
defines module qa.collections.priorityqueue

  defines function

    comparingStrings() as pure
      ->
        t1 as String
        t2 as String
      <-
        rtn as Integer: t1 <=> t2

    suitableLength() as pure
      -> item as String
      <- rtn <- Boolean()
      minLength <- 3
      rtn: length item > minLength

  defines program

    PriorityQueueDemo()
      stdout <- Stdout()

      // === CREATION WITH COMPARATOR ===

      comparator <- () extends Comparator of String as pure function (r:=? t1 <=> t2)
      pq <- PriorityQueue("Bill").withComparator(comparator)

      // === ADDING ELEMENTS ===

      pq += "And"
      pq += "Ted"
      pq += "Excellent"
      pq += "Adventure"

      allEntries <- pq.list()
      stdout.println(`All entries: ${allEntries}`)

      // === BOUNDED QUEUE (TOP-N) ===

      topThree <- pq.withSize(3)
      limitedEntries <- topThree.list()
      stdout.println(`Top 3: ${limitedEntries}`)

      // === STREAM AS SOURCE ===

      cat allEntries | filter by suitableLength > stdout

      // === EMPTY QUEUE ===

      emptyQ <- PriorityQueue() of String
      require emptyQ?
      require emptyQ is empty
      stdout.println(`Empty PQ isSet: ${emptyQ?}`)

Common mistakes

E07620 — A PriorityQueue with no comparator orders its elements by '<=>', and List has none, so the queue cannot be built. Order a type with no '<=>' by building the queue with a comparator: (PriorityQueue() of (List of String)).withComparator(byLength). See ek9 -h E07620 for details.

Incorrect:

emptyQ <- PriorityQueue() of (List of String)

Correct:

emptyQ <- PriorityQueue() of String

E50060 — PriorityQueue does not have a Java-style peek() method. Use .list() to get all entries as a sorted List. See ek9 -h E50060 for details.

Incorrect:

allEntries <- pq.peek()

Correct:

allEntries <- pq.list()

E50060 — PriorityQueue does not have a Java-style toArray() method. Use .list() to get entries as a List. See ek9 -h E50060 for details.

Incorrect:

allEntries <- pq.toArray()

Correct:

allEntries <- pq.list()

E50060 — PriorityQueue does not have a Java-style .add() method. Use the += operator to add elements. See ek9 -h E50060 for details.

Incorrect:

pq.add("Ted")

Correct:

pq += "Ted"

E50060 — EK9 does not have toString(). Use the $ operator or string interpolation. See ek9 -h E50060 for details.

Incorrect:

stdout.println(allEntries.toString())

Correct:

stdout.println(`All entries: ${allEntries}`)

Coming from another language?

Java: PriorityQueue<T> with Comparator, no bounded size built-in (must manage manually). Python: heapq module, heapq.nlargest() for top-N. JavaScript: no built-in priority queue, use libraries. Rust: BinaryHeap<T> with Reverse wrapper. Go: container/heap interface. EK9: PriorityQueue(elem).withComparator(comp).withSize(n) fluent API, integrated with stream pipelines.

Keywords: bounded, collect, collection, comparator, data-structure, order, priority, queue, sorted, top, withComparator, withSize