Come implementare un heap mediano

Question

Come un max-heap e un min-heap, voglio implementare un heap mediano per tenere traccia della mediana di un dato insieme di numeri interi. L'API dovrebbe avere le seguenti tre funzioni:

insert(int) // should take O(logN) 
int median() // will be the topmost element of the heap. O(1) 
int delmedian() // should take O(logN) 

voglio usare un array (a) attuazione per attuare mucchio dove i figli di indice di matrice k sono memorizzati negli indici di matrice 2 * k e 2 * k + 1. Per comodità, la matrice inizia a popolare gli elementi dall'indice 1. Questo è quello che ho finora: L'heap mediano avrà due numeri interi per tenere traccia del numero di numeri interi inseriti che sono> mediana corrente (gcm) e < mediana corrente (lcm).

if abs(gcm-lcm) >= 2 and gcm > lcm we need to swap a[1] with one of its children. 
The child chosen should be greater than a[1]. If both are greater, 
choose the smaller of two. 

Analogamente per l'altro caso. Non riesco a trovare un algoritmo su come affondare e nuotare elementi. Penso che dovrebbe prendere in considerazione quanto vicino il numero è per la mediana, in modo da qualcosa come:

private void swim(int k) { 
    while (k > 1 && absless(k, k/2)) { 
     exch(k, k/2); 
     k = k/2; 
    } 
} 

io non posso venire con l'intera soluzione però.

Answer 1

Sono necessari due heap: un min-heap e un max-heap. Ogni heap contiene circa la metà dei dati. Ogni elemento nel min-heap è maggiore o uguale alla mediana e ogni elemento nel max-heap è minore o uguale alla mediana.

Quando il min-heap contiene un elemento in più del max-heap, la mediana si trova nella parte superiore del min-heap. E quando il max-heap contiene un elemento in più rispetto al min-heap, la mediana è nella parte superiore del max-heap.

Quando entrambi gli heap contengono lo stesso numero di elementi, il numero totale di elementi è pari. In questo caso devi scegliere secondo la tua definizione di mediana: a) la media dei due elementi centrali; b) il maggiore dei due; c) il minore; d) scegliere a caso uno qualsiasi dei due ...

Ogni volta che si inserisce, confrontare il nuovo elemento con quelli nella parte superiore degli heap per decidere dove inserirlo. Se il nuovo elemento è maggiore della mediana corrente, passa al min-heap. Se è inferiore alla mediana corrente, passa all'heap massimo. Quindi potrebbe essere necessario riequilibrare. Se le dimensioni degli heap differiscono di più di un elemento, estrai il minimo/massimo dall'heap con più elementi e inseriscilo nell'altro heap.

Per costruire l'heap mediano per un elenco di elementi, dobbiamo prima utilizzare un algoritmo di tempo lineare e trovare la mediana. Una volta che la mediana è nota, possiamo semplicemente aggiungere elementi al Min-heap e al Max-heap in base al valore mediano. Il bilanciamento degli heap non è richiesto perché la mediana dividerà la lista di input degli elementi in parti uguali.

Se si estrae un elemento, potrebbe essere necessario compensare la modifica della dimensione spostando un elemento da un heap a un altro. In questo modo ti assicuri che, in ogni momento, entrambi gli heap hanno le stesse dimensioni o differiscono di un solo elemento.

Answer 2

Non è un albero di ricerca binario perfettamente bilanciato (BST) un cumulo mediano? È vero che anche i BST rosso-neri non sono sempre perfettamente bilanciati, ma potrebbe essere abbastanza vicino per i tuoi scopi. E log (n) le prestazioni sono garantite!

AVL trees sono più bilanciati rispetto ai BST rosso-neri in modo da avvicinarsi ancora di più ad essere un vero cumulo mediano.

Answer 3

Ecco una implementazione java di un MedianHeap, sviluppata con l'aiuto della spiegazione sopra comocomocomocomo.

import java.util.Arrays; 
import java.util.Comparator; 
import java.util.PriorityQueue; 
import java.util.Scanner; 

/** 
* 
* @author BatmanLost 
*/ 
public class MedianHeap { 

