Heap | Learn for Master

  • Find median of a infinite stream of integers

    January 30, 2017 Author: david
    No comment yet

    Median of a stream of numbers

    Given a stream of integers, find the median of the stream of numbers received so far. 

    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.

    Median of stream of numbers can be queried at multiple times at different point of time. Insertion and median functions can be called in any order. For example:

    First solution be to store the stream received in an unsorted array.

    [Read More...]

  • LeetCode – Find the kth largest element in an unsorted array (Java)

    July 24, 2016 Author: david
    No comment yet

    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

    It’s easy to first sort the array, then pick up the Kth largest element. The time complexity is O(nlogn) if we use quick sort. 

    Min Heap Based Method

    A better method is use a min heap or PriorityQueue with size K.  

    [Read More...]