# Java Using Two PriorityQueues To Conquer

• Just maintain two priority queues maxHeap and minHeap, maxHeap to store the less half, and minHeap larger half, the median should be easily got maxHeap.peak if k % 2 == 1 else average of maxHeap.peek() and minHeap.peek().

``````import java.util.Collections;
import java.util.PriorityQueue;
public class Solution {
public double[] medianSlidingWindow(int[] nums, int k) {
if(nums==null || nums.length==0 || k==0) return new double[0];
double[] res = new double[nums.length - k + 1];
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, Collections.reverseOrder());
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(k);
int idx = 0;
for(int i=0; i<nums.length; i++){
if(maxHeap.isEmpty() || nums[i]<maxHeap.peek()){
}else{
}

if(minHeap.size() > maxHeap.size()){
}

if(maxHeap.size() > minHeap.size()+1){
}

if(i>=k-1){
if (k % 2 == 1) {
res[idx] = (1.0 * maxHeap.peek());
}
else {
res[idx] = (maxHeap.peek()/2.0 + minHeap.peek()  / 2.0);
}
idx += 1;
int toRemove = nums[i-k+1];
if(toRemove<=maxHeap.peek()){
maxHeap.remove(toRemove);
}else{
minHeap.remove(toRemove);
}
if(minHeap.size() > maxHeap.size()){
}
if(maxHeap.size() > minHeap.size()+1){
}
}
}

return res;
}
}
``````

• http://stackoverflow.com/questions/12719066/priority-queue-remove-complexity-time

Java's PriorityQueue remove(Object o) method complexity is O(n) not O(logn)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.