c++ - 高性能堆排序

Question

我有一个大小超过500万的vector，每次我想从vector中取出一个键值最小的元素，然后对这个元素做一些处理。然而，随着这个特定元素的处理， vector 中的所有剩余元素也将受到影响，以便它们的键更新。所以下次如果我想从 vector 中取出具有最小键的元素，我必须再次对 vector 进行排序。问题是从vector中取出最小元素的个数会高达50万个，所以程序运行很慢。为了让大家更清楚的理解，我可以编写如下代码来说明:

void function(vector<MyObj*>& A)
{ //A.size() is near 5 million, maybe even more such as 50 million.
    make_heap(A.begin(), A.end(), compare); // compare function is self-defined.
    for (int i=0; i<500000; i++)
    {
        MyObj* smallest_elem = A.front();
        pop_heap(A.begin(), A.end());
        A.pop_back();
        Process_MyObj(smallest_elem); // here all of the elements 
                                      // in A will be affect, causing 
                                      // their keys changed.

        make_heap(A.begin(), A.end()); // Since all elements' keys in A changed,
                                       // so heap sorting A once again is 
                                       // necessary in my viewpoint.
    }
}

有什么方法可以让代码尽可能高效地运行？欢迎任何想法，不限于算法的改进，例如并行或其他任何东西。非常感谢!

Answer 1

如果 Process_MyObj 确实影响了 A 中所有元素的键，我认为您无能为力。如果它只修改了一些键，您可以编写代码来更新堆中的单个元素。

正如您现在的代码一样，我看不到您从构建堆中获得了什么。我只会进行线性扫描以找到最小元素，将其与最后一个元素交换，然后弹出最后一个元素。