c++ - 为 make_heap 编写 trickleUp 和 trickleDown 例程

Question

我有一个 Nx by Ny 对象 A vector 。

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

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

为此，我需要编写一个 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;

}

Answer 1

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

1. 只操作堆的顶部，那里很明显如何获得索引。这就是您应该如何使用非侵入式堆。
2. 实现你自己的侵入式堆，其中结构 A 有一个索引成员。您需要自己的堆函数来更新它。