Комментарии 17
Разжуйте чем куча отличается от связного списка, и как вообще это понятие попало в "структуры данных"? Вообще-то это СПОСОБ хранения, в противовес стековому или статическому или даже константному размещению.. :)
Н-да, вот тут стало грустно. И это "попасть в Яндекс"..
Спасибо за комментатрий) Да, возможно уместно будет добавить, что некоторые главы статьи рассказывают про абстракции, а не структуры данных, но используется для абстракции какая-то структура данных.
Странно, я считаю кучу вполне себе структурой данных. А почему вы считаете ее способом хранения, но не считаете структурой данных?
Судя по всему, из-за терминологической путаницы. "Кучей" называют не только реализацию приоритетной очереди, но ещё место, где хранятся динамически созданные (например, с помощью операции new в с++) объекты
Можно полюбопытствовать, с каких пор приоритетная очередь (разновидность очереди, которая сама есть разновидность связного списка) стала обзываться "кучей"?
Куча, как способ динамического хранения данных - понятен: "валим всё в кучу, аллокатор + GC разберутся сами кого-куда".
Унивеситет ИТМО тоже не согласен: Приоритетная очередь (англ. priority queue) — это абстрактная структура данных наподобие стека или очереди, где у каждого элемента есть приоритет. Элемент с более высоким приоритетом находится перед элементом с более низким приоритетом. Если у элементов одинаковые приоритеты, они располагаются в зависимости от своей позиции в очереди. Обычно приоритетные очереди реализуются с помощью куч (англ. heap). https://neerc.ifmo.ru/wiki/index.php?title=Приоритетные_очереди
"с помощью" никак не может быть структурой данных, только способом.
Зануда моде оф.
Куча не имеет никакого отношения к очереди приоритетов, да ее используют для реализации, но это не обязательно. Например алгоритм сортировки heapsort тоже использует кучу и название говорит само за себя)
В то же время куча вполне себе структура данных, причем по способу организации их много разных видов.
В статье упоминалась бинарная куча, очень полезная структура данных когда надо поддерживать упорядоченность элементов низкой ценой.
Спс, зануда моде он:
Отвечал на коммент, а не содержимое статьи. В статье, да Вы правы термин "куча" применен к .. дереву, причем по признаку .. "нумерации узлов". Я всё понимаю, что у англичан трудности с наименованием и глубоко вложенная синонимия, но все же обзывать дерево кучей, далеко не самый удачный подход.
В плане заголовка статьи, как подготовка к собеседованию у Яши, вызывает некоторое отторжение: а стоит ли идти туда, где забавно переплетаются термины? :)
PS. И собственно к моему первому вопросу: чем ваша "куча" (дерево, очередь с приоритетами) отличается от банального связного списка. Кстати, однонаправленный и двунаправленный списки это одна и та же структура данных или .. разные? :)
А "многоголовый" список с приоритетами .. к чему отнести?
В статье описана бинарная куча как она есть.
С терминами всегда беда, но есть устоявшиеся, такие как куча. Термин дуальный обозначает как способ хранения, так и структуру данных.
Ну а если говорить именно про собес у яши, то гораздо важнее уметь писать код без ошибок в блокноте, чем реально понимать как оно все работает.
Что-то есть в таком подходе .. ранее звалось "обезьяний метод обучения", но .. может оно так и правильнее. Нефиг забивать башку тем как оно работает, устроено .. для этого Чат-гопоты уже есть с копилотом впридачу.. Возникает только нормальный вопрос: а зачем вообще эти "писатели в блокноте", если есть мощные ИДЕ, и уже со встроенным копилотом или чем подобным? Не пора уже начинать увольнять "сеньоров" и набирать вместо них рерайтеров - постановщиков задач ИИ, и плюсом QA - контроллеров ИИ-шного бреда? :)
я сказал "реализацию приоритетной очереди". Подразумевалась бинарная куча, о которой упоминается в статье. То что приоритетную очередь иногда реализуют через бинарную кучу, надеюсь, не вызывает вопросов.
Очень интересная и полезная статья! Если бы мне попалась такая на первом курсе, то защищать лабы по проге было бы в разы легче и понятнее. Тк очень часто приходилось сначал делать, а потом уже понимать как оно работает.
А в питоне list разве не как список под капотом работает?
Или там массив ссылок на элементы?
Есть базовые структуры данных. Например одномерный массив. На базе его можно построить все перечисленные структуры.
Вижу опечатку в префиксных деревьях, в схеме с псевдографикой.
Структуры данных для подготовки к собеседованиям по алгоритмам