rescuecore.tools.mapgenerator
Class PairHeap

java.lang.Object
  rescuecore.tools.mapgenerator.PairHeap

public class PairHeap

extends java.lang.Object

Constructor Summary

PairHeap()
Construct the pairing heap.

Method Summary

PairNode	addItem(int val, int priority) Insert into the priority queue, and return a PairNode that can be used by decreaseKey.
void	decreaseKey(PairNode p, int newPriority) Change the value of the item stored in the pairing heap.
int	deleteMin() Remove the smallest item from the priority queue.
int	findMin() Find the highest priority value in the priority queue.
PairNode	insert(int val, int priority) Insert into the priority queue.
boolean	isEmpty() Test if the priority queue is logically empty.
static void	main(java.lang.String[] args)
void	makeEmpty() Make the priority queue logically empty.

Methods inherited from class java.lang.Object

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

Constructor Detail

PairHeap

public PairHeap()

Construct the pairing heap.

Method Detail

insert

public PairNode insert(int val,
                       int priority)

Insert into the priority queue.

Parameters:

val - The value to insert

priority - The priority to give the value

addItem

public PairNode addItem(int val,
                        int priority)

Insert into the priority queue, and return a PairNode that can be used by decreaseKey. Duplicates are allowed.

Parameters:

val - the value to insert.

priority - The priority to give the value

Returns:

the node containing the newly inserted item.

findMin

public int findMin()

Find the highest priority value in the priority queue.

Returns:

the highest priority value.

deleteMin

public int deleteMin()

Remove the smallest item from the priority queue.

Throws:

Underflow - if the priority queue is empty.

decreaseKey

public void decreaseKey(PairNode p,
                        int newPriority)

Change the value of the item stored in the pairing heap.

Parameters:

p - any node returned by addItem.

newPriority - - must decrease

isEmpty

public boolean isEmpty()

Test if the priority queue is logically empty.

Returns:

true if empty, false otherwise.

makeEmpty

public void makeEmpty()

Make the priority queue logically empty.

main

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