Priority queue over comparable items with heap-style insertion and top-element access.

PriorityQueue

PriorityQueue

(Item -- queue) Creates an empty priority queue using the schema of Item.
  • The element schema must be a non-Meta In-place schema supported by Array and permit default initialization for insertion. For an existing prototype, supply a mutable view; an immutable prototype makes insertion fail. Direct Text and Code elements are unsupported; wrap them in an In-place Struct when needed.
  • The queue owns its backing array. Copying copies the backing array's items when their schema is copyable. Moving transfers the array and leaves the source empty. Destruction destroys remaining items and releases the allocation.

Fields

Methods

swap

(ordinal0 ordinal1 --) Swaps two backing-array positions.
  • Both ordinals must identify existing elements. Out-of-range access reports Index is out of range! when checked. This low-level operation exchanges slots without repairing heap order.

parent

(ordinal -- parentOrdinal) Returns the parent ordinal for one heap ordinal.
  • Ordinal 0 has no parent; the formula returns 0 there. Other inputs use (ordinal - 1) / 2. The arithmetic does not check whether the computed parent exists.

lchild

(ordinal -- childOrdinal) Returns the left-child ordinal.
  • The formula is ordinal * 2 + 1. The arithmetic does not check whether the computed child exists.

rchild

(ordinal -- childOrdinal) Returns the right-child ordinal.
  • The formula is ordinal * 2 + 2. The arithmetic does not check whether the computed child exists.

lift

(ordinal --) Moves one item upward while it is greater than its parent.
  • Requires an existing ordinal; out-of-range access reports Index is out of range! when checked. Repairs only an upward violation, and does not repair an item lowered beneath its children.

push

(item --) Appends one item and restores the heap ordering upward.
  • An immutable item view is copied; a mutable item view is moved. The item schema must support the selected transfer.
  • Supply exactly one Item.
  • If insertion can grow the backing allocation referenced by the input, copy or move the item to a separate object before insertion. See the Array.append known-issue note.

Known issue: aggregate input (1 100 2) @q.push leaves top 2 because only the last element is lifted; insert items one at a time.

top

(-- ref) Returns a reference to the greatest current item.
  • The reference is mutable through a mutable receiver and immutable through an immutable receiver; push, swap, lift, and growth can move items. A nonempty queue is required; an empty queue reports Index is out of range! when checked.

pop

(--) Intended to remove and destroy the greatest item without returning it; currently unavailable because calling pop fails compilation.

Known issue: calling pop fails compilation because its definition refers to the unavailable copy name. The diagnostic is «copy», Name was not found. push and top work.

getSize

(-- count) Returns the number of queued items.

empty

(-- cond) Reports whether the queue contains no items.

Ordering and empty state

Examples

Runtime example: empty state, size, and top

"PriorityQueue" use
"String"        use
"control"       use

{} Int32 {} [
  q: Int32 PriorityQueue;
  ("empty0=" q.empty LF) printList
  10 @q.push
  3 @q.push
  20 @q.push
  ("size=" q.getSize LF
    "top=" @q.top new LF
    "empty1=" q.empty LF) printList
  0
] "main" exportFunction

Expected Output

empty0=TRUE
size=3
top=20
empty1=FALSE

See also