題目描述

如何得到一個數(shù)據(jù)流中的中位數(shù)？如果從數(shù)據(jù)流中讀出奇數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。如果從數(shù)據(jù)流中讀出偶數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個數(shù)的平均值。

這一題的思路主要在于堆，本豬之前之前都不知道堆是什么。。更不知道大小堆的概念。。故這里僅看懂了思路，但是并沒能夠重現(xiàn)出來，因為并沒有看懂如何維護堆，故在此留坑，看明白如何維護堆的時候，再另作整理。以下為答案：

構建一個最大堆和一個最小堆，分別存儲比中位數(shù)小的數(shù)和大的數(shù)。當目前兩堆總數(shù)為偶數(shù)的時候，把數(shù)字存入最大堆，然后重排最大堆，如果最大堆的堆頂數(shù)字大于最小堆堆頂數(shù)字，則把兩個堆頂數(shù)字交換，重排兩堆，此時兩堆數(shù)字總數(shù)為奇數(shù)，直接輸出最大堆堆頂數(shù)字即為中位數(shù)；如果當前兩堆總數(shù)為技術的時候，把數(shù)字存入最小堆，重排最小堆，如果最大堆的堆頂數(shù)字大于最小堆堆頂數(shù)字，則把兩個堆頂數(shù)字交換，重排兩堆，此時兩堆數(shù)字總數(shù)為偶數(shù)，取兩堆堆頂數(shù)字做平均即為中位數(shù)。

在此先碼一點堆的基本概念：

堆（英語：heap)是計算機科學中一類特殊的數(shù)據(jù)結構的統(tǒng)稱。堆通常是一個可以被看做一棵樹的數(shù)組對象。堆總是滿足下列性質(zhì)：

（1）堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；

（2）堆總是一棵完全二叉樹。

【最大堆】將根節(jié)點最大的堆叫做最大堆或大根堆

【最小堆】根節(jié)點最小的堆叫做最小堆或小根堆