1

我有一个对象向量Nx。NyA

  • A有成员a和b.
  • 如果成员b满足特定条件，则将其添加到指针向量中heapItem。
  • 然后我想使用该函数std::make_heap来创建一个最小堆。

然后，在我的代码中，我想更改A[i][j].b堆中存在的值，并希望堆反映这些更改。

为此，我需要编写一个filterUp和filterDown例程。我的问题是我不知道A[i][j].b堆中的位置。有什么方法可以找到或另一种方法来编写trickleUp&trickleDown例程？我不想经常调用该make_heap函数，因为它可能代价高昂。

#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>

struct A
{
  A(){}

  A(int av, int bv):a(av),b(bv){}

  int a, b;
};

struct MinHeap
{
    bool operator()(const A* lhs, const A* rhs) const
    {
        return lhs->b > rhs->b;
    }
};

int main()
{
  int Nx=4;
  int Ny=3;
  int cnt=0;
  std::vector<A*> heapItem;

  A gridPt[Nx][Ny];  
  for(int i=0; i<Nx; ++i)  // initialize grid of A objects
  {
    for(int j=0; j<Ny; ++j)
    {
      gridPt[i][j].a=i*(-j)+2*j+i+j;
      gridPt[i][j].b=i+j*(-2)+4;

      if(gridPt[i][j].b>0)  // add selected A objects to heap
      { 
          heapItem.push_back(&gridPt[i][j]);
          cnt++;
      }
    }
  }

    std::make_heap(heapItem.begin(), heapItem.end(), MinHeap());  //make heap

    gridPt[1][2].b=3; //this object is in heap. need to call a filterUp or filterDown routine to retain min heap structure

    int count=0;
    for(int i=0; count<heapItem.size(); ++i)
    {
        for(int j=0; j<pow(i,2) && count<heapItem.size(); ++j)
        {
            std::cout << heapItem[count++]->b << "   ";
        }
        std::cout << std::endl;
    }

    //make_heap, push_heap, pop_heap maintain min heap structure

  return 0;

}
4

1 回答 1

0

你有一堆 A* 指针。您需要堆中 A* obj 的索引，以便在操作 obj 后保留堆结构。除了搜索整个堆之外，没有其他方法可以得到它。以下是一些选项：

  1. 只操作堆顶，这里很明显如何获取索引。这就是您应该使用非侵入式堆的方式。
  2. 实现您自己的侵入式堆，其中结构 A 有一个索引成员。您需要自己的堆函数来更新它。
于 2012-11-27T07:16:09.243 回答