算法分析
添加一个元素时:
原则:大的元素往小根堆里面放,小的元素往大根堆里面放,保证A
和B
的值可以取到中位数,并且规定小根堆比大根堆最多多一个,设新来的元素是x
-
1、若小根堆为空或者
x >= A
,则插入到小根堆up
中,否则插入到大根堆中 -
2、维护大根堆和小根堆的数量关系:小根堆比大根堆最多多一个,
- 若
up.size() > down.size() + 1
,将小根堆的堆顶元素转移到大根堆中 - 若
down.size() > up.size()
,将大根堆的堆顶元素转移到小根堆中
- 若
-
3、获取中位数
-
若总体数量为奇数时,中位数为
A
-
若总体数量为偶数时,中位数为
(A + B)/2
-
时间复杂度 $O(Tnlogn)$
Java 代码
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main
{
static PriorityQueue<Integer> up = new PriorityQueue<Integer>();
static PriorityQueue<Integer> down = new PriorityQueue<Integer>((x,y) -> y - x);
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int T = scan.nextInt();
while(T -- > 0)
{
up.clear();
down.clear();
int no = scan.nextInt();
int n = scan.nextInt();
System.out.println(no + " " + (n + 1) / 2);
int cnt = 0;
for(int i = 1;i <= n;i ++)
{
int x = scan.nextInt();
if(up.isEmpty() || x >= up.peek()) up.add(x);
else down.add(x);
//维护两个堆的大小关系
if(up.size() > down.size() + 1) down.add(up.poll());
else if(down.size() > up.size()) up.add(down.poll());
if(i % 2 != 0)
{
System.out.print(up.peek() + " ");
if(++ cnt % 10 == 0) System.out.println();
}
}
if (cnt % 10 != 0) System.out.println();
}
}
}
请问一下大佬,大根堆和小根堆的数量哪个多一有讲究吗