Soluzione


ExtendedHeap

Tutte le operazioni si possono implementare con costo , utilizzando un max-heap per la rappresentazione.

Per implementare la getSecond è sufficiente estrarre temporaneamente il primo elemento, leggere il secondo elemento (nuovo primo) e reinserire il primo elemento.

Analogamente, per implementare la removeSecond è sufficiente estrarre temporaneamente il primo elemento, rimuovere il secondo elemento (nuovo primo) e reinserire il primo elemento.

public class ExtendedHeap extends MaxHeap {
  
  public int getSecond() {
    int first=deleteFirst();
    int second=getFirst();
    insert(first);
    return second;
  }
  
  public int deleteSecond() {
    int first=deleteFirst();
    int second=deleteFirst();
    insert(first);
    return second;
  }
 
}

MinHeap

E’ sufficiente invertire il segno di ogni intero prima di inserirlo nel max-heap; simmetricamente, prima di restituire un elemento letto dal max-heap invertiremo nuovamente il suo segno.

public class MinHeap {
 
  private MaxHeap h;
  
  public MinHeap() {
    h=new MaxHeap();
  }
  
  public void insert(int el) {
    h.insert(-el);
  }
  
  public int getFirst() {
    return -h.getFirst();
  }
  
  public int deleteFirst() {
    return -h.deleteFirst();
  }
  
  public boolean isEmpty() {
    return h.isEmpty();
  }
  
  public boolean isFull() {
    return h.isFull();
  }
  
  public int getSize() {
    return h.getSize();
  }
  
}

Se le chiavi sono di tipo Comparable si può definire un wrapper per “cambiare il verso della disuguaglianza” del metodo compareTo:

class MinHeapComparableWrapper implements Comparable {
 
	public Comparable comp; //Questo è l'oggetto incapsulato
	
	public MinHeapComparableWrapper(Comparable el)	{
		comp=el; 
	}
	
	public int compareTo(Object o) {
		MinHeapComparableWrapper w=(MinHeapComparableWrapper) o;
		return -comp.compareTo(w.comp); //Questa è l'istruzione che inverte la disuguaglianza!
	}
 
}

A questo punto è sufficiente che il min-heap wrappi gli oggetti ricevuti prima di inserirli nel max-heap. Simmetricamente, ogni volta che il min-heap legge un oggetto dal max-heap lo deve “swrappare”.

public class MinHeapComparable {
 
	private MaxHeapComparable h;
	
	public MinHeapComparable() {
		h=new MaxHeapComparable();
	}
	
	public Comparable insert(Comparable el) {
		if(h.isFull())
			return null;
		h.insert(new MinHeapComparableWrapper(el));
		return el;
	}
	
	public Comparable getFirst() {
		MinHeapComparableWrapper w=(MinHeapComparableWrapper) h.getFirst();
		if(w==null) //Empty heap
			return null;
		return w.comp;
	}
	
	public Comparable deleteFirst() {
		MinHeapComparableWrapper w=(MinHeapComparableWrapper) h.deleteFirst();
		if(w==null) //Empty heap
			return null;
		return w.comp;
	}
	
	public boolean isEmpty() {
		return h.isEmpty();
	}
	
	public boolean isFull() {
		return h.isFull();
	}
	
	public int getSize() {
		return h.getSize();
	}
	
}

MedianHeap

Usiamo un max-heap e un min-heap disposti “a clessidra” per rappresentare il median-heap (vedi figura). contiene tutti gli elementi minori o uguali al mediano; contiene tutti gli elementi maggiori del mediano. Dunque la seguente proprietà P è sempre vera:

oppure

(a seconda che il numero totale di elementi sia pari o dispari)

Il mediano può essere trovato con costo leggendo il massimo di . Per inserire un intero è sufficiente

  1. confrontare con il mediano attuale, per determinare in quale dei due heap bisogna inserire l’elemento;
  2. ribilanciare gli heap (spostando al più un elemento) in modo che la proprietà P sia mantenuta.

Discorso analogo vale per la rimozione del mediano: dopo averlo rimosso è necessario ribilanciare gli heap.

public class MedianHeap {
  
  public MaxHeap lowerHeap;
  public MinHeap upperHeap;
  
  public MedianHeap() {
    lowerHeap=new MaxHeap();
    upperHeap=new MinHeap();
  }
  
  public void insert(int c) {
    if(!lowerHeap.isEmpty()) {
      int med=getMedian();
      if(c <= med)
        if(!lowerHeap.isFull())
          lowerHeap.insert(c);
        else {
          System.err.println("Full Heap");
        }
      else
        if(!upperHeap.isFull())
          upperHeap.insert(c);
        else {
          System.err.println("Full Heap");
        }
      reBalance();
    } else { //Empty heap
      lowerHeap.insert(c);
    }
  }
  
  public int getMedian() {
    return lowerHeap.getFirst();
  }
  
  public int deleteMedian() {
    int c=lowerHeap.deleteFirst();
    reBalance();
    return c;
  }
  
  private void reBalance() {
    if(upperHeap.getSize()==lowerHeap.getSize()+1)
      lowerHeap.insert(upperHeap.deleteFirst());
    if(lowerHeap.getSize()==upperHeap.getSize()+2)
      upperHeap.insert(lowerHeap.deleteFirst());
  }
  
}