57

プライオリティ キューは、挿入、削除、トップなどの通常のキュー操作を備えた単なるヒープのようです。これはプライオリティ キューを解釈する正しい方法ですか? さまざまな方法でプライオリティ キューを構築できることは知っていますが、ヒープからプライオリティ キューを構築する場合、プライオリティ キュー クラスを作成し、ヒープとキュー操作を構築するための指示を与える必要がありますか、それとも構築する必要はありませんか?クラス?

つまり、ヒープを構築する関数と、挿入や削除などの操作を行う関数がある場合、これらすべての関数をクラスに配置する必要がありますか、またはmain.

私の質問は、関数のコレクションを持つことは、それらをいくつかのクラスに格納してクラスを介して使用することと同等か、または単に関数自体を使用することと同等かということだと思います。

私が以下に持っているのは、プライオリティ キューの実装のためのすべてのメソッドです。これは実装と呼ぶのに十分ですか、それとも指定された優先キュー クラスに入れる必要がありますか?

#ifndef MAX_PRIORITYQ_H
#define MAX_PRIORITYQ_H
#include <iostream>
#include <deque>
#include "print.h"
#include "random.h"

int parent(int i)
{
    return (i - 1) / 2;
}

int left(int i)
{
    if(i == 0)
        return 1;
    else
        return 2*i;
}

int right(int i)
{
    if(i == 0)
        return 2;
    else
        return 2*i + 1;
}

void max_heapify(std::deque<int> &A, int i, int heapsize)
{
    int largest;
    int l = left(i);
    int r = right(i);
    if(l <= heapsize && A[l] > A[i])
        largest = l;
    else
        largest = i;
    if(r <= heapsize && A[r] > A[largest])
        largest = r;
    if(largest != i) {
        exchange(A, i, largest);
        max_heapify(A, largest, heapsize);
        //int j = max_heapify(A, largest, heapsize);
        //return j;
    }
    //return i;
}

void build_max_heap(std::deque<int> &A)
{
    int heapsize = A.size() - 1;
    for(int i = (A.size() - 1) / 2; i >= 0; i--)
        max_heapify(A, i, heapsize);
}

int heap_maximum(std::deque<int> &A)
{
    return A[0];
}

int heap_extract_max(std::deque<int> &A, int heapsize)
{
    if(heapsize < 0)
        throw std::out_of_range("heap underflow");
    int max = A.front();
    //std::cout << "heapsize : " << heapsize << std::endl;
    A[0] = A[--heapsize];
    A.pop_back();
    max_heapify(A, 0, heapsize);
    //int i = max_heapify(A, 0, heapsize);
    //A.erase(A.begin() + i);
    return max;
}

void heap_increase_key(std::deque<int> &A, int i, int key)
{
    if(key < A[i])
        std::cerr << "New key is smaller than current key" << std::endl;
    else {
        A[i] = key;
        while(i > 1 && A[parent(i)] < A[i]) {
            exchange(A, i, parent(i));
            i = parent(i);
        }
    }
}

void max_heap_insert(std::deque<int> &A, int key)
{
    int heapsize =  A.size();
    A[heapsize] = std::numeric_limits<int>::min();
    heap_increase_key(A, heapsize, key);
}
4

6 に答える 6

177

プライオリティ キューは抽象データ型です。これは、特定のインターフェイスと動作を簡単に説明する方法であり、基礎となる実装については何も述べていません。

ヒープはデータ構造です。これは、特定の操作を非常に効率的にするデータを格納する特定の方法の名前です。

ヒープ データ構造によって効率化される操作は、プライオリティ キュー インターフェイスが必要とする操作であるため、ヒープはプライオリティ キューを実装するのに非常に適したデータ構造です。

于 2013-09-24T22:40:02.650 に答える
13

まさに必要なインターフェイス (insert と pop-max だけ?) を備えたクラスを持つことには利点があります。

  • 後で実装を交換できます (たとえば、ヒープではなくリスト)。
  • キューを使用するコードを読む人は、ヒープ データ構造のより難しいインターフェイスを理解する必要はありません。

私の質問は、関数のコレクションを持つことは、それらを何らかのクラスに格納してクラスを介して使用することと同等か、または単に関数自体を使用することと同等かということだと思います。

「私のプログラムがどのように動作するか」という観点から考えれば、ほとんど同じです。しかし、「私のプログラムが人間の読者にとってどれだけ簡単に理解できるか」という点では同等ではありません。

于 2013-09-24T22:39:46.287 に答える
4

