Java & Android
Java PriorityQueue 활용
그레이트쪼
2017. 1. 10. 20:01
- Heap 자료구조를 구현함
- 주요 메소드
- http://developer.android.com/reference/java/util/PriorityQueue.html
- PriorityQueue(), PriorityQueue(int initialCapacity, Comparator<? super E> comparator) - 생성자
- Boolean add(E o) - 요소를 집어넣는 메소드, 내부적으로 offer(E o)를 호출하는데 offer(E o)와 동일하다고 보면 된다.
- E poll() - 큐에서 top priority 요소를 꺼내는 메소드
- E peek() - 큐에서 top priority 요소를 꺼내지는 않고 보는 메소드
- 그 밖에 size(), remove(Object o), clear() 등도 있다.
- PriorityQueue를 이용하여 min heap과 max heap을 만드는 방법
- 기본 생성자 - PriorityQueue() - 를 사용하면 min heap이 되고 역순으로 비교하는 comparator를 사용하면 max heap이 된다.
- 특별히 Collections.reverseOrder()가 제공된다. 대신 custom comparator를 사용할 수 있는 생성자에선 initial capacity도 함께 지정할 수 밖에 없다.
- Example: min heap과 max heap을 유지하면서 median값을 O(log n)에 제공하는 메소드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(10, Collections.reverseOrder()); // 하위 수는 maxHeap에, 상위 수는 minHeap에 넣는다 // maxHeap의 개수가 minHeap과 같거나 하나 많도록 유지한다 public void addNumber(int number) { if (maxHeap.size() == minHeap.size()) { if ((minHeap.peek() != null) && number > minHeap.peek()) { maxHeap.offer(minHeap.poll()); // move the smallest of minHeap to maxHeap minHeap.offer(number); } else { maxHeap.offer(number); } } else { if (number < maxHeap.peek()) { minHeap.offer(maxHeap.poll()); maxHeap.offer(number); } else { minHeap.offer(number); } } } public double getMedian() { if (maxHeap.isEmpty()) return 0d; // error if (maxHeap.size() == minHeap.size()) { return (minHeap.peek() + maxHeap.peek()) / 2; } else if (maxHeap.size() > minHeap.size()) { return maxHeap.peek(); } } |