    //stores all the numbers less than the current median in a maxheap, i.e median is the maximum, at the root 
    private PriorityQueue<Integer> maxheap; 
    //stores all the numbers greater than the current median in a minheap, i.e median is the minimum, at the root 
    private PriorityQueue<Integer> minheap; 

    //comparators for PriorityQueue 
    private static final maxHeapComparator myMaxHeapComparator = new maxHeapComparator(); 
    private static final minHeapComparator myMinHeapComparator = new minHeapComparator(); 

    /** 
    * Comparator for the minHeap, smallest number has the highest priority, natural ordering 
    */ 
    private static class minHeapComparator implements Comparator<Integer>{ 
     @Override 
     public int compare(Integer i, Integer j) { 
      return i>j ? 1 : i==j ? 0 : -1 ; 
     } 
    } 

    /** 
    * Comparator for the maxHeap, largest number has the highest priority 
    */ 
    private static class maxHeapComparator implements Comparator<Integer>{ 
     // opposite to minHeapComparator, invert the return values 
     @Override 
     public int compare(Integer i, Integer j) { 
      return i>j ? -1 : i==j ? 0 : 1 ; 
     } 
    } 

    /** 
    * Constructor for a MedianHeap, to dynamically generate median. 
    */ 
    public MedianHeap(){ 
     // initialize maxheap and minheap with appropriate comparators 
     maxheap = new PriorityQueue<Integer>(11,myMaxHeapComparator); 
     minheap = new PriorityQueue<Integer>(11,myMinHeapComparator); 
    } 

    /** 
    * Returns empty if no median i.e, no input 
    * @return 
    */ 
    private boolean isEmpty(){ 
     return maxheap.size() == 0 && minheap.size() == 0 ; 
    } 

    /** 
    * Inserts into MedianHeap to update the median accordingly 
    * @param n 
    */ 
    public void insert(int n){ 
     // initialize if empty 
     if(isEmpty()){ minheap.add(n);} 
     else{ 
      //add to the appropriate heap 
      // if n is less than or equal to current median, add to maxheap 
      if(Double.compare(n, median()) <= 0){maxheap.add(n);} 
      // if n is greater than current median, add to min heap 
      else{minheap.add(n);} 
     } 
     // fix the chaos, if any imbalance occurs in the heap sizes 
     //i.e, absolute difference of sizes is greater than one. 
     fixChaos(); 
    } 

    /** 
    * Re-balances the heap sizes 
    */ 
    private void fixChaos(){ 
     //if sizes of heaps differ by 2, then it's a chaos, since median must be the middle element 
     if(Math.abs(maxheap.size() - minheap.size()) > 1){ 
      //check which one is the culprit and take action by kicking out the root from culprit into victim 
      if(maxheap.size() > minheap.size()){ 
       minheap.add(maxheap.poll()); 
      } 
      else{ maxheap.add(minheap.poll());} 
     } 
    } 
    /** 
    * returns the median of the numbers encountered so far 
    * @return 
    */ 
    public double median(){ 
     //if total size(no. of elements entered) is even, then median iss the average of the 2 middle elements 
     //i.e, average of the root's of the heaps. 
     if(maxheap.size() == minheap.size()) { 
      return ((double)maxheap.peek() + (double)minheap.peek())/2 ; 
     } 
     //else median is middle element, i.e, root of the heap with one element more 
     else if (maxheap.size() > minheap.size()){ return (double)maxheap.peek();} 
     else{ return (double)minheap.peek();} 

    } 
    /** 
    * String representation of the numbers and median 
    * @return 
    */ 
    public String toString(){ 
     StringBuilder sb = new StringBuilder(); 
     sb.append("\n Median for the numbers : "); 
     for(int i: maxheap){sb.append(" "+i); } 
     for(int i: minheap){sb.append(" "+i); } 
     sb.append(" is " + median()+"\n"); 
     return sb.toString(); 
    } 

    /** 
    * Adds all the array elements and returns the median. 
    * @param array 
    * @return 
    */ 
    public double addArray(int[] array){ 
     for(int i=0; i<array.length ;i++){ 
      insert(array[i]); 
     } 
     return median(); 
    } 

