реализация приоритетных очередей и куч
Я пытаюсь реализовать очередь с минимальным приоритетом, используя двоичную кучу мин, основанную на описании из «Введение в алгоритмы, третье издание», и у меня есть пара вопросов.
В книге говорится, что нам часто нужно хранить дескриптор (указатель или целое число) для объекта приложения в каждом элементе кучи и что нам также необходимо сохранять дескриптор (индекс массива) для элемента кучи в каждом объекте приложения.
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 вообще.
Суть вопроса заключается в реализации куч / приоритетных очередей для собеседований. Есть мысли по этому поводу?
Решение
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 на векторе.
Другие решения
Других решений пока нет …