-4

我必须使用一种数据结构来保持元素以某种顺序排列，这样我就可以查询最少的元素并有效地插入新元素。所以我选择了 set ( C++ stl). 插入和删除最少元素需要log(n)时间。log(n)

所以我写了以下程序：

#include<iostream>
#include<set>
#include<stdio.h>
using namespace std;
int main()
{
   set<int>s1,s2;
   set<int>::iterator it;
   int tmp,i;
   for(i=1;i<=1000000;i++)s1.insert(i);
   for(i=1;i<=1000000;i++)
   {
      it=s1.begin();
      s2.insert(*it);
      s1.erase(s1.begin());
   }
return 0;
}

但这在我的机器（ i core 31.67 ）上需要几秒钟，我预计会少得多，即我尝试了优先级队列，它也给了我相同的性能。那么我应该实现自己的堆以使其更快还是有其他方法？O(log(1000000)*1000000)2*10^7

4

3 回答 3

9

您正在做的是平衡二叉搜索树可能遭受的最困难的事情之一。您一直在树的最右侧插入项目并从最左侧继续删除项目，使树总是必须重新平衡自己。

于 2013-06-02T08:24:02.400 回答
4

有一个名为的模板priority_queue可以更好地处理您描述的工作负载。它是一个最大堆，而不是最小堆，但它允许您将自定义比较器作为模板参数传递。它是通过在通常是vector.

set实现为平衡二叉树。这意味着每次插入和查询都涉及 log2(n) 高度非本地的内存访问；将其视为 log2(n) 缓存未命中。堆做得更好。这些在现代处理器上尤其粗糙，当您驯服内存访问模式时，经常会看到较大的常数因子加速。

于 2013-06-02T08:20:31.170 回答
0 
class heap
{
   int heap[1000001],siz;
   public:
   int ini()
   {
      siz=0;
   }
   int size()
   {
      return siz;
   }
   int top()
   {
     return heap[1];
   }
  void insert(int num)
  {
     siz++;
     heap[siz]=num;
     int pos=siz,tmp;
     while(pos>1)
     {
    if(heap[pos]<heap[pos/2])
    {
       tmp=heap[pos];
       heap[pos]=heap[pos/2];
       heap[pos/2]=tmp;
    }
    else break;
     }
  }
  void del()
  {
     if(siz==1)
     {
    siz=0;
    return;
     }
     heap[1]=heap[siz];
     siz--;
     int pos=1,tmp;
     while(2*pos<=siz)
     {
    if(2*pos+1<=siz)
    {
       if(heap[2*pos]<=heap[2*pos+1])
       {
          if(heap[pos]>heap[2*pos])
          {
         tmp=heap[pos];
         heap[pos]=heap[2*pos];
         heap[2*pos]=tmp;
         pos=2*pos;
          }
          else break;
       }
       else if(heap[2*pos+1]<=heap[2*pos])
       {
          if(heap[pos]>heap[2*pos+1])
          {
         tmp=heap[pos];
         heap[pos]=heap[2*pos+1];
         heap[2*pos+1]=tmp;
         pos=2*pos+1;
          }
          else break;
       }
    }
    else 
    {

       if(heap[pos]>heap[2*pos])
       {
          tmp=heap[pos];
          heap[pos]=heap[2*pos];
          heap[2*pos]=tmp;
          pos=2*pos;
       }

       else break;

    }
     }
  }

};
int main()
{
   int i,tmp;
   heap a1,a2;
   a1.ini();a2.ini();
   for(i=1;i<=1000000;i++)a1.insert(i);
   for(i=1;i<=1000000;i++)
   {
      tmp=a1.top();
      a2.insert(tmp);
      a1.del();
   }
}

我实现了自己的堆，并在现在 0.25 秒内完成了相同的操作。我想确实是内存分配和释放使设置变慢。

于 2013-06-02T16:12:11.720 回答