DataStructures
Class LeftistHeap

java.lang.Object
  |
  +--DataStructures.LeftistHeap

public class LeftistHeap

extends java.lang.Object

Implements a leftist heap. Note that all "matching" is based on the compareTo method.

Constructor Summary

LeftistHeap()
Construct the leftist heap.

Method Summary

Comparable	deleteMin() Remove the smallest item from the priority queue.
Comparable	findMin() Find the smallest item in the priority queue.
void	insert(Comparable x) Insert into the priority queue, maintaining heap order.
boolean	isEmpty() Test if the priority queue is logically empty.
boolean	isFull() Test if the priority queue is logically full.
static void	main(java.lang.String[] args)
void	makeEmpty() Make the priority queue logically empty.
void	merge(LeftistHeap rhs) Merge rhs into the priority queue.

Methods inherited from class java.lang.Object

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

Constructor Detail

LeftistHeap

public LeftistHeap()

Construct the leftist heap.

Method Detail

merge

public void merge(LeftistHeap rhs)

Merge rhs into the priority queue. rhs becomes empty. rhs must be different from this.

Parameters:

rhs - the other leftist heap.

insert

public void insert(Comparable x)

Insert into the priority queue, maintaining heap order.

Parameters:

x - the item to insert.

findMin

public Comparable findMin()

Find the smallest item in the priority queue.

Returns:

the smallest item, or null, if empty.

deleteMin

public Comparable deleteMin()

Remove the smallest item from the priority queue.

Returns:

the smallest item, or null, if empty.

isEmpty

public boolean isEmpty()

Test if the priority queue is logically empty.

Returns:

true if empty, false otherwise.

isFull

public boolean isFull()

Test if the priority queue is logically full.

Returns:

false in this implementation.

makeEmpty

public void makeEmpty()

Make the priority queue logically empty.

main

public static void main(java.lang.String[] args)