For instance, the bucket queue is a simple priority queue data structure consisting of an array indexed by priority, where each array cell contains a bucket of items with that priority. An extract-min operation performs a sequential search for the first non-empty bucket and chooses an arbitrary item in that bucket. For non-monotone extractions, each extract-min operation takes time (in the worst case) proportional to the array length (the number of distinct priorities).
