Почему куча времени выполнения используется для динамического выделения памяти в языках стиля C и структура данных как называется "кучей"? Есть какая-то связь?
Почему две разные концепции называются кучей?
Ответы (9)
Дональд Кнут говорит (Искусство программирования, третье издание, том 1, стр. 435):
Некоторые авторы примерно в 1975 году начали называть пул доступной памяти «кучей».
Он не говорит, каких авторов, и не дает ссылок на какие-либо конкретные статьи, но говорит, что использование термина «куча» в отношении очередей с приоритетом является традиционным смыслом этого слова.
У них одинаковое имя, но на самом деле они не похожи (даже концептуально). Куча памяти называется кучей так же, как вы называете корзину для белья «кучей одежды». Это имя используется для обозначения беспорядочного места, где память может быть выделена и освобождена по желанию. Структура данных (как указывает ссылка на Википедию, на которую вы ссылаетесь) совершенно иная.
Столкновение имен прискорбно, но не так уж и загадочно. Куча - это небольшое обычное слово, используемое для обозначения кучи, коллекции, группы и т. д. Использование этого слова для структуры данных предшествует (я почти уверен) имени пула. памяти. На самом деле, на мой взгляд, pool был бы гораздо лучшим выбором для последнего. Куча означает вертикальную структуру (например, стопку), которая соответствует структуре данных, но не пулу памяти. Мы не думаем о куче пула памяти как об иерархической, в то время как фундаментальная идея, лежащая в основе структуры данных, заключается в хранении самого большого элемента в верхней части кучи (и подкучках).
Куча структура данных восходит к середине 60-х; куча пула памяти, начало 70-х гг. Термин «куча» (означающий «пул памяти») использовался по крайней мере еще в 1971 году Wijngaarden при обсуждении Алгол.
Возможно, самое раннее использование heap в качестве структуры данных было обнаружено семью годами ранее в
Williams, JWJ, 1964. «Алгоритм 232 - Heapsort», Связь с ACM 7 (6): 347-348
На самом деле, чтение о том, как распределяется память (см. Buddy Blocks), напоминает мне кучу в структурах данных.
ИМО, это просто случайность / совпадение, что эти две совершенно не связанные между собой вещи имеют одно и то же имя. Это похоже на график и график.
Структура данных типа кучи используется алгоритмом поиска доступной памяти. Нижеследующее взято из http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html.
Когда вызывается
new
, он начинает поиск свободного блока памяти, размер которого соответствует вашему запросу. Предположим, что такой блок памяти найден, он помечается как зарезервированный и возвращается указатель на это место. Для этого существует несколько алгоритмов, поскольку необходимо найти компромисс между сканированием всей памяти для поиска наименьшего свободного блока, превышающего размер вашего объекта, или возвратом первого, где умещается необходимая память. Чтобы повысить скорость получения блока памяти, свободные и зарезервированные области памяти поддерживаются в структуре данных, подобной двоичным деревьям, называемым кучей.
Разговорные термины «стековая память» и «куча» не используются в стандарте C ++. Стандарт использует статическое хранилище, хранилище потоков, автоматическое хранилище и динамическое хранилище.
Дополнительную информацию можно найти в разделе «Продолжительность хранения» стандарта.
Следовательно, с точки зрения языка и стандартной библиотеки нет никакой путаницы.
В. Что такое куча? A. Куча - это набор объектов, расположенных друг над другом.
Ответ на ваш вопрос: и куча памяти, и двоичная куча используют ту же концепцию, что и вы. Данные хранятся в виде кучи в памяти в том же порядке, что и записанные в программе, тогда как двоичная куча - это структура данных, которая следует той же концепции хранения данных упорядоченным образом в форме кучи (данные сверху другой). Дайте мне знать, что вы думаете, в разделе комментариев.
Возможно, первая реализованная куча памяти управлялась структурой кучи?