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

170

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

c++ heap terminology heap-memory Андрей Федоров
источник
4
Мне было интересно это сегодня при изучении структур данных.
MitMaro
1
повторяющийся вопрос? http://stackoverflow.com/questions/756861/whats-the-relationship-between-a-heap-and-the-heap
timB33
3
Зайдите в словарь английского языка и посчитайте количество записей в разделе «Выполнить». Сколько из 40+ записей относится к компьютерам? :)
Jmucchiello
2
Возможный дубликат Какая связь между "кучей" и "кучей"?
RCIX
Связанный пост здесь с кучей времени выполнения, используемой для динамического выделения памяти.
RBT

Ответы:

77

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

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

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

Джеймс МакНеллис
источник
11
Пул будет лучшим именем, чем куча.
7
Интересный. Кто-то должен спросить его, помнит ли он, каких авторов.
Профессор Фалькен
27
Википедия утверждает, что это потому, что на ранней стадии Lisp использовал кучу (структуру данных) для реализации своего хранилища памяти. Это не говорит как. Его ссылка «Томас Х. Кормен, Чарльз Лейзерсон, Рональд Л. Ривест (1990): Введение в алгоритмы. MIT Press / McGraw-Hill.», Которого у меня нет.
Стив Джессоп
2
У меня нет ссылок на это, но я думаю, что изначально структура данных, используемая для организации ссылок на открытые блоки памяти, была минимальной кучей. Похоже, это был бы хотя бы приличный способ быстрого поиска наименьшего блока памяти, который позволил бы вам хранить данные, которые вы пытались сохранить. Обновление: то, что я сказал, звучит точно так же, как блоки друзей en.wikipedia.org/wiki/Dynamic_memory_allocation # Приятель% 5Fblocks
Уилл
4
@SteveJessop - Проверка Cormen, Leiserson, Rivest, Stein - 3-е издание (2009) в начале главы Heapsort, в которой говорится только: «Термин« куча »был изначально придуман в контексте heapsort, но с тех пор он стал ссылаться на« сборщик мусора », такие как языки программирования Java и Lisp. Наша структура данных кучи не является хранилищем для сбора мусора, и всякий раз, когда мы ссылаемся на кучи в этой книге, мы будем иметь в виду структуру данных, а не аспект сбора мусора ». CLRS - 2-е издание также имеет почти точно такую ​​же формулировку (нет никаких признаков того, что Лисп использовал кучу).
р джимбоб
64

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

Эндрю Хэйр
источник
8
Да, я думаю, что именно на этом он основывает свой вопрос: они разные. Так почему их называют одним и тем же - есть ли какое-то основное отношение.
Шон Оуэн
9
То, как я истолковал этот ответ: «Нет, нет никакого отношения», поэтому он отвечает на вопрос.
Лоуренс Гонсалвес
Андрей отвечает на это. Там нет никакого отношения. Просто совпадение. Куча памяти больше соответствует обычному использованию, поскольку память выделяется как «куча одежды». Однако структура данных требовала большего воображения. И это становится гораздо более интересным «почему». Название происходит от того факта, что узлы расположены по их ключу, а ключ родительского узла всегда> =, чем его дочерний узел.
Александр Белл
6
Они определенно не связаны. Однако проблема с названием «кучи» состоит в том, что «аналог кучи» - «стек» - также является реальным стеком.
дан
1
Я знаю, почему структура данных кучи называется кучей: потому что она удовлетворяет свойству кучи. Но почему свойство кучи называется таковым? Это не имеет смысла для меня, так как название типа "top heavy" было бы намного лучше.
Томас Эдинг
31

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

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

Возможно, самое раннее использование кучи в качестве структуры данных было найдено семью годами ранее в
Williams, JWJ 1964. «Алгоритм 232 - Heapsort», Communications of ACM 7 (6): 347-348

IJ Кеннеди
источник
1
Да, но куча также подразумевает беспорядок, а кучи памяти обычно беспорядочные. Куча структуры данных очень хорошо упорядочена. Итак, опять же, есть равное несоответствие, идущее в другую сторону на основе общего определения кучи.
jmucchiello
Он всегда вводится как противоположность стека, которого должно быть достаточно, чтобы объяснить имя IMO.
сообщение от
1
Это не совпадение - свободный список может быть реализован как приоритетная очередь через биномиальную кучу.
Хит Ханникутт
2
@jmucchiello: куча бревен (см. рисунок ) хорошо упорядочена и похожа на дерево. Это происхождение названия структуры данных в соответствии с одним из моих учебников для студентов.
Gioele
6

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

Путешествующий техник
источник
Мой комментарий к ответу Питера Чжана также актуален здесь. Бинарная система друзей может быть представлена ​​в виде двоичного дерева, и она также выглядит как допустимая максимальная куча, когда «ключом» каждого узла является общая память под ним (но эти значения неявны и никогда не меняются). Насколько я могу судить, ни алгоритм выделения, ни освобождения не используют операции с кучей в этом двоичном дереве.
Эрик Дубе
5

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

MAK
источник
Эти два графика могут хоть как-то быть связаны. Представьте себе график функции следующим образом: домен кортежа, диапазон) является вершиной, а ребро соединяет две такие вершины
2
@Amit: Для непрерывных графов это означало бы бесконечное число вершин. Это нормально, но это также делает бессмысленным понятие ребер между вершинами. На графике функции f (x) = x * 2 есть ли ребро между (0,0) и (1,2)? Если да, как насчет (0,0) и (0,5,1)? (0,0) и (0,25,0,5)? Нет никакого способа иметь понятие ребра между вершинами, так что это не совсем граф.
МАК
5

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

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

Пэн Чжан
источник
1
Я очень скептически отношусь к этому, в частности, «... свободные и зарезервированные области памяти поддерживаются в структуре данных, похожей на двоичные деревья, называемые кучей». Мне кажется, что автор догадывается, что существует связь, основанная на названии «куча», и, вероятно, ошибается. Кто-нибудь может подтвердить / опровергнуть?
Дон Хэтч
1
После небольшого исследования системы Binary Buddy (используемой в Linux) она может быть представлена ​​двоичным деревом из-за того, как она разбивает данные. Это двоичное дерево выглядит как допустимая максимальная куча, если вы наблюдаете узлы с точки зрения общей памяти, но узлы не вставляются в это двоичное дерево, как они находятся в максимальной куче - узлы вставляются непосредственно в наименьший лист свободной памяти> = запрошенный размер. 1 2 3
Эрик Дубе
1

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

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

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

Р Саху
источник
1

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

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

Маянк Толани
источник
-2

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

Адам Марас
источник
8
Эта гипотеза не кажется совершенно очевидной - как куча (структура данных) вообще полезна для поддержания кучи (динамическая область памяти)?
Кит Рэндалл
7
-1. Я бы предпочел авторитетное утверждение с доказательством, а не просто предположение.
Роб Кеннеди
Очень маловероятно. Кажется, нет веской причины использовать кучу (структуру данных) для управления кучей (пул свободной памяти).
Джейсон