线段树、树状数组虽然查找第k大元素很方便,树状数组代码更是相当短。但是,两者必须要求数据为一定范围内的整数,否则就不能用区间和来查找第k大元素了。所以,学习用BST查找第k大元素是很有必要的。下面给出代码,Pascal版本的Treap查找第k大元素,写得很丑。
{
小根堆实现,支持插入、删除、findkth等操作,其它的什么findmin什么的应该不难。
主要是要维护一个size和cnt域,另外每次旋转啊插入啊删除啊都要更新一下size域
以编程简单的treap也要写一百多行,当然可以精简一些代码,如果是C/C++应该更短
2011-08-12 22:45
}
const
INF=19930317;
var
t:array[0..1000000] of record x,aux,l,r,size,cnt:longint end;
i,j,k,root,x,n,m,size:longint;
procedure modify(i:longint);
begin
t[i].size:=t[t[i].l].size+t[t[i].r].size+t[i].cnt;
end;
procedure left(var i:longint);
var
j:longint;
begin
j:=t[i].r;
t[i].r:=t[j].l;
t[j].l:=i;
modify(i);
i:=j;
modify(i);
end;
procedure right(var i:longint);
var
j:longint;
begin
j:=t[i].l;
t[i].l:=t[j].r;
t[j].r:=i;
modify(i);
i:=j;
modify(i);
end;
procedure insert(var i:longint; x:longint);
begin
if i=0 then
begin
inc(size);
i:=size;
t[size].size:=1;
t[size].cnt:=1;
t[size].l:=0;
t[size].r:=0;
t[size].aux:=random(INF);
t[size].x:=x;
end
else begin
if t[i].x=x then
begin
inc(t[i].cnt);
end
else if x<t[i].x then
begin
insert(t[i].l,x);
if t[t[i].l].aux<t[i].aux then
right(i);
end
else if x>t[i].x then
begin
insert(t[i].r,x);
if t[t[i].r].aux<t[i].aux then
left(i);
end;
modify(i);
end;
end;
procedure delete(var i:longint; x:longint);
begin
if i=0 then
exit;
if x<t[i].x then
delete(t[i].l,x)
else if x>t[i].x then
delete(t[i].r,x)
else begin
if t[i].cnt>1 then
dec(t[i].cnt)
else if t[i].l=0 then
i:=t[i].r
else if t[i].r=0 then
i:=t[i].l
else if t[t[i].l].aux < t[t[i].r].aux then
begin
right(i);
delete(t[i].r,x);
end
else begin
left(i);
delete(t[i].l,x);
end
end;
if i<>0 then
modify(i);
end;
function findkth(i,k:longint):longint;
begin
if k<=t[t[i].l].size then
exit(findkth(t[i].l,k));
if k<=t[t[i].l].size+t[i].cnt then
exit(t[i].x);
exit(findkth(t[i].r,k-t[t[i].l].size-t[i].cnt));
end;
begin
randomize;
t[0].aux:=INF;
readln(n);
for i:=1 to n do
begin
read(x);
insert(root,x);
end;
readln(m);
for i:=1 to m do
begin
read(x);
writeln(findkth(root,x));
end;
readln(m);
for i:=1 to m do
begin
read(x);
delete(root,x);
end;
readln(m);
for i:=1 to m do
begin
read(x);
writeln(findkth(root,x));
end;
end.
原文链接: https://www.cnblogs.com/oa414/archive/2011/08/14/2138574.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/30518
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!