Подтвердить что ты не робот

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

Как и Max-heap и Min-heap, я хочу реализовать Median-кучу, чтобы отслеживать медиану заданного набора целых чисел. 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)

Я хочу использовать реализацию array (a) для реализации кучи, где дети индекса массива k хранятся в индексах массива 2 * k и 2 * k + 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;
    }
}

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

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

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

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

Ответ 2

Вот 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 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 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);
        }
    }
}

Ответ 3

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

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

Ответ 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
    }
  }

Ответ 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);
    }
  }
}