大根堆加小根堆查找中位数o(N)时间复杂度
#include<bits/stdc++.h>
using namespace std;
#define maxn 501
int a[maxn]; // 大根堆
int b[maxn]; // 小根堆
int i=0,j=0; // i是大根堆大小，j是小根堆大小
void swap(int i,int j,int *a){
int tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
void Bigheapinsert(int x){
a[i] = x;
int m = i++;
while(m > 0){
int n = (m-1)/2;
if(a[n] >= a[m]) break;
swap(m,n,a);
m = n;
}
}
void Smallheapinsert(int x){
b[j] = x;
int m = j++;
while(m > 0){
int n = (m-1)/2;
if(b[n] <= b[m]) break;
swap(m,n,b);
m = n;
}
}
void Bigheapify(){
int pos = 0;
while(true){
int left = 2*pos+1;
int right = 2*pos+2;
int largest = pos;
if(left < i && a[left] > a[largest]) largest = left;
if(right < i && a[right] > a[largest]) largest = right;
if(largest == pos) break;
swap(pos, largest, a);
pos = largest;
}
}
void Smallheapify(){
int pos = 0;
while(true){
int left = 2*pos+1;
int right = 2*pos+2;
int smallest = pos;
if(left < j && b[left] < b[smallest]) smallest = left;
if(right < j && b[right] < b[smallest]) smallest = right;
if(smallest == pos) break;
swap(pos, smallest, b);
pos = smallest;
}
}
int main(){
int n;
cin>>n;
int arr[n];
for(int k=0;k<n;k++){
cin>>arr[k];
}
for(int k=0;k<n;k++){
if(i+j == 0 || arr[k] <= a[0]){
Bigheapinsert(arr[k]);
}else{
Smallheapinsert(arr[k]);
}
// 平衡堆大小
if(i-j > 1){
int val = a[0];
a[0] = a[--i];
Bigheapify();
Smallheapinsert(val);
}
else if(j-i > 1){
int val = b[0];
b[0] = b[--j];
Smallheapify();
Bigheapinsert(val);
}
}
double ans = -1;
if((i+j)%2 == 0){
ans =(double) (a[0]+b[0])/2;
}else{
ans =(double) ((i > j) ? a[0] : b[0]);
}
cout<<"ans = "<<ans<<endl;
return 0;
}