数据流的中位数

地址

数据流的中位数

解题思路

1、整个数组分为两部分，第一部分是一个大顶堆，第二部分是一个小顶堆；
2、在插入的过程中，保证第一部分和第二部分的数量相差不超过1，且大顶堆的最大值不超过小顶堆的最小值；
3、优先插入大顶堆，当数量大于小顶堆的时候，把大顶堆的最大值向小顶堆转移；注意，大顶堆只有一个数组的时候，不要转移；
4、当两个堆数量相等的时候，如果大顶堆的最大值大于小顶堆的最小值，那么交换，并重新调整堆；

代码

class MedianFinder {
public:
    /** initialize your data structure here. */
    std::vector<int> minHeap;
    std::vector<int> maxHeap;
    MedianFinder() {
        minHeap.clear();
        maxHeap.clear();
    }
    
    void adjustMaxHeap(std::vector<int>& maxHeap,int currentIndex)
    {
        int parentIndex = findParentNodeIndex(currentIndex);
        if(parentIndex < 0 || parentIndex >= maxHeap.size())
        {
            return;
        }

        if(maxHeap[parentIndex] < maxHeap[currentIndex])
        {
            int temp = maxHeap[parentIndex];
            maxHeap[parentIndex] = maxHeap[currentIndex];
            maxHeap[currentIndex] = temp;
            adjustMaxHeap(maxHeap,parentIndex);
        }
    }
    
    void adjustMaxHeapFromTop(std::vector<int>& heap, int currentIndex)
    {
        if (currentIndex >= heap.size() || currentIndex < 0)
        {
            return;
        }

        // 取左孩子
        int iLeftIndex = findLeftNodeIndex(currentIndex);
        if (iLeftIndex >= heap.size() || iLeftIndex < 0)
        {
            return;
        }
        if (heap[currentIndex] < heap[iLeftIndex])
        {
            int temp = heap[currentIndex];
            heap[currentIndex] = heap[iLeftIndex];
            heap[iLeftIndex] = temp;
            adjustMaxHeapFromTop(heap, iLeftIndex);
        }

        // 取右节点
        int iRightIndex = findRightNodeIndex(currentIndex);
        if (iRightIndex >= heap.size() || iRightIndex < 0)
        {
            return;
        }
        if (heap[currentIndex] < heap[iRightIndex])
        {
            int temp = heap[currentIndex];
            heap[currentIndex] = heap[iRightIndex];
            heap[iRightIndex] = temp;
            adjustMaxHeapFromTop(heap, iRightIndex);
        }
    }
    
    void adjustMinHeapFromTop(std::vector<int>& heap,int currentIndex)
    {
        if(currentIndex >= heap.size() || currentIndex < 0)
        {
            return;
        }

        // 取左孩子
        int iLeftIndex = findLeftNodeIndex(currentIndex);
        if(iLeftIndex >= heap.size() || iLeftIndex < 0)
        {
            return;
        }
        if(heap[currentIndex] > heap[iLeftIndex])
        {
            int temp = heap[currentIndex];
            heap[currentIndex] = heap[iLeftIndex];
            heap[iLeftIndex] = temp;
            adjustMinHeapFromTop(heap,iLeftIndex);
        }
        
        // 取右节点
        int iRightIndex = findRightNodeIndex(currentIndex);
        if(iRightIndex >= heap.size() || iRightIndex < 0)
        {
            return;
        }
        if(heap[currentIndex] > heap[iRightIndex])
        {
            int temp = heap[currentIndex];
            heap[currentIndex] = heap[iRightIndex];
            heap[iRightIndex] = temp;
            adjustMinHeapFromTop(heap,iRightIndex);
        }



    }

    int findParentNodeIndex(int index)
    {
        return floor((index -1 )/2);
    }
    int findLeftNodeIndex(int index)
    {
        return 2*index+1;
    }
    int findRightNodeIndex(int index)
    {
        return 2*index+2;
    }
    void adjustMinHeap(std::vector<int>& minHeap,int currentIndex)
    {
        // 1、找到父节点
        int parentIndex = findParentNodeIndex(currentIndex);
        if(parentIndex < 0)
        {
            return;
        }

        if(minHeap[parentIndex] > minHeap[currentIndex])
        {
            int temp = minHeap[parentIndex];
            minHeap[parentIndex] = minHeap[currentIndex];
            minHeap[currentIndex] = temp;
            adjustMinHeap(minHeap,parentIndex);
        }
    }
    void addNum2MaxHeap(int num)
    {
        maxHeap.push_back(num);
        adjustMaxHeap(maxHeap,maxHeap.size()-1);
        if ((maxHeap.size() > minHeap.size()) && maxHeap.size() > 1)
        {
            int max = maxHeap[0];
            addNum2MinHeap(max);
            maxHeap[0] = maxHeap[maxHeap.size()-1];
            maxHeap.pop_back();
            adjustMaxHeapFromTop(maxHeap,0);
        }

        if ((maxHeap.size() == minHeap.size()) && maxHeap.size() >= 1)
        {
            if (maxHeap[0] > minHeap[0])
            {
                int tmp1 = maxHeap[0];
                int tmp2 = minHeap[0];
                maxHeap[0] = tmp2;
                adjustMaxHeapFromTop(maxHeap, 0);
                minHeap[0] = tmp1;
                adjustMinHeapFromTop(minHeap, 0);
            }
        }
    }

    void addNum2MinHeap(int num)
    {
        minHeap.push_back(num);
        adjustMinHeap(minHeap,minHeap.size()-1);
    }

    
    void addNum(int num) {
        addNum2MaxHeap(num);
    }
    
    double findMedian() {
        if((minHeap.size() + maxHeap.size()) % 2 == 0)
        {
            double t = (double)minHeap[0] + (double)maxHeap[0];
            return t /2;
        }
        if(minHeap.size() > maxHeap.size() )
        {
            return minHeap[0];
        }
        return maxHeap[0];
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */