в чем преимущество карты перед кучей в с ++

Question

В настоящее время я занимаюсь проблемой структуры данных, и у меня есть вопрос, в котором я должен найти k-й по величине элемент в массиве.реальная проблема здесь: https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/.

я сделал этот вопрос двумя разными способами, используя кучу, а второй использует карту.

мое решение с помощью карты.

   int t;
cin>>t;
while(--t>=0){
int n,k;
cin>>n;
vector<int> A(n);
for(int i=0;i<n;i++){
cin>>A[i];
 }
cin>>k;
map<int,int> m;
for(int i=0;i<n;i++){
    m[A[i]]++;
}
auto it=m.begin();
for(int i=1;i<=k-1;i++){
    it++;
}
cout<<it->first<<endl;

но мое решение для карты дает превышение лимита времени.по моему мнению, решение для карты также имеет временную сложность (n + klog (n)), такую ​​же, как решение для кучи.так почему решение карты дает TLE?

Answer 1

Сложность времени для вашего решения с использованием карт будет O (k + nlog (n)).Каждая вставка в std::map занимает время log (n), и вы выполняете 'n' вставки.Временная сложность только для вставки потребует времени O (nlog (n)).

См. http://www.cplusplus.com/reference/map/map/insert/ для получения дополнительной информации о вставке элементов в std::map.

Answer 2

Не видя вашу кучную версию, я бы предположил, что причиной проблемы является распределение карты. Каждому узлу требуется выделение, что подразумевает блокировку и дополнительное управление.

И вы должны следовать указателям внутри структуры данных карты, чего обычно не бывает в кучах.

В больших обозначениях O это ничего не добавляет к времени, но на практике каждый может значительно замедлить программу.