The abstract state is a finite multiset of ordered values, initially empty. Multiplicity matters: deleting the minimum removes one occurrence, not every equal occurrence. Assume a consistent total order on This abstract data type places no fixed-capacity bound on insertion. The only operation requiring a nonempty collection is
T.trait PriorityQueue[T] {
// Pre: true. Post: Q' is the empty multiset.
def clear(): Unit
// Pre: true. Post: Q' = Q with one additional occurrence of x.
def insert(x: T): Unit
// Pre: Q is nonempty.
// Post: result is a minimum of Q;
// Q' is Q with exactly one occurrence of result removed.
def delMin(): T
// Pre: true. Post: result iff Q is empty, and Q' = Q.
def isEmpty(): Boolean
}delMin. The representation must preserve duplicates even if it uses a data structure commonly associated with sets.Yes, provided balancing guarantees logarithmic height. In a suitably maintained balanced binary tree of height , insertion searches one root-to-leaf path and deletion of the minimum follows the leftmost path. Reconnecting the tree and performing the required rebalancing also costs at most a constant amount per level for the standard logarithmic-time schemes. Thus both operations take time, conventionally written for nontrivial sizes. Merely calling a tree approximately balanced would not prove that height bound; it is the balancing guarantee that matters. Without it, a binary search tree can have linear height.
Not automatically: the duplicate-value policy must implement a multiset. A strict binary search tree storing one entry per distinct key represents a set; inserting a second equal value then loses a required occurrence. A fixed rule that puts all equal values on one side also needs care, because ordinary balancing rotations need not preserve that one-sided equality rule.
One valid refinement stores a multiplicity at each distinct key. Inserting an equal key increments its count;
delMin decrements the minimum key's count and removes that node only at zero. Alternatively, use distinct internal keys such as (value, uniqueSerial) while ordering primarily by value and returning only the value. With an appropriate balanced representation either approach preserves every occurrence and the required operation bounds. A bare claim about balanced search trees, with no treatment of duplicates, does not establish the abstract specification.A minimum-oriented binary heap is an appropriate alternative. Store a complete binary tree in an array and maintain heap order. Insertion appends a value and moves it upward; removing the root replaces it by the last value and moves that value downward. Each path has levels, and equal values can be stored in separate slots. Both operations therefore take time when capacity is available.
Unlike a binary search tree, the heap does not maintain a complete search order, so finding an arbitrary specified value can require inspections. A simple array implementation also has a capacity issue: a fixed array can fill, and resizing a growable array occasionally costs , giving an amortized insertion guarantee unless allocation is otherwise managed. This capacity cost is an implementation tradeoff, not an inherent inability of heaps to represent the priority queue abstraction.
Use one real linked list node per occurrence, with a private reference to the first:The representation invariant says that the reachable chain is finite, acyclic and nondecreasing in
class Node(val value: Int, var next: Node)
// Inside the queue implementation:
private var first: Node = nullvalue, and is owned by the queue. Equal adjacent values are explicitly allowed. The abstraction function is the multiset containing one occurrence of v.value for every reachable real linked list node v. Initially first==null represents the empty multiset. No artificial smallest Int is needed as a sentinel, and Int.MinValue remains a valid real value.Insert before the first entry that is at least the new value; equal values remain separate occurrences:In the scanning branch, the loop invariant says that
class ListPriorityQueue extends PriorityQueue[Int] {
private var first: Node = null
def clear(): Unit = { first = null }
def isEmpty(): Boolean = first == null
def insert(x: Int): Unit = {
if (first == null || x <= first.value) {
first = new Node(x, first)
} else {
var p = first
while (p.next != null && p.next.value < x) {
p = p.next
}
p.next = new Node(x, p.next)
}
}
def delMin(): Int = {
require(first != null, "Empty priority queue")
val result = first.value
first = first.next
result
}
}p is reachable and all values from first through p are strictly smaller than x. The rest of the chain is unchanged and remains sorted. The loop variant is the number of nodes after p. At exit either the next value is at least x or there is no next node, so inserting between p and p.next preserves the representation invariant and adds exactly one occurrence under the abstraction function. The head branch covers an empty chain, a new minimum and equality with the old minimum. delMin returns the head's minimum value and removes exactly that occurrence.Insertion is worst-case;
delMin, isEmpty and the head-resetting clear are . Reclaiming an abandoned chain later is garbage-collection work, not an explicit traversal performed by clear. Storage is , including separate nodes for duplicate values. No fixed insertion-capacity precondition has been added. Articles by others on the same topic
There are currently no matching articles.