Какова связь между кучей, используемой при динамическом распределении памяти, и структурой данных?[дубликат]

Question

Возможный Дубликат:
Почему два разных понятия называются “куча”?

Я погуглил, но не могу найти ответ на этот вопрос;какова связь между кучей, используемой при динамическом распределении памяти, и структурой данных?Организована ли память в куче способом, аналогичным структуре данных кучи?Если это так, это кажется очень странным, поскольку выборка памяти должна осуществляться с произвольным доступом AFAIK (т.е. O(1)), но поиск элемента из кучи не выполняется за постоянное время.

Итак, это просто перегруженное значение слова "куча", так сказать, или есть какая-то связь?

Answer 1

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

Структура данных кучи, с другой стороны, совершенно иная - это специализированная древовидная структура с определенными свойствами.

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

Answer 2

Нет, программная куча отличается от структуры данных кучи.Другими словами, никакого отношения. Этот вопрос подробно обсуждается программная куча.

Answer 3

Здесь нет никакой связи, но я признаю, что название может сбить с толку.Куча в памяти - это массив, который ОС выделяет программам.Куча реализуется программами для быстрого поиска.