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

Question

Почему куча времени выполнения используется для динамического распределения памяти в языках C-стиля и структура данных оба называются «кучей»?Есть ли какое-то отношение?

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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

Возможно, самое раннее использование куча поскольку структура данных обнаружена семью годами ранее в
Уильямс, Дж.В.Дж.1964.«Алгоритм 232 — пирамидальная сортировка», Коммуникации ACM 7(6): 347-348

Answer 4

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

Answer 5

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

Answer 6

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

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

Answer 7

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

Больше можно найти на Раздел «Продолжительность хранения» стандарта.

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

Answer 8

К.Что такое куча?А.Куча — это совокупность объектов, расположенных друг на друге.

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

Answer 9

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