leetCode Question: Find Median from Data Stream

Find Median from Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:
[2,3,4] , the median is 3

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

Design a data structure that supports the following two operations:

void addNum(int num) - Add a integer number from the data stream to the data structure.
double findMedian() - Return the median of all elements so far.
For example:

add(1)
add(2)
findMedian() -> 1.5
add(3)
findMedian() -> 2

Analysis:

The problem give us a data stream instead of a regular data array, and ask to get the median of current data. An obvious but not efficient way of getting median is by either sorting the data ( O( n log n ) time ) or inserting the data in ordered data and ( O( n ) time ). In such scenarios, it's quite slow when findMedian is called very often. Since we have already all the relations between previous data, it would be much more efficient if we could utilize that when adding new data.

Here please refer my previous post (see heap sort) for the basic concept in heap, and it is this very useful data structure that can solve this problem very efficiently ( O( log n ) time to add data, O( 1 ) time to find median).

Specifically in this problem, we still have to figure out how to utilze heap to find the median.

The definition of median can be roughly viewed as the middle one or two values of an ordered list. In other words, the ordered list can be divided into two parts, one part contains all the values less than the median, while values in the other part are all greater than the median. No matter the size of list is even or not, the size of two sub-lists divided by the median must be the same.

OK, now let's see what a heap can help us. We know that a min heap is saving the smallest vaule at root, all the other values are greater than the root. A max heap is saving the largest value at root, with all the child nodes smaller than the root.

Thus, a max heap and a min heap now seems perfect fit for the two sub lists divided by the median. Even, for the median, we don't have to know the full order of the sub lists. We only care about how many elements are greater or smaller than the median.

In order to keep the two heap balanced, once we met a new number, intuitively we should add to each heap alternately one by one. However, we don't want to see any numbers in the max heap is greater than any number in min heap. So we have to adjust the heap after each insertion. Sepecifically,

• If current size is even, we try to add the new element to the min heap
  • If the new number to be added is greater than the root in min heap. OK, we push the number into min heap.
  • However, if the new number to be added is smaller than the largest number in the other heap (root node in max heap), this number should be in the max heap but not the min heap we intend to add to. So we add the new number to max heap instead of min heap. But, we still want to keep both heaps balanced in size. So we pop the top number in max heap (which we added the new element into), and push it into the min heap (which we intended to add one into in this round).
• If current size is odd, we try to add the new element to the max heap
  • If the new number to be added is smaller than the root in max heap. OK, we push the number into max heap.
  • Similarly, if the new number to be added is greater than the smallest number in the other heap. We stil have to the same procedure according to the above case.
• To get the median, if current data size is even, we choose the root of both heap and take average. If current data size is odd, we just return the root of min heap.

For the implementation, in C++, we can use priority queue, which is implemented using heap, it has methods such as push, pop, and top, and we don't have to worry about the node downshift or deletion in detail. The constructor of priority queue provides arguments to set the std::geater for the max heap.

In python, for simplicity, I use headq module which could apply heap operations on list, e.g.,headq.heappush(h, num) is to push num into list h using heap operation. For max heap, I just take a negative of value and insert into a min heap to simulate a max heap.

Code (C++):

class MedianFinder {

public:

// Constructor

MedianFinder(){

count = 0;

}

// Adds a number into the data structure.

void addNum(int num) {

if (count % 2 == 0){

if (minHeap.empty()){

minHeap.push(num);

}else{

if (num <= maxHeap.top()){

maxHeap.push(num);

minHeap.push(maxHeap.top());

maxHeap.pop();

}else {

minHeap.push(num);

}

}

}else{

if (num >= minHeap.top()){

minHeap.push(num);

maxHeap.push(minHeap.top());

minHeap.pop();

}else{

maxHeap.push(num);

}

}

count ++;

// cout << "count = " << count<< endl;

// cout << "maxHeap: ";

// print_queue(maxHeap);

// cout << endl << "minHeap: ";

// print_queue(minHeap);

// cout << endl;

}

// Returns the median of current data stream

double findMedian() {

return count % 2 == 0 ? double(minHeap.top() + maxHeap.top()) / 2 : minHeap.top();

}

private:

priority_queue<int> maxHeap;

priority_queue<int, vector<int>, std::greater<int> > minHeap;

int count;

};

// Your MedianFinder object will be instantiated and called as such:

// MedianFinder mf;

// mf.addNum(1);

// mf.findMedian();

Code (Python):

class MedianFinder:

def __init__(self):

"""

Initialize your data structure here.

"""

import heapq #import heapq to support heap operations on list

self.count = 0

self.minHeap = [] # default heapq is smallest element as root

