CODEWITHSUNDEEP
algorithmdata-structuresheap
Allan Jiang
Allan Jiang

Reputation: 11341

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.

Upvotes: 5

Views: 6747

Answers (6)

ayushi singhania
ayushi singhania

Reputation: 1

I think it's not that bad to use heap. You can use max PriorityQueue or maxHeap.

In this method you won't have to iterate through all the values or (k-1) values to get the kth smallest element.

you can do something like: -

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
public void set(int i ){
    pq.set(i);

    if(pq.size() > k){
        pq.poll();
    }
}

public int get(){
    return pq.peek();
}

Upvotes: -1

Zoran Horvat
Zoran Horvat

Reputation: 11311

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

Upvotes: 0

moajiz
moajiz

Reputation: 231

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)

Upvotes: 0

Pinch
Pinch

Reputation: 2888

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.

Upvotes: 8

Gabriella Gonzalez
Gabriella Gonzalez

Reputation: 35099

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

Upvotes: 7

Draco
Draco

Reputation: 262

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

Upvotes: 1

Related Questions