堆實戰(動態數據流求top k大元素,動態數據流求中位數)
- 2019 年 10 月 3 日
- 筆記
動態數據集合中求top k大元素
第1大，第2大 ...第k大 k是這群體里最小的 所以要建立個小頂堆 只需要維護一個大小為k的小頂堆 即可 當來的元素(newCome)> 堆頂元素(smallTop),說明進來的元素有和堆頂競爭的資格,此時的堆頂被踢出 這時把進來的元素放到堆頂 newCome>smallTop,smallTop的左右孩子>smallTop,所以無法確認 newCome和smallTop的左右孩子的大小關係， 在newCome和smallTop的左右子節點找到最小的元素和newCome交換，然後繼續比較newCome與被交換的左右孩子的大小關係 持續這個過程(堆化)即可 如果每次詢問前K大數據，我們都基於當前的數據重新計算的話，那時間複雜度就是O(nlogK)，n表示當前的數據的大小
部分程式碼
topn.php
$static_data=[2,5,3,1,0,7,6,10]; //第3大 /* 2,5,3 2 2,5,3 1 2 2,5,3,1,0 2 2,5,3,1,0,7 3 2,5,3,1,0,7,6 5 2,5,3,1,0,7,6,10 6 維持1個小頂堆 大小為3即可 */ $heap=new Heap(3); //建立一個大小為3的小頂堆 foreach ($static_data as $v){ echo $heap->topn($v).PHP_EOL; } heap.php
public function topn($data) { //堆滿了 if ($this->isFull()) { if ($data > $this->dataArr[1]) { $this->dataArr[1] = $data; $this->smallHeapFirst(); } } else { $this->dataArr[$this->count + 1] = $data; $this->count++; $this->smallHeapLast(); } return $this->dataArr[1]; }動態數據流求中位數
2,3,1,7,5 返回3 1,3,1,7,5,4 返回3,4 數據持續往裡面進，每進來一個數，就詢問中位數是誰們 step1 思路分析:
所謂中位數，就是中間大的1個或者2個元素，中位數滿足的性質，中位數之前的數都它，之後的數都大於它 先以奇數個分析，偶數個原理一樣 1.如果是固定的數據集合，比如數據為n個，中位數即為n/2+1 大的元素，此時只需維護一個大小為(n/2+1) 大小的小頂堆即可 為什麼不能是大頂堆呢，如果堆頂最大，除了知能找到這群集合的最大值外，其它的都無從知曉了 如果是小頂堆，堆頂最小，數據集合比如為5個，第3大的元素肯定小於已經比較過的前2個數，即為中間元素 但是現在是動態數據流，每次進來1個元素，都會詢問中間元素 和靜態數據的區別是:不知道維護的小頂堆的大小了 這時需要維護2個堆了，來了數據，分別放到這2個堆 1個大頂堆，1個小頂堆，大頂堆的數據均小於小頂堆的數據，當要詢問的時候 如果是偶數個數據，兩個堆的堆頂元素即為中間元素 如果奇數個數據，兩個堆中數據較多的那個堆的堆頂元素即為中間元素step1 步驟分析
大頂堆為big,堆頂元素bigpeak,大小為bigsize,小頂堆稱small,堆頂元素為smallpeak,大小為smallsize 進來1個元素，big為空 :放入big big不為空: 放入元素<bigpeak，放入到big 放入元素>bigpeak, 放入到small 放入1個元素完成後 如果bigsize-smallsize>1,把big元素的堆頂元素拿掉 堆化big,把拿掉的元素放入small 然後堆化 如果bigsize-smallsize<1,把small元素的堆頂元素拿掉 堆化small,把拿掉的元素放入big 然後堆化 findmiddle.php
$arr = [9, 8, 11, 4, 2, 6, 5, 1, -1, 3, 20, 10]; //$arr=[9,8,11,4,2,6,5,100]; findMiddle($arr); //動態數據實時獲取中位數 function findMiddle($arr) { //大頂堆 $bigHeap = new Heap(0, 1); //小頂堆 $smallHeap = new Heap(0, 0); foreach ($arr as $k => $v) { if ($bigHeap->isEmpty()) { $bigHeap->insert($v); } else { $bigPeak = $bigHeap->peak(); if ($v < $bigPeak) { $bigHeap->insert($v); } else { $smallHeap->insert($v); } if ($bigHeap->count - $smallHeap->count > 1) { $bigPeak = $bigHeap->deleteFirst(); $smallHeap->insert($bigPeak); } elseif ($smallHeap->count - $bigHeap->count > 1) { $smallPeak = $smallHeap->deleteFirst(); $bigHeap->insert($smallPeak); } } //實時獲取中位數 echo implode(',', midPeak($bigHeap, $smallHeap)) . PHP_EOL; } } function midPeak($heap1, $heap2) { if ($heap1->count == $heap2->count) { $midArr = [$heap1->peak(), $heap2->peak()]; } elseif ($heap2->count > $heap1->count) { $midArr = [$heap2->peak()]; } else { $midArr = [$heap1->peak()]; } return $midArr; } 過程分析
幾個重要的點
- 兩個堆元素數相等時中間元素為兩個堆頂
否者為較多元素堆的堆頂 - 兩者元素個數差值大於1時，要調整堆的元素個數
依次插入的元素 為 9, 8, 11, 4, 2, 6, 5, 1, -1, 3, 20, 10，大頂堆 稱為big,小頂堆稱為small,各自大小bigsize,smallsize,堆頂為bigpeak，smallpeak, 9進來 big為空，插入big, bigsize-smallsize=1 不大於1 此時bigsize>smallsize 中間元素為bigpeak即為[9] 8進來 8<bigpeak, 插入big,bigsize-smallsize=2 大於1 此時bigpeak 需要從Big刪除，big堆化，放入到small ，small堆化 ,此時bigsize=smallsize 所以中間元素為[bigpeak,smallpeak] 即為[8,9] 11進來 11>bigpeak(8),11插入small,此時smallsize=2,bigsize=1,差值不大於1，因為smallsize>bigsize,中間元素為[smallpeak] 即為[9] 4進來 4<bigpeak(8),4插入到big,big堆化，此時bigsize=2,smallsize=2,中間元素為[bigpeak,smallpeak] 即為[8,9]此時堆圖
2進來 2<8 ,2插入big然後堆化，bigsize=3,smallsize=2 所以此時中位數為[8] 6進來 6<8,6插入big後堆化 為下圖 此時,bigsize=4,smallsize=2,bigsize-smallsize>1,刪除big的堆頂元素 堆化，然後把把刪除的元素插入到small，堆化後 此時big,small見下圖,中間元素位[bigpeak,smallpeak]即 [6,8]5進來 5<bigpeak(8),5插入big堆化 此時Bigsize=4,smallsize=3,差值不大於1，中間元素位bigpeak 即為[6] 之後的步驟同理 插入數據因為需要涉及堆化，所以時間複雜度變成了O(logn)，但是求中位數我們只需要返回大頂堆的堆頂元素就可以了，所以時間複雜度就是O(1)
