Package placement

Class MinPairingHeap<T extends Comparable<T>>

java.lang.Object
placement.MinPairingHeap<T>
public class MinPairingHeap<T extends Comparable<T>>
extends Object
Implements a pairing heap. Supports a increaseKey operation. Note that all "matching" is based on the compareTo method. Based on implementation by Mark Allen Weiss from the book "Data Stuctures & Algorithm Analysis in Java" - Prentice Hall 1999

  • Constructor Summary

    Constructors
    Constructor Description
    MinPairingHeap()
    Construct the pairing heap.

  • Method Summary

    Modifier and Type Method Description
    void decreaseKey​(PNode<T> p, T newVal)
    Change the value of the item stored in the pairing heap.
    T deleteMin()
    Remove the smallest item from the priority queue.
    T findMin()
    Find the smallest item in the priority queue.
    PNode<T> insert​(T x)
    Insert into the priority queue, and return a PNode that can be used by decreaseKey.
    boolean isEmpty()
    Test if the priority queue is logically empty.
    static void main​(String[] args)  
    void makeEmpty()
    Make the priority queue logically empty.

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • MinPairingHeap

      public MinPairingHeap()
      Construct the pairing heap.

  • Method Details

    • insert

      public PNode<T> insert​(T x)
      Insert into the priority queue, and return a PNode that can be used by decreaseKey. Duplicates are allowed.
      Parameters:
      x - the item to insert.
      Returns:
      the PNode containing the newly inserted item.

    • findMin

      public T findMin()
      Find the smallest item in the priority queue.
      Returns:
      the smallest item, or null if empty.

    • deleteMin

      public T deleteMin()
      Remove the smallest item from the priority queue.
      Returns:
      the smallest item, or null if empty.

    • decreaseKey

      public void decreaseKey​(PNode<T> p, T newVal)
      Change the value of the item stored in the pairing heap. Does nothing if newVal is larger than the currently stored value.
      Parameters:
      p - any PNode returned by addItem.
      newVal - the new value, which must be smaller than the currently stored value.

    • isEmpty

      public boolean isEmpty()
      Test if the priority queue is logically empty.
      Returns:
      true if empty, false otherwise.

    • makeEmpty

      public void makeEmpty()
      Make the priority queue logically empty.

    • main

      public static void main​(String[] args)