Package com.zybooks.dsaj.pq

Class HeapPriorityQueue<K,V>

java.lang.Object
com.zybooks.dsaj.pq.AbstractPriorityQueue<K,V>
com.zybooks.dsaj.pq.HeapPriorityQueue<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:
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 com.zybooks.dsaj.pq.AbstractPriorityQueue

    AbstractPriorityQueue.PQEntry<K,V>

  • Field Summary

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

  • Constructor Summary

    Constructors
    Constructor
    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

    Modifier and Type
    Method
    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 returns the newly created entry.
    protected int
    left(int j)
     
    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 com.zybooks.dsaj.pq.AbstractPriorityQueue

    compare, createEntry, isEmpty

    Methods inherited from class java.lang.Object

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

  • Field Details

    • heap

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

  • Constructor Details

    • 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 Details

    • 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)
      Inserts a key-value pair and returns the newly created entry.
      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

    • removeMin

      public Entry<K,V> removeMin()
      Removes and returns an entry with minimal key.
      Returns:
      the removed entry (or null if empty)