Package dsa.lab09.solutions

Class BinaryHeapPriorityQueue<Priority extends Comparable<Priority>,Item>

java.lang.Object

dsa.lab09.solutions.BinaryHeapPriorityQueue<Priority,Item>

Type Parameters:

Priority - the priority type

Item - the item type

All Implemented Interfaces:

Container<PriorityQueueItem<Priority,Item>>, PriorityQueue<Priority,Item>, Iterable<PriorityQueueItem<Priority,Item>>

public class BinaryHeapPriorityQueue<Priority extends Comparable<Priority>,Item>
extends Object
implements PriorityQueue<Priority,Item>

A binary heap priority queue.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	BinaryHeapPriorityQueue.BinaryHeapIterator<Priority extends Comparable<Priority>,Item>

Nested classes/interfaces inherited from interface dsa.lab09.base.PriorityQueue

PriorityQueue.ItemIterator<Priority extends Comparable<Priority>,Item>

Constructor Summary

Constructors

Constructor	Description
BinaryHeapPriorityQueue()	Construct an empty binary heap priority queue.
BinaryHeapPriorityQueue(PriorityQueueItem<Priority,Item>... items)	Construct a binary heap priority queue containing the given items.
BinaryHeapPriorityQueue(Iterable<PriorityQueueItem<Priority,Item>> items)	Construct a binary heap priority queue containing the given items.
BinaryHeapPriorityQueue(Iterable<PriorityQueueItem<Priority,Item>> items, int size)	Construct a binary heap priority queue containing the given items more efficiently than BinaryHeapPriorityQueue(Iterable).

Method Summary

Modifier and Type	Method	Description
void	insert(PriorityQueueItem<Priority,Item> item)	Insert the given prioritised item.
Iterable<PriorityQueueItem<Priority,Item>>	items()	Get a forward iterable that yields each prioritised item once.
PriorityQueueItem<Priority,Item>	max()	Get the item with the greatest priority.
PriorityQueueItem<Priority,Item>	removeMax()	Remove the item with the greatest priority.
Iterable<PriorityQueueItem<Priority,Item>>	reversed()	Get a reverse iterable that yields each prioritised item once.
int	size()	Get the number of contained items.

Methods inherited from class java.lang.Object

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

Methods inherited from interface dsa.lab02.base.Container

contains, isEmpty, iterator

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Methods inherited from interface dsa.lab09.base.PriorityQueue

insert, itemsOnly, reversedItemsOnly

Constructor Details

BinaryHeapPriorityQueue

public BinaryHeapPriorityQueue()

Construct an empty binary heap priority queue.

BinaryHeapPriorityQueue

public BinaryHeapPriorityQueue(Iterable<PriorityQueueItem<Priority,Item>> items)

Construct a binary heap priority queue containing the given items.

Parameters:

items - the items

BinaryHeapPriorityQueue

public BinaryHeapPriorityQueue(Iterable<PriorityQueueItem<Priority,Item>> items,
 int size)
                        throws IllegalArgumentException

Construct a binary heap priority queue containing the given items more efficiently than BinaryHeapPriorityQueue(Iterable).

Parameters:

items - the items

size - the number of items

Throws:

IllegalArgumentException - if size != n (where n is items's size)

BinaryHeapPriorityQueue

@SafeVarargs
public BinaryHeapPriorityQueue(PriorityQueueItem<Priority,Item>... items)

Construct a binary heap priority queue containing the given items.

Parameters:

items - the items

Method Details

size

public int size()

Description copied from interface: Container

Get the number of contained items.

Specified by:

size in interface Container<Priority extends Comparable<Priority>>

Returns:

the size

max

public PriorityQueueItem<Priority,Item> max()

Description copied from interface: PriorityQueue

Get the item with the greatest priority.

Specified by:

max in interface PriorityQueue<Priority extends Comparable<Priority>,Item>

Returns:

the maximum priority item, or null if empty

insert

public void insert(PriorityQueueItem<Priority,Item> item)

Description copied from interface: PriorityQueue

Insert the given prioritised item.

Specified by:

insert in interface PriorityQueue<Priority extends Comparable<Priority>,Item>

Parameters:

item - the prioritised item

removeMax

public PriorityQueueItem<Priority,Item> removeMax()

Description copied from interface: PriorityQueue

Remove the item with the greatest priority.

Specified by:

removeMax in interface PriorityQueue<Priority extends Comparable<Priority>,Item>

Returns:

the maximum priority item, or null if empty

items

public Iterable<PriorityQueueItem<Priority,Item>> items()

Description copied from interface: PriorityQueue

Get a forward iterable that yields each prioritised item once.

The items are iterated over in max-to-min order (by priority).

Specified by:

items in interface Container<Priority extends Comparable<Priority>>

Specified by:

items in interface PriorityQueue<Priority extends Comparable<Priority>,Item>

Returns:

an iterable over the prioritised items

reversed

public Iterable<PriorityQueueItem<Priority,Item>> reversed()

Description copied from interface: PriorityQueue

Get a reverse iterable that yields each prioritised item once.

The items are iterated over in min-to-max order (by priority).

Specified by:

reversed in interface PriorityQueue<Priority extends Comparable<Priority>,Item>

Returns:

an iterable over the prioritised items