1
複数のデータを読み込み、それらのデータの中央値を計算するためにADTを作成する必要があります。 ADTは、MINヒープとMAXヒープで構成されています。 MinHeapクラスの数値は中央値よりも大きいか等しい。メジアンJavaの最大ヒープと最小ヒープ実装
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);
}
}
}
} `
MaxHeapクラスは、中央値より小さいか等しい数値をとります。
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);
}
}
} `
そして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");
}
}
}
}`
MinHeapは機能しますが、MaxHeapは数値を保存せず、0.0しか印刷しません。私は本当にここにこだわっている。