The title comes from Question 295 in LeetCode: the median of a data stream. The difficulty level is Hard and the current pass rate is 33.5%.

Topic describes

The median is the number in the middle of an ordered list. If the list length is even, the median is the average of the middle two numbers.

For example,

The median of [2,3,4] is 3

The median of [2,3] is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

  • Void addNum(int num) – Adds an integer from the data stream to the data structure.
  • Double findMedian() – Returns the current median for all elements.

Example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2
Copy the code

Input:

Output:

title

This problem gives us a data stream, so let’s figure out the median. For data streams, which are dynamic (flowing), it is inefficient to use arrays and sort each new piece of data that comes in.

The common data structures used to deal with dynamic data are stack, queue, binary tree and heap.

In this case, we use a data structure called a heap.

The data is first divided into two parts, with the largest heap at the top being smaller than the smallest heap at the bottom.

To ensure that data is evenly distributed between the two heaps, the difference in the number of data in the two heaps cannot exceed 1 during a dynamic operation.

To ensure that all the data in the maximum heap is smaller than the data in the minimum heap, new data must be compared with the maximum value of the maximum heap or the minimum value of the minimum heap during operation.

Animation description

Code implementation

class MedianFinder {
    public PriorityQueue<Integer> minheap, maxheap;
    public MedianFinder(a) {
        // Maintain the smallest heap of larger elements
        maxheap = new PriorityQueue<Integer>(Collections.reverseOrder());
        // Maintain the maximum heap of smaller elements
        minheap = new PriorityQueue<Integer>();
    }
    
    // Adds a number into the data structure.
    public void addNum(int num) {
        maxheap.add(num);
        minheap.add(maxheap.poll());
        if(maxheap.size() < minheap.size()) { maxheap.add(minheap.poll()); }}// Returns the median of current data stream
    public double findMedian(a) {
        if (maxheap.size() == minheap.size()) {
            return (maxheap.peek() + minheap.peek()) * 0.5;
        } else {
            returnmaxheap.peek(); }}};Copy the code

Personal website: www.cxyxiaowu.com

Individual public number: five minutes to learn the algorithm