    /** 
    * Just a test 
    * @param N 
    */ 
    public void test(int N){ 
     int[] array = InputGenerator.randomArray(N); 
     System.out.println("Input array: \n"+Arrays.toString(array)); 
     addArray(array); 
     System.out.println("Computed Median is :" + median()); 
     Arrays.sort(array); 
     System.out.println("Sorted array: \n"+Arrays.toString(array)); 
     if(N%2==0){ System.out.println("Calculated Median is :" + (array[N/2] + array[(N/2)-1])/2.0);} 
     else{System.out.println("Calculated Median is :" + array[N/2] +"\n");} 
    } 

    /** 
    * Another testing utility 
    */ 
    public void printInternal(){ 
     System.out.println("Less than median, max heap:" + maxheap); 
     System.out.println("Greater than median, min heap:" + minheap); 
    } 

    //Inner class to generate input for basic testing 
    private static class InputGenerator { 

     public static int[] orderedArray(int N){ 
      int[] array = new int[N]; 
      for(int i=0; i<N; i++){ 
       array[i] = i; 
      } 
      return array; 
     } 

     public static int[] randomArray(int N){ 
      int[] array = new int[N]; 
      for(int i=0; i<N; i++){ 
       array[i] = (int)(Math.random()*N*N); 
      } 
      return array; 
     } 

     public static int readInt(String s){ 
      System.out.println(s); 
      Scanner sc = new Scanner(System.in); 
      return sc.nextInt(); 
     } 
    } 

    public static void main(String[] args){ 
     System.out.println("You got to stop the program MANUALLY!!");   
     while(true){ 
      MedianHeap testObj = new MedianHeap(); 
      testObj.test(InputGenerator.readInt("Enter size of the array:")); 
      System.out.println(testObj); 
     } 
    } 
} 

Answer 4

Ecco un'implementazione Scala, seguendo l'idea del comocomocomocomo sopra.

class MedianHeap(val capacity:Int) { 
    private val minHeap = new PriorityQueue[Int](capacity/2) 
    private val maxHeap = new PriorityQueue[Int](capacity/2, new Comparator[Int] { 
     override def compare(o1: Int, o2: Int): Int = Integer.compare(o2, o1) 
    }) 

    def add(x: Int): Unit = { 
     if (x > median) { 
     minHeap.add(x) 
     } else { 
     maxHeap.add(x) 
     } 

     // Re-balance the heaps. 
     if (minHeap.size - maxHeap.size > 1) { 
     maxHeap.add(minHeap.poll()) 
     } 
     if (maxHeap.size - minHeap.size > 1) { 
     minHeap.add(maxHeap.poll) 
     } 
    } 

    def median: Double = { 
     if (minHeap.isEmpty && maxHeap.isEmpty) 
     return Int.MinValue 
     if (minHeap.size == maxHeap.size) { 
     return (minHeap.peek+ maxHeap.peek)/2.0 
     } 
     if (minHeap.size > maxHeap.size) { 
     return minHeap.peek() 
     } 
     maxHeap.peek 
    } 
    } 

Answer 5

Ecco il mio codice in base alla risposta fornita da comocomocomocomo:

import java.util.PriorityQueue; 

public class Median { 
private PriorityQueue<Integer> minHeap = 
    new PriorityQueue<Integer>(); 
private PriorityQueue<Integer> maxHeap = 
    new PriorityQueue<Integer>((o1,o2)-> o2-o1); 

public float median() { 
    int minSize = minHeap.size(); 
    int maxSize = maxHeap.size(); 
    if (minSize == 0 && maxSize == 0) { 
     return 0; 
    } 
    if (minSize > maxSize) { 
     return minHeap.peek(); 
    }if (minSize < maxSize) { 
     return maxHeap.peek(); 
    } 
    return (minHeap.peek()+maxHeap.peek())/2F; 
} 

public void insert(int element) { 
    float median = median(); 
    if (element > median) { 
     minHeap.offer(element); 
    } else { 
     maxHeap.offer(element); 
    } 
    balanceHeap(); 
} 

private void balanceHeap() { 
    int minSize = minHeap.size(); 
    int maxSize = maxHeap.size(); 
    int tmp = 0; 
    if (minSize > maxSize + 1) { 
     tmp = minHeap.poll(); 
     maxHeap.offer(tmp); 
    } 
    if (maxSize > minSize + 1) { 
     tmp = maxHeap.poll(); 
     minHeap.offer(tmp); 
    } 
    } 
}