Почему две разные концепции называются "кучей"?

Ответ 1

Дональд Кнут говорит ( "Искусство компьютерного программирования", "Третье издание", том 1, стр. 435):

Несколько авторов начали с 1975 года называть пул доступной памяти "кучей".

Он не говорит, какие авторы и не дает ссылок на какие-либо конкретные документы, но говорит, что использование термина "куча" в отношении очередей приоритетов является традиционным смыслом слова.

Ответ 2

Они имеют одно и то же имя, но они действительно не похожи (даже концептуально). Куча памяти называется кучей так же, как вы относитесь к корзине для белья как к "куче одежды". Это имя используется, чтобы указать на несколько грязное место, где память может быть выделена и освобождена по желанию. Структура данных (так как ссылка Википедии, на которую вы ссылаетесь) совершенно другая.

Ответ 3

Столкновение имен является неудачным, но не все таинственным. Куча - это небольшое общее слово, используемое для обозначения кучи, коллекции, группы и т.д. Использование слова для предварительной структуры данных (я уверен) - имя пула памяти. На самом деле, по моему мнению, пул был бы намного лучшим выбором для последнего. Куча означает вертикальную структуру (например, кучу), которая соответствует структуре данных, но не пул памяти. Мы не считаем кучу памяти пустым как иерархическую, тогда как фундаментальная идея структуры данных заключается в том, что наибольший элемент находится в верхней части кучи (и подвалов).

Куча структуры данных датируется серединой 60-х годов; куча пула памяти, начале 70-х. Термин куча (означающий пул памяти) использовался, по крайней мере, еще в 1971 году Wijngaarden в обсуждениях Algol.

Возможно, самое раннее использование кучи в качестве структуры данных найдено семь лет назад в
Уильямс, J. W. J. 1964. "Алгоритм 232 - Хепсорт", Связь ACM 7 (6): 347-348

Ответ 4

Собственно, чтение о распределении памяти (см. Buddy Blocks) напоминает мне кучу в структурах данных.

Ответ 5

ИМО это просто случайность/совпадение, что эти две совершенно не связанные вещи имеют одно и то же имя. Это как график и график.

Ответ 6

Структура данных в виде кучи используется алгоритмом нахождения доступного распределения памяти. Ниже приведено от http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html.

Когда вызывается new, он начинает искать свободный блок памяти, который соответствует размеру вашего запроса. Предположим, что такой блок памяти найден, он помечен как зарезервированный и возвращается указатель на это местоположение. Существует несколько алгоритмов для достижения этого, потому что необходимо выполнить компромисс между сканированием всей памяти для поиска наименьшего свободного блока, большего, чем размер вашего объекта, или возврата первого, где требуется память. Чтобы повысить скорость получения блока памяти, свободные и зарезервированные области памяти сохраняются в структуре данных, подобной бинарным деревьям, называемым кучей.

Ответ 7

Разговорные термины стековая память и кучная память не используются в стандарте C++. Стандарт использует статическое хранение, хранение потоков, автоматическое хранение и динамическое хранение.

Более подробную информацию можно найти в разделе "Стандарт хранения".

Следовательно, с точки зрения языка и стандартной библиотеки нет никакой путаницы.

Ответ 8

Q. Что такое куча? A. Куча - это набор объектов, расположенных друг над другом.

Ответ на ваш вопрос: и куча памяти, и двоичная куча используют ту же концепцию, что и вы. Данные хранятся в виде кучи в памяти в том же порядке, в котором они записаны в программе, тогда как бинарная куча - это структура данных, которая следует той же концепции хранения данных в упорядоченном виде в виде кучи (данные сверху другого). Дайте мне знать, что вы думаете в разделе комментариев.

Ответ 9

Возможно, первая реализованная куча памяти управлялась структурой кучи?