---
# System prepended metadata

title: Find Median by Heap

---

# Find Median by Heap

動態地維護了一個大頂堆max_heap和一個小頂堆min_heap，這兩個堆各自存放「一半」的資料（這裡的「一半」是指兩個堆的size()相差小於等於1），且維持max_heap的堆頂<=min_heap的堆頂。

1. 在插入新元素x時，如果max_heap為空，直接將x壓入max_heap；

2. 否則，先比較 max_heap.size() 與 min_heap.size()：

    若max_heap與min_heap元素個數相同：

        若 x < max_heap 的堆頂，將x壓入 max_heap；

        否則，將x壓入 min_heap；

    若 max_heap 比 min_heap 的size小（需要通過調整兩個堆，以保證平衡）：

        若 x < max_heap 的堆頂，直接將x壓入 max_heap；

        否則，將 min_heap 的堆頂彈出並壓入 max_heap，再將x壓入min_heap

   若 max_heap 比 min_heap 的size大（同樣需要通過調整兩個堆）：

        若 x > max_heap 的堆頂，直接將x壓入 min_heap；

        否則，將 max_heap 的堆頂彈出並壓入 min_heap，再將x壓入max_heap

3. 求中位數:

    若max_heap與min_heap元素個數相同：

        median = max_heap 的堆頂與 min_heap 的堆頂的算數平均值

    若 max_heap 比 min_heap 的size小：

        median = min_heap 的堆頂

    否則：

        median = max_heap 的堆頂


## leecode problem 295

```
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

// leetcode problem 295

int main(){
    priority_queue<int> max_heap;
    priority_queue<int, vector<int>, greater<int>> min_heap;

    int x;
    cin >> x;
    max_heap.push(x);
    while(cin >> x){
        if(x == 0){
            break;
        }
        if(max_heap.size() > min_heap.size()){
            if(x >= max_heap.top()){
                min_heap.push(x);
            }else{
                min_heap.push(max_heap.top());
                max_heap.pop();
                max_heap.push(x);
            }

        }else if(max_heap.size() < min_heap.size()){
            if(x <= min_heap.top()){
                max_heap.push(x);
            }else{
                max_heap.push(min_heap.top());
                min_heap.pop();
                min_heap.push(x);
            }
        }else{
            if(x >= max_heap.top()){
                min_heap.push(x);
            }else{
                max_heap.push(x);
            }
        }

        if(max_heap.size() > min_heap.size()){
            cout << max_heap.top() << endl;
        }else if(max_heap.size() < min_heap.size()){
            cout << min_heap.top() << endl;
        }else{
            cout << (float)(max_heap.top() + min_heap.top()) / 2 << endl;
        }

    }

	return 0;
}

```


