HeapPriorityQueue

java.lang.Object
- net.datastructures.AbstractPriorityQueue<K,V>
- - net.datastructures.HeapPriorityQueue<K,V>

All Implemented Interfaces:

PriorityQueue<K,V>

Direct Known Subclasses:

HeapAdaptablePriorityQueue
```
public class HeapPriorityQueue<K,V>
extends AbstractPriorityQueue<K,V>
```
An implementation of a priority queue using an array-based heap.

Nested Class Summary
- Nested classes/interfaces inherited from class net.datastructures.AbstractPriorityQueue
  AbstractPriorityQueue.PQEntry<K,V>

Field Summary

Fields
Modifier and Type Field and Description

protected ArrayList<Entry<K,V>> heap
primary collection of priority queue entries

Fields
Modifier and Type	Field and Description
`protected ArrayList<Entry<K,V>>`	`heap` primary collection of priority queue entries

Constructor Summary

Constructors
Constructor and Description
`HeapPriorityQueue()` Creates an empty priority queue based on the natural ordering of its keys.
`HeapPriorityQueue(Comparator<K> comp)` Creates an empty priority queue using the given comparator to order keys.
`HeapPriorityQueue(K[] keys, V[] values)` Creates a priority queue initialized with the respective key-value pairs.

Method Summary

Methods
Modifier and Type	Method and Description
`protected void`	`downheap(int j)` Moves the entry at index j lower, if necessary, to restore the heap property.
`protected boolean`	`hasLeft(int j)`
`protected boolean`	`hasRight(int j)`
`protected void`	`heapify()` Performs a bottom-up construction of the heap in linear time.
`Entry<K,V>`	`insert(K key, V value)` Inserts a key-value pair and return the entry created.
`protected int`	`left(int j)`
`static void`	`main(String[] args)`
`Entry<K,V>`	`min()` Returns (but does not remove) an entry with minimal key.
`protected int`	`parent(int j)`
`Entry<K,V>`	`removeMin()` Removes and returns an entry with minimal key.
`protected int`	`right(int j)`
`int`	`size()` Returns the number of items in the priority queue.
`protected void`	`swap(int i, int j)` Exchanges the entries at indices i and j of the array list.
`protected void`	`upheap(int j)` Moves the entry at index j higher, if necessary, to restore the heap property.

Methods inherited from class net.datastructures.AbstractPriorityQueue
checkKey, compare, isEmpty

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

- Field Detail
  - heap
```
protected ArrayList<Entry<K,V>> heap
```
    primary collection of priority queue entries
- Constructor Detail
  - HeapPriorityQueue
```
public HeapPriorityQueue()
```
    Creates an empty priority queue based on the natural ordering of its keys.
  - HeapPriorityQueue
```
public HeapPriorityQueue(Comparator<K> comp)
```
    Creates an empty priority queue using the given comparator to order keys.
    
    Parameters:
    comp - comparator defining the order of keys in the priority queue
  - HeapPriorityQueue
```
public HeapPriorityQueue(K[] keys,
                 V[] values)
```
    Creates a priority queue initialized with the respective key-value pairs. The two arrays given will be paired element-by-element. They are presumed to have the same length. (If not, entries will be created only up to the length of the shorter of the arrays)
    
    Parameters:
    keys - an array of the initial keys for the priority queue
    values - an array of the initial values for the priority queue
- Method Detail
  - parent
```
protected int parent(int j)
```
  - left
```
protected int left(int j)
```
  - right
```
protected int right(int j)
```
  - hasLeft
```
protected boolean hasLeft(int j)
```
  - hasRight
```
protected boolean hasRight(int j)
```
  - swap
```
protected void swap(int i,
        int j)
```
    Exchanges the entries at indices i and j of the array list.
  - upheap
```
protected void upheap(int j)
```
    Moves the entry at index j higher, if necessary, to restore the heap property.
  - downheap
```
protected void downheap(int j)
```
    Moves the entry at index j lower, if necessary, to restore the heap property.
  - heapify
```
protected void heapify()
```
    Performs a bottom-up construction of the heap in linear time.
  - size
```
public int size()
```
    Returns the number of items in the priority queue.
    
    Returns:
    number of items
  - min
```
public Entry<K,V> min()
```
    Returns (but does not remove) an entry with minimal key.
    
    Returns:
    entry having a minimal key (or null if empty)
  - insert
```
public Entry<K,V> insert(K key,
                V value)
                  throws IllegalArgumentException
```
    Inserts a key-value pair and return the entry created.
    
    Parameters:
    key - the key of the new entry
    value - the associated value of the new entry
    
    Returns:
    the entry storing the new key-value pair
    
    Throws:
    
    IllegalArgumentException - if the key is unacceptable for this queue
  - removeMin
```
public Entry<K,V> removeMin()
```
    Removes and returns an entry with minimal key.
    
    Returns:
    the removed entry (or null if empty)
  - main
```
public static void main(String[] args)
```

Class HeapPriorityQueue<K,V>

Nested Class Summary

Nested classes/interfaces inherited from class net.datastructures.AbstractPriorityQueue

Field Summary

Constructor Summary

Method Summary

Methods inherited from class net.datastructures.AbstractPriorityQueue

Methods inherited from class java.lang.Object

Field Detail

heap

Constructor Detail

HeapPriorityQueue

HeapPriorityQueue

HeapPriorityQueue

Method Detail

parent

left

right

hasLeft

hasRight

swap

upheap

downheap

heapify

size

min

insert

removeMin

main