Разница между приоритетной очередью и кучей

Кажется, что очередь приоритетов - это просто куча с обычными операциями очереди, такими как insert, delete, top и т.д. Является ли это правильным способом интерпретации очереди приоритетов? Я знаю, что вы можете создавать очереди приоритетов по-разному, но если бы я должен был создать очередь приоритетов из кучи, необходимо создать класс очереди приоритетов и дать инструкции для построения кучи и операций очереди или нет необходимости строить класс?

Я имею в виду, если у меня есть функция для создания кучи и функций для выполнения операций, таких как insert, delete, мне нужно поместить все эти функции в класс или я могу просто использовать инструкции, вызвав их в 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);
}

Ответы

Ответ 1

Имея класс с именно необходимым интерфейсом (просто вставкой и pop-max?), у него есть преимущества.

  • Вы можете обменять реализацию (список вместо кучи, например) позже.
  • Кому-то, читающему код, который использует очередь, не нужно понимать более сложный интерфейс структуры данных кучи.

Я думаю, мой вопрос заключается в том, имеет ли набор функций эквивалент их хранения в каком-либо классе и использование их через класса или просто используя сами функции.

Это в основном эквивалентно, если вы просто думаете с точки зрения "как работает моя программа". Но это не эквивалентно с точки зрения "насколько легко моя программа понятна человеческому читателю".

Ответ 2

Приоритетная очередь представляет собой абстрактный тип данных . Это сокращенный способ описания конкретного интерфейса и поведения и ничего не говорит о базовой реализации.

Куча - это структура данных . Это имя для конкретного способа хранения данных, что делает определенные операции очень эффективными.

Так получилось, что куча - очень хорошая структура данных для реализации очереди приоритетов, потому что операции, которые становятся эффективными с помощью структуры данных кучи, - это операции, которые требуется интерфейсу очереди приоритетов.

Ответ 3

Термин приоритет относится к общей структуре данных, полезной для упорядочивания приоритетов ее элемента. Есть несколько способов достижения этого, например, различные упорядоченные древовидные структуры (например, дерево воспроизведения) достаточно хорошо, а также различные кучи, например, d-кучи или кучи Фибоначчи. Концептуально куча представляет собой древовидную структуру, где вес каждого node не меньше веса любого node в поддереве, направленном на этот node.

Ответ 4

Стандартная библиотека шаблонов С++ предоставляет make_heap, push_heap и алгоритмы pop_heap для куч (обычно реализуются как двоичные кучи), которые работают с произвольными итераторами произвольного доступа. Он лечит итераторы в качестве ссылки на массив, и использует массив в кучу преобразование. Он также обеспечивает приоритет_коррекции контейнера, который переносит эти объекты в контейнерный класс. Однако там не является стандартной поддержкой операции уменьшения/увеличения.

priority_queue ссылается на абстрактный тип данных, полностью определяемый операциями, которые могут выполняться на нем. Таким образом, в С++ STL prioroty_queue является одним из адаптеров последовательности - адаптеры базовых контейнеров (вектор, список и deque являются базовыми, поскольку они не могут быть построены друг от друга без потери эффективности), определенных в <queue> header (<bits/stl_queue.h> в моем случае на самом деле). Как видно из его определения (как говорит Бьярне Страуструп):

контейнерный адаптер обеспечивает ограниченный интерфейс для контейнера. В в частности, адаптеры не предоставляют итераторов; они должны быть используются только через их специализированные интерфейсы.

В моей реализации 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 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
    {

В противоположность этому куча описывает, как ее элементы извлекаются и хранятся в памяти. Это (древовидная) структура данных, другие - это массив, хэш-таблица, структура, объединение, множество..., что дополнительно удовлетворяет heap: все узлы либо [больше или равно], либо [меньше или равно] каждому из своих дочерних элементов в соответствии с предикатом сравнения, определенным для кучи.

Итак, в моем куче кучи я не нахожу контейнер кучи, а набор алгоритмов

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

как:

  • __ is_heap_until
  • __ is_heap
  • __ push_heap
  • __ adjust_heap
  • __ pop_heap
  • make_heap
  • sort_heap

все из них (исключая __is_heap, прокомментированные как "Эта функция является расширением, а не частью стандарта С++" ), описанным как

   *  @ingroup heap_algorithms
   *
   *  This operation... (what it  does)

Ответ 5

Не совсем. "Приоритет" в названии зависит от значения приоритета для записей в очереди, определяя их... конечно: приоритет. Однако есть много способов реализовать такой PQ.