self.maxHeap = [] # modify the heapq in max heap by making nums negative (* -1), whenever push in or pop out from the maxHeap

def addNum(self, num):

"""

Adds a num into the data structure.

:type num: int

:rtype: void

"""

if self.count % 2 == 0:

if len(self.minHeap) == 0:

heapq.heappush(self.minHeap, num)

else:

if num <= -self.maxHeap[0]:

heapq.heappush(self.maxHeap, -num)

heapq.heappush(self.minHeap, -heapq.heappop(self.maxHeap))

else:

heapq.heappush(self.minHeap, num)

else:

if num >= self.minHeap[0]:

heapq.heappush(self.minHeap, num)

heapq.heappush(self.maxHeap, -heapq.heappop(self.minHeap))

else:

heapq.heappush(self.maxHeap, -num)

self.count += 1

def findMedian(self):

"""

Returns the median of current data stream

:rtype: float

"""

if self.count % 2 == 0:

return (float(self.minHeap[0]) + float(-self.maxHeap[0])) / 2.0

else:

return float(self.minHeap[0])

# Your MedianFinder object will be instantiated and called as such:

# mf = MedianFinder()

# mf.addNum(1)

# mf.findMedian()

leetcode Question: Kth Largest Element in an Array

Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.

Analysis:

This is a good practice of using data structure Heap ! We know that C++ STL already has heap operations, but here in this post, I'd like to write the heap data structure of our own. In one of my previous post (here), I have already introduced the heap sort, in which the code can be applied in this problem perfectly.  Now I will briefly describe how to construct a heap.

In this problem, we utilize array  (list in python) to represent heap, literally heap is a Tree structure, which has the following property:
The value of parent node is greater/smaller than that of its children.
(Be careful with the definition, it has no constrains about the child nodes in the same level)

Before we start to construct heap, firstly let's review the tree representation using array. Simply, let's use a vector<int> to define a binary tree A, where the value of node is type int. Then let's define the tree structure:
(1) Every element is used to represent a tree node.
(2) The root node is defined as the 1st element of A, A[0].
(3) For each node A[i], its left child is A[i*2+1], its right child is A[i*2+2].
(4) For each node A[i], its parent node is A[(i-2)/2], when (i-2)/2 >=0

This is not a very complete definition, but enough for our heap implementation. Now we construct the heap, as well as heap sort algorithm.

The most important step in the algorithm is called "downshift". This downshift operation, takes the root node of the binary tree, compare to its left and right children, swap the value with the greater/smaller child, recursively.  This can be implemented as a standalone function.

Since the tree leaves has no child node, so the leaf nodes are left without any downshift operation. To construct the heap, we can downshift all the non-leaf nodes, from bottom to top. After this loop, the tree is now called a heap.

In order to get the heap sort result (which is usually an array), one more operation is needed. Currently the heap is a binary tree, to get the sorted array, every time we take the root node (which is biggest/smallest element), and then swap the root node with the last node in the tree. (Remember we have used an array to represent a tree?) , then apply downshift of the root node, to keep the tree as a heap.

Code(C++):

class Solution {
public:
    void downshift(vector<int> &h, int n, int parent){
        if (parent < 0){return;}
        int left = parent*2+1;
        int right = parent*2+2;
        int mxch;
        if (left>=n) {return;}
        if (right>=n){mxch=left;}
        else{
            mxch = h[left]>=h[right]?left:right;
        }
        if (h[parent]<h[mxch]){
            int tmp = h[parent];
            h[parent] = h[mxch];
            h[mxch] = tmp;
            downshift(h,n,mxch);
        }
    }


    void constructHeap(vector<int>& h, int n){
        int parent = (n-2/2);
        for (; parent>=0;parent--){
            downshift(h, n, parent);
        }
    }
    
    void heapsort(vector<int> &h, int n){
        constructHeap(h,n);
        int i=n-1;
        vector<int> b(n,0);
        while (i>=0){
            b[n-i-1]=h[0];
            int tmp = h[0];
            h[0] = h[i];
            h[i] = tmp;
            downshift(h,i,0);
            i--;
        }
        for (int i=0;i<n;i++){
            h[i] = b[i];
        }
    }
    
    int findKthLargest(vector<int>& nums, int k) {
        heapsort(nums,nums.size());
        return nums[k-1];
    }
};

Code(Python):

