edu.ucsb.adl.middleware
Class PriorityDeque

java.lang.Object
  |
  +--edu.ucsb.adl.middleware.PriorityDeque

public final class PriorityDeque

extends java.lang.Object

A double-ended priority queue, or "priority deque". The elements of the queue must be pairwise comparable and totally and consistently ordered; any failure in this regard will generally result in a corrupt, useless queue. Elements can be inserted in O(log n) time and, in contrast to an ordinary priority queue, both minimum and maximum elements can be removed in O(log n) time.

This class is multithread-safe.

Our implementation is based on: M.D. Atkinson, J.-R. Sack, N. Santoro, and T. Strothotte, "Min-Max Heaps and Generalized Priority Queues," Communications of the ACM, vol. 29, no. 10, October 1986, pp. 996-1000. For an alternative algorithm, see: S.C. Chang and M.W. Du, "Diamond deque: A simple data structure for priority deques," Information Processing Letters, vol. 46, 1993, pp. 231-237.

Version:

$Header: /export/home/gjanee/middleware/edu/ucsb/adl/middleware/RCS/PriorityDeque.java,v 1.1 2000/02/26 17:03:53 gjanee Exp $

$Log: PriorityDeque.java,v $ Revision 1.1 2000/02/26 17:03:53 gjanee Initial revision

Author:

Greg Janée
Alexandria Digital Library

Constructor Summary

PriorityDeque()
Constructs an empty priority deque.

Method Summary

edu.ucsb.adl.middleware.Comparable	getMax() Returns the maximum element in the queue.
edu.ucsb.adl.middleware.Comparable	getMin() Returns the minimum element in the queue.
void	insert(edu.ucsb.adl.middleware.Comparable element) Inserts an element in the queue.
boolean	isEmpty() Tests if the queue is empty.
edu.ucsb.adl.middleware.Comparable	removeMax() Removes the maximum element from the queue.
edu.ucsb.adl.middleware.Comparable	removeMin() Removes the minimum element from the queue.
int	size() Returns the number of elements in the queue.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

PriorityDeque

public PriorityDeque()

Constructs an empty priority deque.

Method Detail

insert

public void insert(edu.ucsb.adl.middleware.Comparable element)

Inserts an element in the queue.

Parameters:

element - The element.

getMin

public edu.ucsb.adl.middleware.Comparable getMin()

Returns the minimum element in the queue.

Returns:

The minimum element, or null if the queue is empty.

getMax

public edu.ucsb.adl.middleware.Comparable getMax()

Returns the maximum element in the queue.

Returns:

The maximum element, or null if the queue is empty.

removeMin

public edu.ucsb.adl.middleware.Comparable removeMin()

Removes the minimum element from the queue. If the queue is empty, this method does nothing.

Returns:

The minimum element, or null if the queue is empty.

removeMax

public edu.ucsb.adl.middleware.Comparable removeMax()

Removes the maximum element from the queue. If the queue is empty, this method does nothing.

Returns:

The maximum element, or null if the queue is empty.

size

public int size()

Returns the number of elements in the queue.

Returns:

The number of elements.

isEmpty

public boolean isEmpty()

Tests if the queue is empty.

Returns:

true if the queue is empty.