CODEWITHSUNDEEP
c++
leo
leo

Reputation: 61

choose n largest elements in two vector

I have two vectors, each contains n unsorted elements, how can I get n largest elements in these two vectors?

my solution is merge two vector into one with 2n elements, and then use std::nth_element algorithm, but I found that's not quite efficient, so anyone has more efficient solution. Really appreciate.

Upvotes: 1

Views: 326

Answers (4)

ltjax
ltjax

Reputation: 15997

You can do the "n'th element" algorithm conceptually in parallel on the two vectors quite easiely (at least the simple variant that's only linear in the average case).

  1. Pick a pivot.
  2. Partition (std::partition) both vectors by that pivot. You'll have the first vector partitioned by some element with rank i and the second by some element with rank j. I'm assuming descending order here.
  3. If i+j < n, recurse on the right side for the n-i-j greatest elements. If i+j > n, recurse on the left side for the n greatest elements. If you hit i+j==n, stop the recursion.

You basically just need to make sure to partition both vectors by the same pivot in every step. Given a decent pivot selection, this algorithm is linear in the average case (and works in-place).

See also: http://en.wikipedia.org/wiki/Selection_algorithm#Partition-based_general_selection_algorithm

Edit: (hopefully) clarified the algorithm a bit.

Upvotes: 0

Chris Hopman
Chris Hopman

Reputation: 2102

vector<T> heap;
heap.reserve(n + 1);

vector<T>::iterator left = leftVec.begin(), right = rightVec.begin();

for (int i = 0; i < n; i++) {
    if (left != leftVec.end()) heap.push_back(*left++);
    else if (right != rightVec.end()) heap.push_back(*right++);
}

if (left == leftVec.end() && right == rightVec.end()) return heap;

make_heap(heap.begin(), heap.end(), greater<T>());

while (left != leftVec.end()) {
    heap.push_back(*left++);
    push_heap(heap.begin(), heap.end(), greater<T>());
    pop_heap(heap.begin(), heap.end(), greater<T>());
    heap.pop_back();
}

/* ... repeat for right ... */

return heap;

Note I use *_heap directly rather than priority_queue because priority_queue does not provide access to its underlying data structure. This is O(N log n), slightly better than the naive O(N log N) method if n << N.

Upvotes: 1

ur.
ur.

Reputation: 2947

Assuming that n is far smaller than N this is quite efficient. Getting minElem is cheap and sorted inserting in L cheaper than sorting of the two vectors if n << N. 

L := SortedList()
For Each element in any of the vectors do
{
  minElem := smallest element in L
  if( element >= minElem or if size of L < n)
  {
    add element to L
    if( size of L > n )
    {
      remove smallest element from L
    }
  }
}

Upvotes: 1

Juraj Blaho
Juraj Blaho

Reputation: 13451

You may push the elements into priority_queue and then pop n elements out.

Upvotes: 1

Related Questions