Generic Median Heap using PriorityQueues

Question

I've implemented a generic data structure to keep track of the median in a streaming list of numbers. I was hoping to gather the community's feedback on code style and taste.

package ad.collections;
import sun.reflect.generics.reflectiveObjects.NotImplementedException;
import java.util.*;
/**
 * Created by adhulipa on 10/28/16.
 */
public class MedianHeap<E extends Number & Comparable> implements Queue<Number> {
 private enum QueueSize { BIGGER, SMALLER };
 private PriorityQueue<E> lowers;
 private PriorityQueue<E> uppers;
 public MedianHeap() {
 super();
 lowers = new PriorityQueue<E>(Collections.reverseOrder());
 uppers = new PriorityQueue<E>();
 }
 @Override
 public boolean offer(Number number) {
 boolean offered;
 if ( !lowers.isEmpty() && isLessThan(number, lowers.peek())) {
 // Cast number to actual type E
 offered = lowers.offer( (E) number);
 } else if ( !uppers.isEmpty() && isGreaterThan(number, uppers.peek())) {
 offered = uppers.offer( (E) number);
 } else {
 // Otherwise, add new number to smaller of the two queues
 Queue smallerQueue = selectQueue(QueueSize.SMALLER);
 offered = smallerQueue.offer(number);
 }
 rebalance();
 return offered;
 }
 @Override
 public Double peek() {
 return this.median(false);
 }
 @Override
 public int size() {
 return lowers.size() + uppers.size();
 }
 @Override
 public boolean isEmpty() {
 return lowers.isEmpty() && uppers.isEmpty();
 }
 @Override
 public Double poll() {
 Double median = this.median(true);
 rebalance();
 return median;
 }
 private void rebalance() {
 while ( Math.abs(lowers.size() - uppers.size()) > 1 ) {
 Queue bigger = selectQueue(QueueSize.BIGGER);
 Queue smaller = selectQueue(QueueSize.SMALLER);
 smaller.offer(bigger.poll());
 }
 }
 private Double median(boolean isPoll) {
 Double median = null;
 if ( queueSizesEqual() ) {
 median = (lowers.peek().doubleValue() + uppers.peek().doubleValue()) / 2;
 if (isPoll) {
 lowers.poll();
 uppers.poll();
 }
 } else { // peek() bigger queue
 Queue bigger = selectQueue(QueueSize.BIGGER);
 Number medianNumber = (Number) bigger.peek();
 median = medianNumber.doubleValue();
 if (isPoll) {
 bigger.poll();
 }
 }
 return median;
 }
 private boolean queueSizesEqual() {
 return lowers.size() == uppers.size();
 }
 private Queue selectQueue(QueueSize which) {
 Queue smaller = lowers;
 Queue bigger = uppers;
 Queue answer;
 if (uppers.size() < lowers.size()) {
 smaller = uppers;
 bigger = lowers;
 } else if (uppers.size() > lowers.size() ){
 bigger = uppers;
 smaller = lowers;
 }
 switch (which ){
 case BIGGER:
 answer = bigger;
 break;
 case SMALLER:
 answer = smaller;
 break;
 default:
 answer = smaller;
 }
 return answer;
 }
 private boolean isLessThan(Number newItem, E currentMin) {
 E item = (E) newItem;
 return item.compareTo(currentMin) < 0;
 }
 private boolean isGreaterThan(Number newItem, E currentMax) {
 E item = (E) newItem;
 return item.compareTo(currentMax) > 0;
 }
 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 Not Implemented methods below
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 @Override
 public boolean remove(Object o) throws NotImplementedException { throw new NotImplementedException(); }
 @Override
 public boolean contains(Object o) {
 throw new NotImplementedException();
 }
 @Override
 public Iterator<Number> iterator() {
 throw new NotImplementedException();
 }
 @Override
 public Object[] toArray() {
 throw new NotImplementedException();
 }
 @Override
 public <T> T[] toArray(T[] a) {
 throw new NotImplementedException();
 }
 @Override
 public boolean add(Number i) throws NotImplementedException {
 throw new NotImplementedException();
 }
 @Override
 public Number remove() {
 throw new NotImplementedException();
 }
 @Override
 public boolean containsAll(Collection<?> c) {
 throw new NotImplementedException();
 }
 @Override
 public boolean addAll(Collection<? extends Number> c) {
 throw new NotImplementedException();
 }
 @Override
 public boolean removeAll(Collection<?> c) {
 throw new NotImplementedException();
 }
 @Override
 public boolean retainAll(Collection<?> c) {
 throw new NotImplementedException();
 }
 @Override
 public void clear() {
 throw new NotImplementedException();
 }
 @Override
 public Number element() {
 throw new NotImplementedException();
 }
}

Answer 1

A few of my personal pet hates:

• You should avoid boxed Doubles as much as possible. If you are looking for a double that you can set to null, you should consider using the OptionalDouble instead.
• You are violating the contract of the Queue interface. Notably the poll method, which is really only supposed to remove one number from the queue (yours can remove two in some circumstances), and can return an item that was never put in the queue in the first place.
• The number of NotImplementedExceptions you are throwing around tells me that the Queue interface is not the right one to implement for this purpose. (Frankly, that type of exception should not exist, as it only encourages bad practice.)

• cafed00d: 1. Thank you for the note on OptionalDouble -- 2. & 3. That makes sense. This is not a Queue. (i.e. violates the "is-a" rule) What I'm really looking for is a Heap interface. Would you say that it is better to define a Heap interface myself with only the methods (offer, poll, peek, remove, isEmpty & size) ? My MedianHeap can implement this new Heap interface.
• Joe C: Java does have a heap interface (albeit by a different name - PriorityQueue. That said, I don't think it's appropriate for what you're trying to do, for exactly the same reasons as Queue is not appropriate. I would consider designing an interface that describes only what you need method-wise (why do you need a poll method, for example?).
• cafed00d: That sounds good. I'll define my own interface for this problem. I defined the poll method because I was implementing the Queue interface. I thought this data structure as being-a-heap from the get-go. But, now I see that poll is unnecessary. I would instead have a remove(Number element) method which will remove a specific element from the array. Users could also use this method to remove the median if they wished to do so.