0
popMin 및 popMax 메서드를 모두 포함하는 대기열 클래스를 구현하고 있습니다. 지금까지 두 개의 우선 순위 대기열을 사용하여 작업을 수행했습니다. 그러나 제거가 log (n) 시간 일지라도 다른 대기열에서도 선형을 제거해야합니다. 바이너리 힙을 사용하여 이중 종료 우선 순위 큐를 구현할 수 있다는 것을 알고 있지만, 빌드하는 데 선형 시간이 걸린다 고 잘못 생각하지 않는다면? 더 효율적으로 할 수있는 방법이 있습니까? Java 라이브러리 클래스도 사용할 수 있습니다.min-max 대기열 클래스에서 min 및 max를 선형 시간보다 짧게 삭제합니다.
static class MinMaxQueue {
PriorityQueue<String> MinQueue = new PriorityQueue<String>();
PriorityQueue<String> MaxQueue = new PriorityQueue<String>(Collections.reverseOrder());
void push(String val) {
MinQueue.add(val);
MaxQueue.add(val);
}
String popMin() {
MaxQueue.remove(MinQueue.peek());
return MinQueue.remove();
}
String popMax() {
MinQueue.remove(MaxQueue.peek());
return MaxQueue.remove();
}
int size() {
return MinQueue.size();
}
}