Take the 2-minute tour ×

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.

share|improve this question
If you used a heap, how would you find the smallest element? After that, how would you find the 2nd smallest? 3rd, 4th, 5th? Now, how would you find the kth-smallest? What would be the processing Order of finding the kth smallest? (Hint: It'd be O(k lg n)) –  abelenky Apr 9 '12 at 1:07
add comment

5 Answers

up vote 6 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
I see nothing wrong with this answer (yet); if you downvoted, please consider leaving a comment. In fact, this seems like a very reasonable answer. –  ninjagecko Apr 9 '12 at 1:34
+1 In fact, this answer seems to be practically correct (except for the O(1)): use a skiplist to keep track of the elements. Perform an online insertion sort to keep the elements sorted in a en.wikipedia.org/wiki/Skip_list#Indexable_skiplist . Insertions, deletions, and indexing (kth largest element) are each O(log(N)) (not O(1) though, sadly, unless you can find another dynamically-updatable datastructure). –  ninjagecko Apr 9 '12 at 1:39
I +1'd because what it said is correct and a relevant hint. I agree it seemed a bit discouraging to -1 without explaining why in a comment. –  gbulmer Apr 9 '12 at 1:57
Yes, I was wrong about O(1). I"ll fix it. –  Gabriel Gonzalez Apr 9 '12 at 2:08
I think a good way of doing it is using a min heap.... –  Allan Jiang Apr 9 '12 at 3:03
add comment

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).

share|improve this answer
Indeed you could do it this way. I believe you would need to augment each junction in the binary tree with the metadata of "number of children this element has", so you could perform binary search to find the kth element by merely descending the tree from the root. –  ninjagecko Apr 9 '12 at 1:47
add comment

One of the solution could be using the strategy of quick sort.

Step 1 : Pick the fist element as pivot element and take it to its correct place. (maximum n checks) now when you reach the correct location for this element then you do a check

step 2.1 : if location >k your element resides in the first sublist. so you are not interested in the second sublist.

step 2.2 if location

step 2.3 if location == k you have got the element break the look/recursion

Step 3: repete the step 1 to 2.3 by using the appropriate sublist

Complexity of this solution is O(n log n)

share|improve this answer
add comment

Heap is not the right structure for finding the Kth smallest element of an array, simply because you would have to remove K-1 elements from the heap in order to get to the Kth element.

There is a much better approach to finding Kth smallest element, which relies on median-of-medians algorithm. Basically any partition algorithm would be good enough on average, but median-of-medians comes with the proof of worst-case O(N) time for finding the median. In general, this algorithm can be used to find any specific element, not only the median.

Here is the analysis and implementation of this algorithm in C#: Finding Kth Smallest Element in an Unsorted Array

P.S. On a related note, there are many many things that you can do in-place with arrays. Array is a wonderful data structure and only if you know how to organize its elements in a particular situation, you might get results extremely fast and without additional memory use.

Heap structure is a very good example, QuickSort algorithm as well. And here is one really funny example of using arrays efficiently (this problem comes from programming Olympics): Finding a Majority Element in an Array

share|improve this answer
add comment

Your Answer