class Solution:
    def downshift(self, nums, n, parent):
        if parent < 0:
            return
        left = parent * 2 + 1
        right = parent * 2 + 2
        if left >= n:
            return
        if right >=n:
            mxch = left
        else:
            if nums[left] >= nums[right]:
                mxch = left
            else:
                mxch = right
                
        if nums[parent]<nums[mxch]:
            nums[parent], nums[mxch] = nums[mxch], nums[parent]
            self.downshift(nums, n, mxch)

    def constructHeap(self, nums, n):
        parent = (n-2)/2
        for i in range(parent,-1,-1):
            self.downshift(nums, n, i)
    
    def heapSort(self, nums, n):
        self.constructHeap(nums, n)
        i = n - 1
        num_tmp = []
        while i>=0:
            num_tmp.append(nums[0])
            nums[0], nums[i] = nums[i], nums[0]
            self.downshift(nums,i,0)
            i -= 1
        return num_tmp
    
    # @param {integer[]} nums
    # @param {integer} k
    # @return {integer}
    def findKthLargest(self, nums, k):
        new = self.heapSort(nums,len(nums))
        return new[k-1]
        

How to use C++ STL heap? A toy example

How to use C++ STL heap?

In my previous post (click here), heap sort algorithm is presented You can also find the basic concept of the heap and how heap data structure is created and maintained. Generally speaking, heap is a tree structure where its parent node is the biggest(max heap) or smallest(min heap) of the values. Note that heap is NOT the BST, by traversing the tree cannot lead you to the sorted sequence as BST.


So, in our daily use or for the interview, sometime you don't have to implement the heap but using it is required. For example, let's see the toy example (this is also an interview question) below:

• How to find pair with kth largest sum? Given two sorted arrays of numbers, we want to find the pair with the kth largest possible sum. (A pair is one element from the first array and one element from the second array). For example, with arrays:

          A [2, 3, 5, 8, 13]
          B [4, 8, 12, 16]
          The pairs with largest sums are
          13 + 16 = 29
          13 + 12 = 25
          8 + 16 = 24
          13 + 8 = 21
          8 + 12 = 20
         So the pair with the 4th largest sum is (13, 8). How to find the pair with the kth largest    possible sum?



Analysis:
When the problem requires the largest, smallest, most frequent, etc. element in a big range of data, or the data is not 'static' but in stream, using heap is a good direction to try (always with the hashmap). For this problem, a max heap can be created according to the sum value, which is the sum of the two values in A and B array respectively. For better illustration, we consider the sorted arrays are in descending order (A[13,9,5,3,2], B[16,12,8,4]).

The algorithm is straightforward it you are familiar with the heap data structure:


(1) Push the A[0],B[0] into the heap.
(2) Do the following k times:
                 Pop the top node (A[i],B[j]) in the heap and output it.
                 Push the A[i+1],B[j] and A[i],B[j+1] into the heap.
(3) Update the heap

In C++ STL, heap can be created using the make_heap , which is in the <algorithm> lib.
And pop_heap, push_heap is used to add and remove element in the heap.
Below I show the code for this problem and you can see how to use the heap with STL:

Code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


bool _cmp(pair<pair<int,int>, int> a, pair<pair<int,int>, int> b){
    return a.second < b.second;
}

int main()
{
    //Initialize the data
    int a[5]= {13,2,3,8,5};
    int b[4] = {8,4,16,12};
    vector<int> A(a,a+5);
    vector<int> B(b,b+4);
    sort(A.rbegin(),A.rend());  // rbegin to get the descending order
    sort(B.rbegin(),B.rend());
    //Print the sorted array
    cout << "Original Arrays: "<< endl;
    for (int i=0;i<A.size();i++){cout << A[i] <<" ";}
    cout <<endl;
    for (int i=0;i<B.size();i++){cout << B[i] <<" ";}
    cout <<endl;

    //Use pair<<id_A,id_B>, A[id_A]+B[id_B]> as the node in the heap
    vector <pair<pair<int,int>, int> > C; // vector to maintain the heap.
    C.push_back(make_pair(make_pair(0,0),A[0]+B[0])); //push the first node
    make_heap(C.begin(),C.end(),_cmp); // make the heap

    int n =5; //get the first 5 biggest pairs
    for (int i=0;i<n;i++){
        pair<pair<int,int>, int> hroot = C.front(); // get the root of the heap (biggest sum)
        int maxi = hroot.first.first;
        int maxj = hroot.first.second;
        cout << "[" << A[maxi] << "," << B[maxj]<< "]," << hroot.second << endl;
        //pop the root node
        pop_heap(C.begin(),C.end(),_cmp);
        C.pop_back();

        //push the two new nodes
        C.push_back(make_pair(make_pair(maxi+1,maxj),A[maxi+1]+B[maxj]));
        push_heap(C.begin(),C.end(),_cmp);

        C.push_back(make_pair(make_pair(maxi,maxj+1),A[maxi]+B[maxj+1]));
        push_heap(C.begin(),C.end(),_cmp);

    }
    return 0;
}