プライオリティ キューという用語は、その要素のプライオリティを順序付けるのに役立つ一般的なデータ構造を指します。これを実現する方法は複数あります。たとえば、さまざまな順序付けられたツリー構造 (たとえば、スプレイ ツリーが適切に機能します) や、d ヒープやフィボナッチ ヒープなどのさまざまなヒープがあります。概念的には、ヒープは、すべてのノードの重みが、そのノードでルーティングされるサブツリー内のノードの重みよりも小さくないツリー構造です。

于 2013-09-24T22:42:48.077 に答える
3

C++ 標準テンプレート ライブラリは、ヒープ (通常はバイナリ ヒープとして実装される) の make_heap、push_heap、および pop_heap アルゴリズムを提供します。これらは、任意のランダム アクセス反復子で動作します。イテレータを配列への参照として扱い、配列からヒープへの変換を使用します。また、コンテナのようなクラスでこれらの機能をラップするコンテナ アダプタ priority_queue も提供します。ただし、減少/増加キー操作の標準サポートはありません。

priority_queueは、実行される操作によって完全に定義された抽象データ型を指します。prioroty_queueしたがって、C++ STL では、シーケンス アダプターの 1 つです。つまり、基本的なコンテナーのアダプター (ベクトル、リスト、およびデキューは、効率を失うことなく相互に構築することができないため、基本的なものです) であり、<queue>ヘッダーで定義されます (<bits/stl_queue.h>私の場合は実際に)。その定義からわかるように (Bjarne Stroustrup が言うように):

コンテナ アダプタは、コンテナへの制限されたインターフェイスを提供します。特に、アダプターは反復子を提供しません。これらは、専用のインターフェースを介してのみ使用することを意図しています。

私の実装prioroty_queueでは、次のように説明されています

/**
   *  @brief  A standard container automatically sorting its contents.
   *
   *  @ingroup sequences
   *
   *  This is not a true container, but an @e adaptor.  It holds
   *  another container, and provides a wrapper interface to that
   *  container.  The wrapper is what enforces priority-based sorting 
   *  and %queue behavior.  Very few of the standard container/sequence
   *  interface requirements are met (e.g., iterators).
   *
   *  The second template parameter defines the type of the underlying
   *  sequence/container.  It defaults to std::vector, but it can be
   *  any type that supports @c front(), @c push_back, @c pop_back,
   *  and random-access iterators, such as std::deque or an
   *  appropriate user-defined type.
   *
   *  The third template parameter supplies the means of making
   *  priority comparisons.  It defaults to @c less<value_type> but
   *  can be anything defining a strict weak ordering.
   *
   *  Members not found in "normal" containers are @c container_type,
   *  which is a typedef for the second Sequence parameter, and @c
   *  push, @c pop, and @c top, which are standard %queue operations.
   *  @note No equality/comparison operators are provided for
   *  %priority_queue.
   *  @note Sorting of the elements takes place as they are added to,
   *  and removed from, the %priority_queue using the
   *  %priority_queue's member functions.  If you access the elements
   *  by other means, and change their data such that the sorting
   *  order would be different, the %priority_queue will not re-sort
   *  the elements for you.  (How could it know to do so?)

テンプレート:

  template<typename _Tp, typename _Sequence = vector<_Tp>,
       typename _Compare  = less<typename _Sequence::value_type> >
    class priority_queue
    {

これとは対照的に、ヒープはその要素がどのようにフェッチされ、メモリに格納されているかを表します。これは (ツリーベースの) データ構造であり、その他は配列、ハッシュ テーブル、構造体、ユニオン、セットなどであり、さらにヒープ プロパティを満たします。すべてのノードは [以上] または [以下] のいずれかです。 equal to] ヒープに定義された比較述語に従って、その子のそれぞれ。

したがって、ヒープヘッダーにはヒープコンテナーはなく、一連のアルゴリズムが見つかります

  /**
   * @defgroup heap_algorithms Heap Algorithms
   * @ingroup sorting_algorithms
   */ 

お気に入り:

  • __is_heap_until
  • __is_heap
  • __push_heap
  • __調整_ヒープ
  • __pop_heap
  • make_heap
  • sort_heap

それらのすべて (__is_heap を除き、「この関数は拡張機能であり、C++ 標準の一部ではありません」とコメントされています) として説明されています。

   *  @ingroup heap_algorithms
   *
   *  This operation... (what it  does)
于 2013-09-25T00:11:37.957 に答える
0

Not really. The "priority" in the name stems from a priority value for the entries in the queue, defining their ... of course: priority. There are many ways to implement such a PQ, however.

于 2013-09-24T22:39:27.197 に答える