Google 面试题：Java实现用最大堆和最小堆查找中位数 Find median with min heap and max heap in Java

浏览数：46 / 时间：2015年06月08日

Google面试题

股市上一个股票的价格从开市开始是不停的变化的，需要开发一个系统，给定一个股票，它能实时显示从开市到当前时间的这个股票的价格的中位数（中值）。

SOLUTION 1:

1.维持两个heap,一个是最小堆，一个是最大堆。

2.一直使maxHeap的size大于minHeap.

3. 当两边size相同时，比较新插入的value,如果它大于minHeap的最大值，把它插入到minHeap。并且把minHeap的最小值移动到maxHeap。

...具体看代码

 1 /**************************************************************
 2  * 
 3  * 08-722 Data Structures for Application Programmers
 4  * Lab 7 Heaps and Java PriorityQueue class
 5  * 
 6  * Find median of integers using Heaps (maxHeap and minHeap)
 7  * 
 8  * Andrew id:  yuzhang
 9  * Name: Yu Zhang
10  * 
11  **************************************************************/
12 
13 import java.util.*;
14 
15 public class FindMedian {
16     private static PriorityQueue<Integer> maxHeap, minHeap;
17 
18     public static void main(String[] args) {
19 
20         Comparator<Integer> revCmp = new Comparator<Integer>() {
21             @Override
22             public int compare(Integer left, Integer right) {
23                 return right.compareTo(left);
24             }
25         };
26 
27         // Or you can use Collections‘ reverseOrder method as follows.
28         // Comparator<Integer> revCmp = Collections.reverseOrder();
29 
30         maxHeap = new PriorityQueue<Integer>(20, revCmp);
31         minHeap = new PriorityQueue<Integer>(20);
32 
33         addNumber(6);
34         addNumber(4);
35         addNumber(3);
36         addNumber(10);
37         addNumber(12);
38         System.out.println(minHeap);
39         System.out.println(maxHeap);
40         System.out.println(getMedian());
41 
42         addNumber(5);
43         System.out.println(minHeap);
44         System.out.println(maxHeap);
45         System.out.println(getMedian());
46 
47         addNumber(7);
48         addNumber(8);
49         System.out.println(minHeap);
50         System.out.println(maxHeap);
51         System.out.println(getMedian());
52     }
53 
54     /*
55      * Note: it maintains a condition that maxHeap.size() >= minHeap.size()
56      */
57     public static void addNumber(int value) {
58         if (maxHeap.size() == minHeap.size()) {
59             if (minHeap.peek() != null && value > minHeap.peek()) {
60                 maxHeap.offer(minHeap.poll());
61                 minHeap.offer(value);
62             } else {
63                 maxHeap.offer(value);
64             }
65         } else {
66             if (value < maxHeap.peek()) {
67                 minHeap.offer(maxHeap.poll());
68                 maxHeap.offer(value);
69             } else {
70                 minHeap.offer(value);
71             }
72         }
73     }
74 
75     /*
76      * If maxHeap and minHeap are of different sizes, 
77      * then maxHeap must have one extra element.
78      */
79     public static double getMedian() {
80         if (maxHeap.isEmpty()) {
81             return -1; 
82         }
83         
84         if (maxHeap.size() == minHeap.size()) {
85             return (double)(minHeap.peek() + maxHeap.peek())/2;
86         } else {
87             return maxHeap.peek();
88         }
89     }
90 }

View Code

SOLUTION 2:

比起solution 1 ，进行了简化

1.无论如何，直接把新值插入到maxHeap。

2. 当minHeap为空，直接退出。

3. 当maxHeap比minHeap多2个值，直接移动一个值到maxHeap即可。

4. 当maxHeap比minHeap多1个值，比较顶端的2个值，如果maxHeap的最大值小于minHeap的最小值，交换2个值即可。

