/
NikolayIvkin
/
TheAlgorithms
Обзор
Документация
Войти
/
NikolayIvkin
/
TheAlgorithms
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
src/main/java/com/thealgorithms/misc/MedianOfRunningArray.java
53 строки
2 KB
Ansh Shah
Make `MedianOfRunningArray` Generic (#4392)
24 сен 2023, 08:50
Не верифицирован
24 сен 2023, 08:50
d3a3213
Код
Авторство
О чём код?
package com.thealgorithms.misc; import java.util.Collections; import java.util.PriorityQueue; /** * @author shrutisheoran */ public abstract class MedianOfRunningArray<T extends Number & Comparable<T>> { private PriorityQueue<T> maxHeap; private PriorityQueue<T> minHeap; // Constructor public MedianOfRunningArray() { this.maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // Max Heap this.minHeap = new PriorityQueue<>(); // Min Heap } /* Inserting lower half of array to max Heap and upper half to min heap */ public void insert(final T e) { if (!minHeap.isEmpty() && e.compareTo(minHeap.peek()) < 0) { maxHeap.offer(e); if (maxHeap.size() > minHeap.size() + 1) { minHeap.offer(maxHeap.poll()); } } else { minHeap.offer(e); if (minHeap.size() > maxHeap.size() + 1) { maxHeap.offer(minHeap.poll()); } } } /* Returns median at any given point */ public T median() { if (maxHeap.isEmpty() && minHeap.isEmpty()) { throw new IllegalArgumentException("Enter at least 1 element, Median of empty list is not defined!"); } else if (maxHeap.size() == minHeap.size()) { T maxHeapTop = maxHeap.peek(); T minHeapTop = minHeap.peek(); return calculateAverage(maxHeapTop, minHeapTop); } return maxHeap.size() > minHeap.size() ? maxHeap.peek() : minHeap.peek(); } public abstract T calculateAverage(T a, T b); }