Package com.zybooks.dsaj.pq

Class HeapAdaptablePriorityQueue<K,V>

java.lang.Object

com.zybooks.dsaj.pq.AbstractPriorityQueue<K,V>

com.zybooks.dsaj.pq.HeapPriorityQueue<K,V>

com.zybooks.dsaj.pq.HeapAdaptablePriorityQueue<K,V>

Type Parameters:

K - The key type (keys must be unique and comparable)

V - The value type stored with each entry

All Implemented Interfaces:

AdaptablePriorityQueue<K,V>, PriorityQueue<K,V>

public class HeapAdaptablePriorityQueue<K,V>
extends HeapPriorityQueue<K,V>
implements AdaptablePriorityQueue<K,V>

An implementation of an adaptable priority queue using an array-based heap.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	HeapAdaptablePriorityQueue.AdaptablePQEntry<K,V>	Extension of the PQEntry to include location information.

Nested classes/interfaces inherited from class com.zybooks.dsaj.pq.AbstractPriorityQueue

AbstractPriorityQueue.PQEntry<K,V>

Field Summary

Fields inherited from class com.zybooks.dsaj.pq.HeapPriorityQueue

heap

Constructor Summary

Constructors

Constructor	Description
HeapAdaptablePriorityQueue()	Creates an empty adaptable priority queue using natural ordering of keys.
HeapAdaptablePriorityQueue(Comparator<K> comp)	Creates an empty adaptable priority queue using the given comparator to order keys.

Method Summary

Modifier and Type	Method	Description
protected void	bubble(int j)	Restores the heap property by moving the entry at index j upward/downward.
protected AbstractPriorityQueue.PQEntry<K,V>	createEntry(K key, V value)	Factory function to create an entry storing key,value.
void	remove(Entry<K,V> entry)	Removes the given entry from the priority queue.
void	replaceKey(Entry<K,V> entry, K key)	Replaces the key of an entry.
void	replaceValue(Entry<K,V> entry, V value)	Replaces the value of an entry.
protected void	swap(int i, int j)	Exchanges the entries at indices i and j of the array list.
protected HeapAdaptablePriorityQueue.AdaptablePQEntry<K,V>	validate(Entry<K,V> entry)	Validates an entry to ensure it is location-aware.

Methods inherited from class com.zybooks.dsaj.pq.HeapPriorityQueue

downheap, hasLeft, hasRight, heapify, insert, left, min, parent, removeMin, right, size, upheap

Methods inherited from class com.zybooks.dsaj.pq.AbstractPriorityQueue

compare, isEmpty

Methods inherited from class java.lang.Object

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

Methods inherited from interface com.zybooks.dsaj.pq.PriorityQueue

insert, isEmpty, min, removeMin, size

Constructor Details

HeapAdaptablePriorityQueue

public HeapAdaptablePriorityQueue()

Creates an empty adaptable priority queue using natural ordering of keys.

HeapAdaptablePriorityQueue

public HeapAdaptablePriorityQueue(Comparator<K> comp)

Creates an empty adaptable priority queue using the given comparator to order keys.

Parameters:

comp - comparator defining the order of keys in the priority queue

Method Details

createEntry

protected AbstractPriorityQueue.PQEntry<K,V> createEntry(K key,
 V value)

Factory function to create an entry storing key,value.

Overrides:

createEntry in class AbstractPriorityQueue<K,V>

Parameters:

key - the key

value - the value

Returns:

the new PQEntry

validate

protected HeapAdaptablePriorityQueue.AdaptablePQEntry<K,V> validate(Entry<K,V> entry)
                                                             throws IllegalArgumentException

Validates an entry to ensure it is location-aware.

Parameters:

entry - an entry instance

Returns:

the entry cast as an AdaptablePQEntry instance

Throws:

IllegalArgumentException - if the given entry was not valid

swap

protected void swap(int i,
 int j)

Exchanges the entries at indices i and j of the array list.

Overrides:

swap in class HeapPriorityQueue<K,V>

bubble

protected void bubble(int j)

Restores the heap property by moving the entry at index j upward/downward.

remove

public void remove(Entry<K,V> entry)
            throws IllegalArgumentException

Removes the given entry from the priority queue.

Specified by:

remove in interface AdaptablePriorityQueue<K,V>

Parameters:

entry - an entry of this priority queue

Throws:

IllegalArgumentException - if e is not a valid entry for the priority queue.

replaceKey

public void replaceKey(Entry<K,V> entry,
 K key)
                throws IllegalArgumentException

Replaces the key of an entry.

Specified by:

replaceKey in interface AdaptablePriorityQueue<K,V>

Parameters:

entry - an entry of this priority queue

key - the new key

Throws:

IllegalArgumentException - if e is not a valid entry for the priority queue.

replaceValue

public void replaceValue(Entry<K,V> entry,
 V value)
                  throws IllegalArgumentException

Replaces the value of an entry.

Specified by:

replaceValue in interface AdaptablePriorityQueue<K,V>

Parameters:

entry - an entry of this priority queue

value - the new value

Throws:

IllegalArgumentException - if e is not a valid entry for the priority queue.