5. 当maxHeap较大时，中值是maxHeap的顶值，否则取2者的顶值的中间值。

  1 /**************************************************************
  2  * 
  3  * 08-722 Data Structures for Application Programmers
  4  * Lab 7 Heaps and Java PriorityQueue class
  5  * 
  6  * Find median of integers using Heaps (maxHeap and minHeap)
  7  * 
  8  * Andrew id:  yuzhang
  9  * Name: Yu Zhang
 10  * 
 11  **************************************************************/
 12 
 13 import java.util.*;
 14 
 15 public class FindMedian_20150122 {
 16     private static PriorityQueue<Integer> maxHeap, minHeap;
 17 
 18     public static void main(String[] args) {
 19         // Or you can use Collections‘ reverseOrder method as follows.
 20         // Comparator<Integer> revCmp = Collections.reverseOrder();
 21 
 22         maxHeap = new PriorityQueue<Integer>(20, new Comparator<Integer>(){
 23             public int compare(Integer o1, Integer o2) {
 24                 return o2 - o1;
 25             }
 26         });
 27         
 28         minHeap = new PriorityQueue<Integer>(20);
 29 
 30         addNumber(6);
 31         addNumber(4);
 32         addNumber(3);
 33         addNumber(10);
 34         addNumber(12);
 35         System.out.println(minHeap);
 36         System.out.println(maxHeap);
 37         System.out.println(getMedian());
 38 
 39         addNumber(5);
 40         System.out.println(minHeap);
 41         System.out.println(maxHeap);
 42         System.out.println(getMedian());
 43 
 44         addNumber(7);
 45         addNumber(8);
 46         System.out.println(minHeap);
 47         System.out.println(maxHeap);
 48         System.out.println(getMedian());
 49     }
 50 
 51     /*
 52      * Note: it maintains a condition that maxHeap.size() >= minHeap.size()
 53      */
 54     public static void addNumber1(int value) {
 55         if (maxHeap.size() == minHeap.size()) {
 56             if (!maxHeap.isEmpty() && value > minHeap.peek()) {
 57                 // put the new value in the right side.
 58                 maxHeap.offer(minHeap.poll());
 59                 minHeap.offer(value);
 60             } else {
 61                 // add the new value into the left side.
 62                 maxHeap.offer(value);
 63             }
 64         } else {
 65             if (value < maxHeap.peek()) {
 66                 // add the new value into the left side.
 67                 minHeap.offer(maxHeap.poll());
 68                 maxHeap.offer(value);
 69             } else {
 70                 // add the new value into the right side.
 71                 minHeap.offer(value);
 72             }
 73         }
 74     }
 75     
 76     /*
 77      * Note: it maintains a condition that maxHeap.size() >= minHeap.size()
 78      * solution 2:
 79      */
 80     public static void addNumber(int value) {
 81         maxHeap.offer(value);
 82         
 83         // For this case, before insertion, max-heap has n+1 and min-heap has n elements.  
 84         // After insertion, max-heap has n+2 and min-heap has n elements, so violate!  
 85         // And we need to pop 1 element from max-heap and push it to min-heap  
 86         if (maxHeap.size() - minHeap.size() == 2) {
 87             // move one to the right side.
 88             minHeap.offer(maxHeap.poll());
 89         } else {
 90             if (minHeap.isEmpty()) {
 91                 return;
 92             }
 93             
 94             // If the newly inserted value is larger than root of min-heap  
 95             // we need to pop the root of min-heap and insert it to max-heap.  
 96             // And pop root of max-heap and insert it to min-heap 
 97             if (minHeap.peek() < maxHeap.peek()) {
 98                 // exchange the top value in the minHeap and the maxHeap.
 99                 minHeap.offer(maxHeap.poll());
100                 maxHeap.offer(minHeap.poll());
101             }
102         }
103     }
104 
105     /*
106      * If maxHeap and minHeap are of different sizes, 
107      * then maxHeap must have one extra element.
108      */
109     public static double getMedian() {
110         if (maxHeap.isEmpty()) {
111             return -1;
112         }
113         
114         if (maxHeap.size() > minHeap.size()) {
115             return maxHeap.peek();
116         } else {
117             return (double)(maxHeap.peek() + minHeap.peek()) / 2;
118         }
119     }
120 }