java.lang.Object
- minpq.OptimizedHeapMinPQ<T>

Type Parameters:

T - the type of elements in this priority queue.

All Implemented Interfaces:

ExtrinsicMinPQ<T>
```
public class OptimizedHeapMinPQ<T>
extends Object
implements ExtrinsicMinPQ<T>
```
Optimized binary heap implementation of the ExtrinsicMinPQ interface.

See Also:

ExtrinsicMinPQ

Field Summary

Fields
Modifier and Type	Field	Description
`private List<PriorityNode<T>>`	`items`	`List` of `PriorityNode` objects representing the heap of item-priority pairs.
`private Map<T,Integer>`	`itemToIndex`	`Map` of each item to its associated index in the `items` heap.

Constructor Summary

Constructors
Constructor Description

OptimizedHeapMinPQ()
Constructs an empty instance.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`private boolean`	`accessible(int index)`	Returns true if and only if the index is accessible.
`void`	`add(T item, double priority)`	Adds an item with the given priority value.
`void`	`changePriority(T item, double priority)`	Updates the given items' associated priority value.
`boolean`	`contains(T item)`	Returns true if the given item is in this priority queue.
`private static int`	`left(int index)`	Returns the index of the given index's left child.
`private int`	`min(int index1, int index2)`	Returns the index with the lower priority, or 0 if neither is accessible.
`private static int`	`parent(int index)`	Returns the index of the given index's parent node.
`T`	`peekMin()`	Returns the item with the minimum priority value.
`T`	`removeMin()`	Returns and removes the item with the minimum priority value.
`private static int`	`right(int index)`	Returns the index of the given index's right child.
`private void`	`sink(int index)`	Bubbles down the node currently at the given index.
`int`	`size()`	Returns the number of items in this priority queue.
`private void`	`swap(int index1, int index2)`	Swap the nodes at the two indices.
`private void`	`swim(int index)`	Bubbles up the node currently at the given index.

Methods inherited from class java.lang.Object
clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface minpq.ExtrinsicMinPQ
isEmpty

- Field Detail
  - items
```
private final List<PriorityNode<T>> items
```
    List of PriorityNode objects representing the heap of item-priority pairs.
  - itemToIndex
```
private final Map<T,Integer> itemToIndex
```
    Map of each item to its associated index in the items heap.
- Constructor Detail
  - OptimizedHeapMinPQ
```
public OptimizedHeapMinPQ()
```
    Constructs an empty instance.
- Method Detail
  - add
```
public void add(T item,
                double priority)
```
    Description copied from interface: ExtrinsicMinPQ
    
    Adds an item with the given priority value.
    
    Specified by:
    
    add in interface ExtrinsicMinPQ<T>
    
    Parameters:
    
    item - the element to add.
    
    priority - the priority value for the item.
  - contains
```
public boolean contains(T item)
```
    Description copied from interface: ExtrinsicMinPQ
    
    Returns true if the given item is in this priority queue.
    
    Specified by:
    
    contains in interface ExtrinsicMinPQ<T>
    
    Parameters:
    
    item - element to be checked for containment.
    
    Returns:
    
    true if the given item is in this priority queue.
  - peekMin
```
public T peekMin()
```
    Description copied from interface: ExtrinsicMinPQ
    
    Returns the item with the minimum priority value.
    
    Specified by:
    
    peekMin in interface ExtrinsicMinPQ<T>
    
    Returns:
    
    the item with the minimum priority value.
  - removeMin
```
public T removeMin()
```
    Description copied from interface: ExtrinsicMinPQ
    
    Returns and removes the item with the minimum priority value.
    
    Specified by:
    
    removeMin in interface ExtrinsicMinPQ<T>
    
    Returns:
    
    the item with the minimum priority value.
  - changePriority
```
public void changePriority(T item,
                           double priority)
```
    Description copied from interface: ExtrinsicMinPQ
    
    Updates the given items' associated priority value.
    
    Specified by:
    
    changePriority in interface ExtrinsicMinPQ<T>
    
    Parameters:
    
    item - the element whose associated priority value should be modified.
    
    priority - the updated priority value.
  - size
```
public int size()
```
    Description copied from interface: ExtrinsicMinPQ
    
    Returns the number of items in this priority queue.
    
    Specified by:
    
    size in interface ExtrinsicMinPQ<T>
    
    Returns:
    
    the number of elements in this priority queue.
  - parent
```
private static int parent(int index)
```
    Returns the index of the given index's parent node.
  - left
```
private static int left(int index)
```
    Returns the index of the given index's left child.
  - right
```
private static int right(int index)
```
    Returns the index of the given index's right child.
  - accessible
```
private boolean accessible(int index)
```
    Returns true if and only if the index is accessible.
  - min
```
private int min(int index1,
                int index2)
```
    Returns the index with the lower priority, or 0 if neither is accessible.
  - swap
```
private void swap(int index1,
                  int index2)
```
    Swap the nodes at the two indices.
  - swim
```
private void swim(int index)
```
    Bubbles up the node currently at the given index.
  - sink
```
private void sink(int index)
```
    Bubbles down the node currently at the given index.

Class OptimizedHeapMinPQ<T>

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Methods inherited from interface minpq.ExtrinsicMinPQ

Field Detail

items

itemToIndex

Constructor Detail

OptimizedHeapMinPQ

Method Detail

add

contains

peekMin

removeMin

changePriority

size

parent

left

right

accessible

min

swap

swim

sink