# C++ Solution with Heap Sort implemented

• ``````class Solution {
public:
vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
if (nums1.empty() || nums2.empty()) return vector<pair<int, int>>();
vector<pair<int, int>> bucket;
vector<pair<int, int>> result;
for (int i=0; i < nums1.size(); i++){
for (int j=0; j < nums2.size(); j++){
bucket.push_back(make_pair(nums1[i], nums2[j]));
}
}

if (k > bucket.size()) k = bucket.size();
get_kth_element_sorted(bucket, k);
for (int i=0; i < k; i++) {
result.push_back(bucket[bucket.size()-1-i]);
}
return result;
}

int left(int idx){
return (idx << 1) + 1;
}
int right(int idx){
return (idx << 1) + 2;
}
//
void min_heapify(vector<pair<int, int>>& bucket, int idx){
int l = left(idx);
int r = right(idx);
int smallest = idx;
if (l < heap_size && (bucket[l].first+bucket[l].second) < (bucket[smallest].first+bucket[smallest].second)) smallest = l;
if (r < heap_size && (bucket[r].first+bucket[r].second) < (bucket[smallest].first+bucket[smallest].second)) smallest = r;
if (smallest !=idx){
swap(bucket[smallest], bucket[idx]);
min_heapify(bucket, smallest);
}
}
//construct heap
void construct_min_heap(vector<pair<int, int>>& bucket){
heap_size = bucket.size();
for (int i=(heap_size << 1)-1; i >=0; i--){
min_heapify(bucket, i);
}
}

void get_kth_element_sorted(vector<pair<int, int>>& bucket, int k){
construct_min_heap(bucket);
for (int i=0; i < k; i++) {
swap(bucket[heap_size-1], bucket[0]);
heap_size--;
min_heapify(bucket, 0);
}
}
private:
int heap_size;
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.