Find k-th smallest element data structure

Question

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.

Answer 1

Two solutions come in mind:

• Use a balanced binary search tree (Red black, AVG, Splay,... any would do). You're already familiar with operation (1) and (2). For operation (3), just store an extra value at each node: the total number of nodes in that subtree. You could easily use this value to find the kth smallest element in O(log(n)). For example, let say your tree is like follows - root A has 10 nodes, left child B has 3 nodes, right child C has 6 nodes (3 + 6 + 1 = 10), suppose you want to find the 8th smallest element, you know you should go to the right side.

• Use a skip list. It also supports all your (1), (2), (3) operations for O(logn) on average but may be a bit longer to implement.

Answer 2

Well, if your data structure keeps the elements sorted, then it's easy to find the kth lowest element.

Answer 3

The worst-case cost of a Binary Search Tree for search and insertion is O(N) while the average-case cost is O(lgN).

Thus, I would recommend using a Red-Black Binary Search Tree which guarantees a worst-case complexity of O(lgN) for both search and insertion.

You can read more about red-black trees here and see an implementation of a Red-Black BST in Java here.
So in terms of finding the k-th smallest element using the above Red-Black BST implementation, you just need to call the select method, passing in the value of k. The select method also guarantees worst-case O(lgN).