реализация приоритетных очередей и куч

Я пытаюсь реализовать очередь с минимальным приоритетом, используя двоичную кучу мин, основанную на описании из «Введение в алгоритмы, третье издание», и у меня есть пара вопросов.

В книге говорится, что нам часто нужно хранить дескриптор (указатель или целое число) для объекта приложения в каждом элементе кучи и что нам также необходимо сохранять дескриптор (индекс массива) для элемента кучи в каждом объекте приложения.

1) Будет ли реализация кучи обычно выглядеть примерно так?

template <class KeyType, class ObjectType>
struct HeapElement
{
KeyType key;
ObjectType* pObject;
};template <class KeyType, class ObjectType>
class MinHeap
{
// ...
private:
std::vector< HeapElement<KeyType, ObjectType> > data;
};

И тогда класс ObjectType также будет хранить heapIndex:

class Foo
{
// ...
int heapIndex;
};

2) Очередь с минимальным приоритетом и двоичная минимальная куча, как правило, реализуются как один класс, или очередь с минимальным приоритетом обычно реализуется как собственный класс с закрытым членом класса кучи?

class MinPriorityQueue
{
// ...
private:
MinHeap minHeap;
};

Я спрашиваю, потому что, если вы посмотрите на реализацию чего-то вроде ExtractMin()требуется, чтобы вы манипулировали данными кучи:

int min = data[0]; // data: private heap data member
heapSize--; // heapSize: private heap data member
MinHeapify(0); // MinHeapify: private heap member function

Так, может, класс очереди с минимальным приоритетом должен действовать как класс-оболочка?

T MinPriorityQueue::ExtractMin()
{
return minHeap.ExtractMin();
}

В этом случае двоичный класс min heap может реализовать Min(), ExtractMin(), DecreaseKey(), а также Insert() и содержат функциональные возможности для двоичной минимальной кучи и очереди с минимальным приоритетом. Тогда не было бы необходимости в классе MinPriorityQueue вообще.

Суть вопроса заключается в реализации куч / приоритетных очередей для собеседований. Есть мысли по этому поводу?

0

Решение

1) Обычно вам не нужно изменять типы значений только потому, что вы хотите создать из них кучу. Вы бы сделали свою кучу примерно так:

template <class KeyType, class ObjectType>
struct HeapElement
{
KeyType key;
size_t heapIndex;
ObjectType* pObject;
};template <class KeyType, class ObjectType>
class MinHeap
{
// ...
private:
//this is just to allocate the data.  Elements in here don't move
std::vector< HeapElement<KeyType, ObjectType> > data;

//this is the heap.  Elements are indexes into data vector
std::vector<size_t> heapArray;
};

Затем в ходе реализации алгоритма Дейкстры вы используете индексы в векторе данных для ссылки на объекты, и вы можете получить индекс кучи каждого элемента с помощью data[itemIndex].heapIndex,

НО смотри мой ответ здесь: Алгоритм Прима: Как получить индекс ключа, для которого должна выполняться операция DECREASE_KEY? … Я обычно реализую алгоритм Дейкстры без операция уменьшения_ключа.

2) Я на самом деле не вижу никакой причины создавать класс кучи, отдельный от реализации очереди приоритетов. Я бы на самом деле назвал класс, который вам нужен, «куча», но не приоритетная очередь, поскольку интерфейсы приоритетной очереди обычно не ожидают, что ключи будут отделены от объектов.

Вы должен использование std::make_heap, std::push_heap а также std::pop_heap на векторе.

0

Другие решения

Других решений пока нет …