ABSTRACT

Priority Queue is one of the most extensively studied Abstract Data Types (ADT) due to its fundamental importance in the context of resource managing systems, such as operating systems. Priority Queues work on finite subsets of a totally ordered universal set U. Without any loss of generality we assume that U is simply the set of all non-negative integers. In its simplest form, a Priority Queue supports two operations, namely,

insert(x, S): update S by adding an arbitrary x ∈ U to S.

delete-min(S): update S by removing from S the minimum element of S.