Package placement

Class MaxPairingHeap<T extends Comparable<T>>

java.lang.Object
placement.MaxPairingHeap<T>
All Implemented Interfaces:
MaxPriorityQueue<T>
public class MaxPairingHeap<T extends Comparable<T>>
extends Object
implements MaxPriorityQueue<T>
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 Details

    • MaxPairingHeap

      public MaxPairingHeap()
      Construct the pairing heap.

    • MaxPairingHeap

      public MaxPairingHeap​(MaxPairingHeap<T> h1, MaxPairingHeap<T> h2)
      Construct the pairing heap by merging h1 and h2.

  • Method Details

    • add

      public void add​(T x)
      Insert into the priority queue, and return a PNode that can be used by decreaseKey. Duplicates are allowed.
      Specified by:
      add in interface MaxPriorityQueue<T extends Comparable<T>>
      Parameters:
      x - the item to insert.

    • add

      public void add​(PNode<T> p)

    • findMax

      public T findMax()
      Find the biggest item in the priority queue.
      Specified by:
      findMax in interface MaxPriorityQueue<T extends Comparable<T>>
      Returns:
      the biggest item, or null if empty.

    • deleteMax

      public T deleteMax()
      Remove the biggest item from the priority queue.
      Specified by:
      deleteMax in interface MaxPriorityQueue<T extends Comparable<T>>
      Returns:
      the biggest item, or null if empty.

    • increaseKey

      public void increaseKey​(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 bigger 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.

    • getAll

      public ArrayList<T> getAll()
      Specified by:
      getAll in interface MaxPriorityQueue<T extends Comparable<T>>

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • main

      public static void main​(String[] args)

    • merge

      public void merge​(MaxPriorityQueue<T> b)
      Specified by:
      merge in interface MaxPriorityQueue<T extends Comparable<T>>

    • size

      public int size()
      Specified by:
      size in interface MaxPriorityQueue<T extends Comparable<T>>