CODEWITHSUNDEEP
algorithmdata-structures
MRMKR
MRMKR

Reputation: 147

Datastructure for many queries of getting kth largest value

I'm trying to solve probelm which states: make data structure which supports:

1) Add element with key k

2) Delete element with key k

3) Print kth largest element in data structure

I thought that maxheap should work, but in this case we need to delete first k-1 largest value from heap to get the kth maximum element, so it won't work here.

How I can solve this ?

Upvotes: 3

Views: 405

Answers (1)

Zim-Zam O'Pootertoot
Zim-Zam O'Pootertoot

Reputation: 18148

You can solve this with an order statistic tree, which is a (balanced) binary tree that lets you find the ith smallest (or largest) element in log(n) time with a balanced tree.

Upvotes: 2

Related Questions