Class IndexBinomialMinPQ<Key>

  • All Implemented Interfaces:
    Iterable<Integer>

    public class IndexBinomialMinPQ<Key>
    extends Object
    implements Iterable<Integer>
    The IndexBinomialMinPQ class represents an indexed priority queue of generic keys. It supports the usual insert and delete-the-minimum operations, along with delete and change-the-key methods. In order to let the client refer to keys on the priority queue, an integer between 0 and N-1 is associated with each key ; the client uses this integer to specify which key to delete or change. It also supports methods for peeking at the minimum key, testing if the priority queue is empty, and iterating through the keys. This implementation uses a binomial heap along with an array to associate keys with integers in the given range. The insert, delete-the-minimum, delete, change-key, decrease-key, increase-key and size operations take logarithmic time. The is-empty, min-index, min-key, and key-of operations take constant time. Construction takes time proportional to the specified capacity.
    Author:
    Tristan Claverie
    • Constructor Summary

      Constructors 
      Constructor Description
      IndexBinomialMinPQ​(int N)
      Initializes an empty indexed priority queue with indices between 0 to N-1 Worst case is O(n)
      IndexBinomialMinPQ​(int N, Comparator<Key> comparator)
      Initializes an empty indexed priority queue with indices between 0 to N-1 Worst case is O(n)
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void changeKey​(int i, Key key)
      Changes the key associated with index i to the given key Worst case is O(log(n))
      boolean contains​(int i)
      Does the priority queue contains the index i ? Worst case is O(1)
      void decreaseKey​(int i, Key key)
      Decreases the key associated with index i to the given key Worst case is O(log(n))
      void delete​(int i)
      Deletes the key associated the given index Worst case is O(log(n))
      int delMin()
      Deletes the minimum key Worst case is O(log(n))
      void increaseKey​(int i, Key key)
      Increases the key associated with index i to the given key Worst case is O(log(n))
      void insert​(int i, Key key)
      Associates a key with an index Worst case is O(log(n))
      boolean isEmpty()
      Whether the priority queue is empty Worst case is O(1)
      Iterator<Integer> iterator()
      Gets an Iterator over the indexes in the priority queue in ascending order The Iterator does not implement the remove() method iterator() : Worst case is O(n) next() : Worst case is O(log(n)) hasNext() : Worst case is O(1)
      Key keyOf​(int i)
      Gets the key associated with index i Worst case is O(1)
      int minIndex()
      Gets the index associated with the minimum key Worst case is O(log(n))
      Key minKey()
      Gets the minimum key currently in the queue Worst case is O(log(n))
      int size()
      Number of elements currently on the priority queue Worst case is O(log(n))
    • Constructor Detail

      • IndexBinomialMinPQ

        public IndexBinomialMinPQ​(int N)
        Initializes an empty indexed priority queue with indices between 0 to N-1 Worst case is O(n)
        Parameters:
        N - number of keys in the priority queue, index from 0 to N-1
        Throws:
        IllegalArgumentException - if N < 0
      • IndexBinomialMinPQ

        public IndexBinomialMinPQ​(int N,
                                  Comparator<Key> comparator)
        Initializes an empty indexed priority queue with indices between 0 to N-1 Worst case is O(n)
        Parameters:
        N - number of keys in the priority queue, index from 0 to N-1
        comparator - a Comparator over the keys
        Throws:
        IllegalArgumentException - if N < 0
    • Method Detail

      • isEmpty

        public boolean isEmpty()
        Whether the priority queue is empty Worst case is O(1)
        Returns:
        true if the priority queue is empty, false if not
      • contains

        public boolean contains​(int i)
        Does the priority queue contains the index i ? Worst case is O(1)
        Parameters:
        i - an index
        Returns:
        true if i is on the priority queue, false if not
        Throws:
        IllegalArgumentException - if the specified index is invalid
      • size

        public int size()
        Number of elements currently on the priority queue Worst case is O(log(n))
        Returns:
        the number of elements on the priority queue
      • insert

        public void insert​(int i,
                           Key key)
        Associates a key with an index Worst case is O(log(n))
        Parameters:
        i - an index
        key - a Key associated with i
        Throws:
        IllegalArgumentException - if the specified index is invalid
        IllegalArgumentException - if the index is already in the queue
      • minIndex

        public int minIndex()
        Gets the index associated with the minimum key Worst case is O(log(n))
        Returns:
        the index associated with the minimum key
        Throws:
        NoSuchElementException - if the priority queue is empty
      • minKey

        public Key minKey()
        Gets the minimum key currently in the queue Worst case is O(log(n))
        Returns:
        the minimum key currently in the priority queue
        Throws:
        NoSuchElementException - if the priority queue is empty
      • delMin

        public int delMin()
        Deletes the minimum key Worst case is O(log(n))
        Returns:
        the index associated with the minimum key
        Throws:
        NoSuchElementException - if the priority queue is empty
      • keyOf

        public Key keyOf​(int i)
        Gets the key associated with index i Worst case is O(1)
        Parameters:
        i - an index
        Returns:
        the key associated with index i
        Throws:
        IllegalArgumentException - if the specified index is invalid
        IllegalArgumentException - if the index is not in the queue
      • changeKey

        public void changeKey​(int i,
                              Key key)
        Changes the key associated with index i to the given key Worst case is O(log(n))
        Parameters:
        i - an index
        key - the key to associate with i
        Throws:
        IllegalArgumentException - if the specified index is invalid
        IllegalArgumentException - if the index has no key associated with
      • decreaseKey

        public void decreaseKey​(int i,
                                Key key)
        Decreases the key associated with index i to the given key Worst case is O(log(n))
        Parameters:
        i - an index
        key - the key to associate with i
        Throws:
        IllegalArgumentException - if the specified index is invalid
        NoSuchElementException - if the index has no key associated with
        IllegalArgumentException - if the given key is greater than the current key
      • increaseKey

        public void increaseKey​(int i,
                                Key key)
        Increases the key associated with index i to the given key Worst case is O(log(n))
        Parameters:
        i - an index
        key - the key to associate with i
        Throws:
        IllegalArgumentException - if the specified index is invalid
        NoSuchElementException - if the index has no key associated with
        IllegalArgumentException - if the given key is lower than the current key
      • delete

        public void delete​(int i)
        Deletes the key associated the given index Worst case is O(log(n))
        Parameters:
        i - an index
        Throws:
        IllegalArgumentException - if the specified index is invalid
        NoSuchElementException - if the given index has no key associated with
      • iterator

        public Iterator<Integer> iterator()
        Gets an Iterator over the indexes in the priority queue in ascending order The Iterator does not implement the remove() method iterator() : Worst case is O(n) next() : Worst case is O(log(n)) hasNext() : Worst case is O(1)
        Specified by:
        iterator in interface Iterable<Key>
        Returns:
        an Iterator over the indexes in the priority queue in ascending order