[LeetCode] Find Median from Data Stream

Question can be found https://leetcode.com/problems/find-median-from-data-stream/

class MedianFinder {
    priority_queue<int> up;
    priority_queue<int, vector<int>, greater<int> > down;
public:
    // Adds a number into the data structure.
    void addNum(int num) {
        if(up.empty() || num <= up.top()) {
            up.push(num);
        }
        else if(down.empty() || num >= down.top()) {
            down.push(num);
        }
        else {
            up.push(num);
        }

        if(up.size() >= down.size() + 2) {
            int t = up.top();
            up.pop();
            down.push(t);
        }
        else if(down.size() >= up.size() + 2){
            int t = down.top();
            down.pop();
            up.push(t);
        }
    }
    // Returns the median of current data stream
    double findMedian() {
        if(up.size() > down.size()) return up.top();
        else if(down.size() > up.size()) return down.top();
        return (up.top() + down.top())/2.0;
    }
};

[LintCode] Heapify

Given an integer array, heapify it into a min-heap array.

For a heap array A, A[0] is the root of heap, and for each A[i], A[i * 2 + 1] is the left child of A[i] and A[i * 2 + 2] is the right child of A[i].

Example

Given [3,2,1,4,5], return [1,2,3,4,5] or any legal heap array.

class Solution {
public:
    void heapify(vector<int> &num) 
    {
        int len = num.size();
        int start = (len-2)/2;
        while(start >= 0)
        {
            int root = start;
            while(2*root+1 < len)
            {
                int swap = root;
                int left = 2*root + 1;
                int right = left + 1;
                
                if(num[swap]>num[left]) swap = left;
                if(right<len&&num[right]<num[swap]) swap = right;
                
                if(swap == root) break;
                int tmp = num[swap];
                num[swap] = num[root];
                num[root] = tmp;
                root = swap;
            }
            start --;
        }
    }
};