algorithmdata-structuresheap

Find k-th smallest element data structure


I have a problem here that requires to design a data structure that takes O(lg n) worst case for the following three operations:

  a) Insertion: Insert the key into data structure only if it is not already there.
  b) Deletion: delete the key if it is there!
  c) Find kth smallest : find the ݇k-th smallest key in the data structure

I am wondering if I should use heap but I still don't have a clear idea about it.
I can easily get the first two part in O(lg n), even faster but not sure how to deal with the c) part.

Anyone has any idea please share.


Solution

  • Two solutions come in mind: