Как реализовать медианную кучу

Question

Как и Max-heap и Min-heap, я хочу реализовать медианную кучу, чтобы отслеживать медиану заданного набора целых чисел. API должен иметь следующие три функции:

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

Я хочу использовать массив (а) реализацию для реализации кучи, где дети индекса массива K сохраняется в индексах массива 2 * к и 2 * к + 1. Для удобства массив начинает заполнять элементы из индекса 1. Это то, что у меня есть до сих пор: Медиана-куча будет иметь два целых числа, чтобы отслеживать количество вставленных до сих пор целых чисел, которые являются текущими медианными (gcm) и < текущая медиана (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. 

Аналогичным образом для другого случая. Я не могу придумать алгоритм, как тонуть и плавать. Я думаю, что следует принять во внимание, насколько близко число к медиане, так что-то вроде:

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

Я не могу придумать все решение, хотя.

Answer 1

Вам нужны две кучи: одна мини-куча и одна максимальная куча. Каждая куча содержит около половины данных. Каждый элемент в мини-куче больше или равен медиане, и каждый элемент в макс-куче меньше или равен медианной.

Когда мини-куча содержит еще один элемент, чем максимальная куча, медиана находится в верхней части мини-кучи. И когда максимальная куча содержит еще один элемент, чем минимальная куча, медиана находится в верхней части максимальной кучи.

Если обе кучи содержат одинаковое количество элементов, общее количество элементов равно. В этом случае вам нужно выбрать в соответствии с вашим определением медианы: а) среднее из двух средних элементов; б) большее из двух; c) меньшее; d) произвольно выбрать любую из двух ...

Каждый раз, когда вы вставляете, сравнивайте новый элемент с теми, что находятся в верхней части кучи, чтобы решить, где их вставить. Если новый элемент больше текущей медианы, он переходит в мини-кучу. Если он меньше, чем текущая медиана, он переходит в максимальную кучу. Тогда вам может понадобиться перебалансировка. Если размеры кучи отличаются более чем на один элемент, извлеките мин/макс из кучи с большим количеством элементов и вставьте их в другую кучу.

Чтобы построить медианную кучу для списка элементов, мы должны сначала использовать алгоритм линейного времени и найти медиану. Как только медиана известна, мы можем просто добавить элементы в Min-heap и Max-heap на основе медианного значения. Балансировка куч не требуется, потому что медиана будет разделять входной список элементов на равные половины.

Если вы извлечете элемент, вам может потребоваться скомпенсировать изменение размера, перемещая один элемент из одной кучи в другую. Таким образом, вы гарантируете, что во всех случаях обе кучи имеют одинаковый размер или отличаются только одним элементом.

Answer 2

Не идеально сбалансированное двоичное дерево поиска (BST) медианная куча? Это правда, что даже красно-черные BST не всегда идеально сбалансированы, но это может быть достаточно близко для ваших целей. И производительность log (n) гарантирована!

AVL trees более сбалансированы, чем красно-черные BST, поэтому они становятся еще ближе к истинной медианной куче.

Answer 3

Здесь представлено java-приложение MedianHeap, разработанное с помощью приведенного выше объяснения 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

Это реализация Scala, следуя идее comocomocomocomo выше.

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

Вот мой код, основанный на ответ, представленный 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); 
    } 
    } 
}