Max Heap und Min Heap-Implementierung für den Median Java

Question

Ich muss einen ADT erstellen, um eine Anzahl von Daten zu lesen und den Median dieser Daten zu berechnen. Der ADT besteht aus einem MIN- und einem MAX-Heap. Die Klasse MinHeap nimmt die Zahlenwerte oder gleich dem Median.

public class MinHeap {

public double[] data; 
public int Size; 

public MinHeap(int size) { 
     data = new double[size]; 
     Size = 0; 
} 

public double getMinimum(){ 
    return this.data[0]; 
} 

public boolean isEmpty() { 
     return (Size == 0); 
} 

private int getParentIndex(int nodeIndex) { 
    return (nodeIndex - 1)/2; 
} 

public void insertu(double value) throws Exception { 
    if (Size == data.length) 
      throw new Exception("Heap's underlying storage is overflow"); 
    else { 
      Size++; 
      data[Size - 1] = value; 
      siftUp(Size - 1); 
    } 
} 
public void siftUp(int nodeIndex) { 
    int parentIndex; 
    double tmp; 
    if (nodeIndex != 0) { 
      parentIndex = getParentIndex(nodeIndex); 
      if (data[parentIndex] > data[nodeIndex]) { 
       tmp = data[parentIndex]; 
       data[parentIndex] = data[nodeIndex]; 
       data[nodeIndex] = tmp; 
       siftUp(parentIndex); 
      } 
    } 
} 

} `

Die MaxHeap Klasse nimmt die Zahlen, die kleiner oder gleich als der Median.

public class MaxHeap{

public double [] _Heap; 
public int _size; 
public int tam=0; 

public MaxHeap (int a){ 

    _Heap = new double[a]; 
    _size = _Heap.length; 
    for (int i = _Heap.length/2 ; i >=0 ; i--) { 
     tam++; 
     maxHeapify(i); 
    } 
} 

private int parent(int pos) 
{ return pos/2; } 

private int leftChild(int pos) 
{ return (2 * pos); } 

private int rightChild(int pos) 
{ return (2 * pos) + 1; } 

private void swap(int fpos,int spos) { 
    double tmp; 
    tmp = _Heap[fpos]; 
    _Heap[fpos] = _Heap[spos]; 
    _Heap[spos] = tmp; 
} 

private void maxHeapify (int i) { 
    int l = leftChild(i), r = rightChild(i), largest; 
    if(l < _size && _Heap[l] > _Heap[i]) { 
     tam+=2; 
     largest = l; 
     } 
     else largest = i; 
    if(r < _size && _Heap[r] > _Heap[largest]) { 
     largest = r; 
     tam+=2; } 
    if (largest != i) { 
     tam++; 
     swap(i, largest); 
     maxHeapify (largest); } 
    } 

protected boolean isEmpty() { return _size == 0; } 

protected void deleteMax() { 
    if (_size > 1) { 
     tam++; 
     maxHeapify(0); 
     double max = _Heap[0]; 
     _size--; 
     swap(0, _size); 
     maxHeapify(0); } 
    else _size = 0;  
} 

protected double extractMax() { 
    maxHeapify(0); 
    return _Heap[0]; 
} 
public void insert(double element) 
{ 
    _Heap[++tam] = element; 
    int current = tam; 

    while(_Heap[current] > _Heap[parent(current)]) 
    { 
     swap(current,parent(current)); 
     current = parent(current); 
    } 
} 

} `

Und der ADT:

`import java.util.InputMismatchException;` 
`import java.util.Scanner;` 

public class ColaPrioridadMediana {

private MinHeap MIN; 
private MaxHeap MAX; 
private int size; 

public ColaPrioridadMediana(int cap) { 
    if (cap%2==0){ 
     MIN = new MinHeap(cap/2); 
     MAX = new MaxHeap(cap/2); 
    } 
    else{ 
     MIN = new MinHeap((cap+1)/2); 
     MAX = new MaxHeap((cap+1)/2); 
     } 
    size = MAX.counter + MIN.Size; 
} 

public void insertar(double x) throws Exception{ 
    if (x <= MAX.extractMax()){ 
     if (MAX.counter > MIN.Size){ 
      double d = MAX.extractMax(); 
      MIN.insertu(d); 
      MAX.insert(x); 
     } 
     else{ 
      MAX.insert(x); 
     } 
    } 
    else{ 
     if (MIN.Size > MAX.counter){ 
      double d = MIN.getMinimum(); 
      MAX.insert(d); 
      MIN.data[0] = x; 
      MIN.siftUp(1); 
     } 
     else{ 
      MIN.insertu(x); 
     } 
    } 
} 

public int getSize(){ 
    return size; 
} 

public double getMediana() throws Exception{ 
    if(MAX.counter==MIN.Size){return ((MAX.extractMax()+MIN.getMinimum())/2);} 
    else{ 
     if (MAX.counter<MIN.Size){return MIN.getMinimum();} 
     else{return MAX.extractMax();} 
    } 
} 

public static void main(String[] args) throws NumberFormatException, Exception{ 
    @SuppressWarnings("resource") 
    Scanner num=new Scanner(System.in); 
    ColaPrioridadMediana allNumbers=new ColaPrioridadMediana(10); 
    while(true){ 
     System.out.print("Number:"); 
     try{ 
      String number=num.nextLine(); 
      double d; 
      if(!number.isEmpty()){ 
       allNumbers.insertar(Double.parseDouble(number)); 
      }else{ 
       d = allNumbers.getMediana(); 

      System.out.println("The result is " + d); 
      System.out.println(allNumbers.MAX.extractMax()); 
      System.out.println(allNumbers.MIN.getMinimum()); 
      System.out.println(allNumbers.MAX.counter); 
      System.out.println(allNumbers.MIN.Size); 
      for (int i=0;i<allNumbers.MAX._Heap.length;i++){ 
      System.out.println(allNumbers.MAX._Heap[i]); 
      System.out.println(allNumbers.MIN.data[i]); 
      } 

      System.exit(0); 
      } 
     } 
     catch(InputMismatchException e){ 
      System.out.println("Not number"); 
      } 
     } 
    } 

}`

Der MinHeap funktioniert, aber der MaxHeap speichert keine Zahlen und druckt nur 0.0. Ich bin wirklich hier drin.

Answer 1

In Java ist die Verwendung der Java-Standardklasse PriorityQueue zum Simulieren von Max-Min-Heap keine schlechte Idee. Es wird die Codierung signifikant reduzieren.

public class MaxMinHeap{ 
PriorityQueue<Integer> minHeap = new PriorityQueue<>(); 
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((x,y)->(y-x)); 

private void add(int val) { 
    if (maxHeap.size() == 0) { 
     maxHeap.add(val); 
    } else { 
     int maxTop = maxHeap.peek(); 
     if (val <= maxTop) { 
      maxHeap.add(val); 
     } else { 
      minHeap.add(val); 
     } 
     if (maxHeap.size() - minHeap.size() > 1) { 
      minHeap.add(maxHeap.poll()); 
     } else if (minHeap.size() - maxHeap.size() > 1) { 
      maxHeap.add(minHeap.poll()); 
     } 
    } 
} 

private double findMedian() { 
    if(maxHeap.size() > minHeap.size()) { 
     return maxHeap.peek(); 
    }else if(maxHeap.size() == minHeap.size()) { 
     return ((double) maxHeap.peek() + minHeap.peek())/2; 
    }else { 
     return minHeap.peek(); 
    } 
} 

}