Opus5
Class LeftistHeap

java.lang.Object
  |
  +--Opus5.AbstractObject
        |
        +--Opus5.AbstractContainer
              |
              +--Opus5.AbstractTree
                    |
                    +--Opus5.BinaryTree
                          |
                          +--Opus5.LeftistHeap

All Implemented Interfaces:

Comparable, Container, MergeablePriorityQueue, PriorityQueue, Tree

public class LeftistHeap

extends BinaryTree

implements MergeablePriorityQueue

A node of a mergeable priority queue implemented as a leftist tree.

Version:

$Id: LeftistHeap.java,v 3.6 1998/09/23 13:00:00 brpreiss Exp $

Author:

Bruno R. Preiss, P.Eng.

Inner classes inherited from class Opus5.AbstractTree

AbstractTree.TreeEnumeration

Field Summary

protected int

nullPathLength The null path length.

Fields inherited from class Opus5.BinaryTree

key, left, right

Fields inherited from class Opus5.AbstractContainer

count

Fields inherited from interface Opus5.MergeablePriorityQueue

copyright

Fields inherited from interface Opus5.Tree

copyright

Constructor Summary

LeftistHeap()
Constructs an empty LeftistHeap.

LeftistHeap(Comparable key)
Constructs a LeftistHeap that contains the specified key.

Method Summary

Comparable	dequeueMin() Dequeues and returns the "smallest" object in this leftist heap.
void	enqueue(Comparable object) Enqueues the specified object in this leftist heap.
Comparable	findMin() Returns the "smallest" object in this leftist heap.
void	merge(MergeablePriorityQueue queue) Merges the contents of the specified mergeable priority queue with this leftist heap.
protected void	swapSubtrees() Swaps the subtres of this node.

Methods inherited from class Opus5.BinaryTree

attachKey, attachLeft, attachRight, compareTo, depthFirstTraversal, detachKey, detachLeft, detachRight, getDegree, getKey, getLeft, getRight, getSubtree, isEmpty, isLeaf, purge

Methods inherited from class Opus5.AbstractTree

accept, breadthFirstTraversal, getCount, getEnumeration, getHeight

Methods inherited from class Opus5.AbstractContainer

hashCode, isFull, toString

Methods inherited from class Opus5.AbstractObject

compare, equals, isEQ, isGE, isGT, isLE, isLT, isNE

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface Opus5.Container

accept, getCount, getEnumeration, isEmpty, isFull, purge

Methods inherited from interface Opus5.Comparable

compare, isEQ, isGE, isGT, isLE, isLT, isNE

Field Detail

nullPathLength

protected int nullPathLength

The null path length.

Constructor Detail

LeftistHeap

public LeftistHeap()

Constructs an empty LeftistHeap.

LeftistHeap

public LeftistHeap(Comparable key)

Constructs a LeftistHeap that contains the specified key.

Method Detail

swapSubtrees

protected void swapSubtrees()

Swaps the subtres of this node.

merge

public void merge(MergeablePriorityQueue queue)

Merges the contents of the specified mergeable priority queue with this leftist heap. It is assumed that the specified priority queue is a LeftistHeap instance. After merging the contents, the specified queue is empty.

Specified by:

merge in interface MergeablePriorityQueue

Parameters:

queue - The queue to merge with this one.

enqueue

public void enqueue(Comparable object)

Enqueues the specified object in this leftist heap.

Specified by:

enqueue in interface PriorityQueue

Parameters:

object - The object to enqueue.

findMin

public Comparable findMin()

Returns the "smallest" object in this leftist heap. The smallest object in this leftist heap is the object that is less than or equal to all other objects in this leftist heap.

Specified by:

findMin in interface PriorityQueue

Returns:

The "smallest" object in this leftist heap.

Throws:

ContainerEmptyException - If this leftist heap is empty.

dequeueMin

public Comparable dequeueMin()

Dequeues and returns the "smallest" object in this leftist heap. The smallest object in this leftist heap is the object that is less than or equal to all other objects in this leftist heap.

Specified by:

dequeueMin in interface PriorityQueue

Returns:

The "smallest" object in this leftist heap.

Throws:

ContainerEmptyException - If this leftist heap is empty.