如何實現中間堆

Question

像最大堆和最小堆一樣，我想實現一箇中間堆來跟蹤給定整數集的中值。該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 * 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; 
    } 
} 

我不能拿出完整的解決方案，但。

Answer 1

你需要兩堆：一個分堆和一個最大堆。每個堆包含大約一半的數據。 min-heap中的每個元素大於或等於中位數，並且max-heap中的每個元素都小於或等於中位數。

當min-heap包含比max-heap更多的元素時，中位數位於min-heap的頂部。當最大堆包含比最小堆多一個元素時，中位數位於最大堆頂部。

當兩個堆包含相同數量的元素時，元素的總數是偶數。 在這種情況下，您必須根據您的中位數的定義進行選擇：a）兩個中間元素的平均值; b）兩者中較大的一個; 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); 
    } 
    } 
}