алгоритм — Создание принципов кучи — реализация в переполнении стека
У меня проблемы с домашней работой. Меня попросили реализовать приоритетную очередь, используя кучу в C ++.
При поиске примеров кода для создания кучи я встречался много раз в этом определении:
Массив это представляет кучу массив с двумя атрибутами:
— длина, количество элементов в массиве
— кучного размера, количество элементов кучи, хранящихся в массиве
Итак, мой вопрос заключается в следующем: что ? мне нужно реализовать это самостоятельно (скажем, сделать кучу классов, которая содержит 3 поля — массив элементов, длину и размер кучи)?
Я просто не знаю с чего начать.
Решение
Структура данных двоичной кучи обычно рисуется в виде двоичного дерева с определенными свойствами, но обычно реализуется с использованием простого массива. Причина этого заключается в том, что версия массива использует меньше памяти, чем явное двоичное дерево, и ее намного проще манипулировать. Следовательно, массив Вы видите, что описан массив, который содержит все значения в куче.
Два поля, которые вы видите, представляют общий размер этого массива (длина), который отслеживает, сколько места для хранения доступно, и количество элементов в этом массиве, который вы фактически используете (кучного размера). Когда вы вставляете элемент в кучу, вам нужно убедиться, что для него есть место, возможно, перераспределить массив, чтобы он был больше, и скопировать поверх существующих элементов, а затем нужно будет запустить операцию всплывающего окна для вставки нового элемента. в кучу.
Однако, как правило, вы обходите логику поддержки массива и этих двух полей, размещая кучу поверх динамического массива, например C ++. std::vector или Java ArrayList, Таким образом, логика для отслеживания пространства хранения и увеличения массива обрабатывается для вас автоматически.
В зависимости от параметров присваивания, поскольку это делается в C ++, вы можете заглянуть в std::make_heap, std::push_heap, а также std::pop_heap алгоритмы из <algorithm> заголовок. Они позволяют легко реализовать кучу поверх существующего контейнера, такого как std::vector, На самом деле, это как std::priority_queue класс обычно реализуется.
Если вам нужно реализовать операции с кучей самостоятельно, вы можете проверить описание двоичной кучи, приведенное в этом раздаточном материале, который, кажется, близко соответствует заданию, которое вам дали.
Надеюсь это поможет!
Другие решения
Других решений пока нет …