1

オブジェクトのNxbyNyベクトルがありますA。

  • Aメンバーaとb。
  • メンバーbが特定の基準を満たしている場合、それはポインターのベクトルに追加されますheapItem。
  • 次に、この関数std::make_heapを使用して最小ヒープを作成します。

次に、私のコードで、ヒープ内のA[i][j].bpresentの値を変更し、ヒープにこれらの変更を反映させたいと思います。

このために、私は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* ポインターのヒープがあります。obj を操作した後にヒープ構造を保持するには、ヒープ内の A* objのインデックスが必要です。ヒープ全体を検索する以外に取得する方法はありません。以下にいくつかのオプションを示します。

  1. インデックスを取得する方法が明らかなヒープのトップのみを操作してください。これは、邪魔にならないヒープを使用する方法です。
  2. 構造体 A にインデックス メンバーがある独自の侵入型ヒープを実装します。それを更新する独自のヒープ関数が必要です。
于 2012-11-27T07:16:09.243 に答える