3

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 ?

MRMKR
  • 147
  • 1
  • 10
  • You probably want a (balanced) binary search tree: http://stackoverflow.com/questions/2329171/find-kth-smallest-element-in-a-binary-search-tree-in-optimum-way/2329236#2329236 – IVlad Apr 17 '17 at 20:25
  • Possible duplicate of [Find kth smallest element in a binary search tree in Optimum way](http://stackoverflow.com/questions/2329171/find-kth-smallest-element-in-a-binary-search-tree-in-optimum-way) – gsamaras Apr 17 '17 at 20:29

1 Answers1

2

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.

Zim-Zam O'Pootertoot
  • 17,888
  • 4
  • 41
  • 69