Package src.maxpq

Class MaxPQ<T extends Comparable<T>>

java.lang.Object
src.maxpq.MaxPQ<T>

public class MaxPQ<T extends Comparable<T>> extends Object
Maximum Priority Queue
Coda a priorità massima
Version:
1.0.0
Author:
Lorenzo Radice
  • Constructor Summary

    Constructors
    Constructor
    Description
    MaxPQ(int dim)
    Costruttore della coda a priorità massima.
  • Method Summary

    Modifier and Type
    Method
    Description
    void
    buildBU(T[] a)
    Costruzione Bottom Up.
    Elimina l'elemento della coda con la priorità più alta e lo ritorna.
    void
    insert(T v)
    Inserisce l'oggetto nello primo spazio vuoto della coda e la riordina.
    boolean
    Controlla se la coda è vuota
    Legge l'elemento della coda con maggiore priorità.
    int
    Ritorna la dimensione della coda
    T[]
    Ritorna l'array della coda riordinata e svuotandola.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Constructor Details

    • MaxPQ

      public MaxPQ(int dim)
      Costruttore della coda a priorità massima.
      Parameters:
      dim - lunghezza coda
  • Method Details

    • isEmpty

      public boolean isEmpty()
      Controlla se la coda è vuota
      Returns:
      true se la coda è vuota
    • size

      public int size()
      Ritorna la dimensione della coda
      Returns:
      lunghezza della coda
    • insert

      public void insert(T v)
      Inserisce l'oggetto nello primo spazio vuoto della coda e la riordina.

      Complessità
      Caso migliore
      T = O(1)
      S = O(1)
      Caso peggiore
      T = O(log(n))
      S = O(n)
      Parameters:
      v - oggetto da inserire
    • delete

      public T delete()
      Elimina l'elemento della coda con la priorità più alta e lo ritorna.

      Complessità
      Caso migliore
      T = O(1)
      Caso peggiore
      T = O(log(n))
      Returns:
      primo elemento della coda
    • buildBU

      public void buildBU(T[] a)
      Costruzione Bottom Up.

      Complessità
      T = θ(n) Non stabile
      Parameters:
      a - array da riordinare
    • sort

      public T[] sort()
      Ritorna l'array della coda riordinata e svuotandola.
      Complessità
      T = O(log(n))
      Returns:
      array ordinato
    • read

      public T read()
      Legge l'elemento della coda con maggiore priorità.
      Complessità
      T = O(1)
      Returns:
      primo elemento