Можно ли создать кучу мин / макс, не зная окончательного размера?

Question

Я пытаюсь написать программу, которая изучит пространство состояний простой игры.

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

Но какой это должен быть размер кучи? Максимальное количество состояний, которое может быть сгенерировано, равно 9 !, я думаю, что это довольно много. Как это сделать, если я не хочу выделять это огромное пространство памяти сразу?

Я кодирую это в C. Есть идеи?

Answer 1

Предполагается, что вам нужно хранить одно целочисленное значение для каждого состояния. Общий размер = 9! * sizeof int (4 байта) = 1,384 МБ. Это не так много! Также, если нет внутреннего цикла для вычисления состояний, тогда временная сложность должна быть O (10 ^ 6) и должна вычисляться за несколько миллисекунд.

Да. Вы можете создать кучу, не зная окончательного размера. Просто используйте связанный список и динамическое распределение памяти.