0

ヒープとルート要素のリンクされた構造の実装で最も遠い要素を見つける方法を考えていました。要素を Enque および Deque できるようにしたい。

いくつかの明確化: 私が意味したのは、リンクされた構造が最大ヒープを構成しているとしましょう (ルート要素が最大の値を持っています)。ツリーの一番下のどこかに要素があり、エンキューしているかデキューしているかに応じて、後で挿入または削除します。その要素をどのように決定しますか？また、ツリーのルート ノードをどのように決定しますか? (一番上)

4

3 に答える 3

1

これがあなたが求めているものであることに完全に肯定的ではありませんが、これは片方向リストの最後の要素を指す1つの方法です:

T *p = NULL, *q = NULL;  // q follows p by one node
p = root;
while (p)
{
    q = p;
    p = p -> next;
}

// q now points to last node
于 2009-12-10T19:28:00.913 に答える
0

たぶん、このようなものですか？

struct node {
  node *parent;
  node *children[2];
  int data; //or whatever else you want
};

struct heap {
  node *root;
  node *last;
};

ただし、これを実装するのは、配列を使用するよりもはるかに複雑です。ここに仮想の追加があります

void add(struct heap* h, int d)
{
  node* add = malloc(sizeof(node));
  add->data = d;
  node* current = h->root;
  while(current->children[1]) current = current->children[1];
  current->children[1] = add;
  add.parent = current;
  add.children[0] = NULL;
  add.children[1] = NULL; 
  h.last = add;
  percolate_up(h);
}

そんな感じ。

于 2009-12-10T20:28:15.893 に答える
0

ヒープ構造に何かを追加する通常の方法は、ルートから開始し、ツリーを「たどって」新しい要素が配置される場所を見つけることです。どこに行くかを見つけたら、そこに置きます。それがその場所に既にあるものを置き換えることを意味する場合は、以前の値を取得して、下に移動し続けてどこに行くかを見つけます。葉に当たるまで繰り返し、その葉の適切な子として「運ぶ」値を追加します。

新しい値が 5 で、ヒープのルート ノードが 10 を保持していたとします。5 は明らかに 10 を下回るので、10 の子を調べます。それらが 8 と 7 であるとします。どちらも 5 より大きいので、1 つを選択します (どのように選択するかは、ヒープのバランスを維持しようとしているかどうかによって異なります)。7 を選択し、子 3 と 4 があるとします。5 は 7 より下ですが、3 または 4 より上なので、たとえば 4 を 5 に置き換え、そのノードの子を調べて 4 をどこに置くかを確認します。には子がありません。4 を含む新しいリーフを追加するだけです。

ルートを見つける方法についての質問については、通常、ルートは、保持しているツリーへの唯一のポインターです。これは、すべての操作の開始点です。別の場所から始めた場合は、ルートまで移動できると思いますが、その理由は疑問です。

于 2009-12-10T20:42:02.260 に答える