Двоичная куча (binary heap), очередь с приоритетом, сортировка кучей - Структуры данных C#

[@CODEBLOG]

Двоичная куча - binary heap - представляет собой полное бинарное дерево, для которого выполняется основное свойство кучи: приоритет каждой вершины больше приоритетов её потомков.
В простейшем случае приоритет каждой вершины можно считать равным её значению. В таком случае структура называется max-куча, поскольку корень поддерева является максимумом из значений элементов поддерева.

[@abdusamadjuraev2615]

ураааааааааааааааааааа,50 000 тысяч подписчиков,поздравляю CODE BLOG!

[@CODEBLOG]

Спасибо :)

[@abdusamadjuraev2615]

@@CODEBLOG двоичная куча как я понял,это как бинарное дерево,ну например от одного дпнного насследуется 2,и пока эти 2 не выполнятся,остальные данные не наследуется,ну првильно я понимаю?

[@CODEBLOG]

@@abdusamadjuraev2615 ну да, по самому смыслу названия бинарное дерево означает, что есть два потомка )

[@DmitryDolganov]

Спасибо!

[@CODEBLOG]

Всегда пожалуйста )

[@praaabot]

Вадим, Добрый день.
Вопрос.
Вы в конструкторе с параметром 1:55:15
public Heap(List items)
{
//добавляете не отсортированную коллекцию
this.items.AddRange(Items);
//тут вызываете её сортировку
for(int i = Count; i >=0 ; i--)
{
Sort(i);
}
}
Почему бы было не воспользоваться методом Add который вы реализовывали для добавления элементов в кучу, он ведь сразу балансирует элементы ?
public Heap(List items)
{
foreach (var item in items)
{
Add(item);
}
}

[@CODEBLOG]

Это возможно, но будет работать медленнее. Сортировка будет выполняться после добавления каждого элемента. А так добавляется сразу вся коллекция и сортируется один раз

[@Frai57]

Не совсем понимаю используется ли вообще у нас метод Peek?
Просто получается так что он просто баластом висит

[@Penat_Vilikirentiy]

Спасибо за стрим, а если у нас к примеру 4 вида приоритета, нулевой ( не активный) - 0, низкий - 1, средний - 2 и высокий - 3, то наша двоичная куча будет их корректно отрабатывать и выбрасывать сперва элементы с самым высоким приоритетом? из примера вроде как отрабатывало корректно на повторяющиеся приоритеты, и почему куча? если структура упорядоченная, в куче ведь вроде все вразброс, прям как в куче с одеждой)

[@CODEBLOG]

да, должно нормально работать. А куча - как кучка, горка, пирамида, где максимальный элемент - это макушка )

[@xtereone]

Ну шо пацаны, Heap Sort?)

[@AShahabov]

Видео по B-tree не планируется?

[@CODEBLOG]

Планирую потом записать еще 10 видео по более сложным структурам и B-tree будет среди них :)

[@ВолодимирБарибін-е8у]

Я что-то не въехал можете кинуть время на рассмотр "Очереди с приоритетом"

[@CODEBLOG]

куча и так есть очередь с приоритетом. когда ты добавляешь элемент она автоматически перестраивается, чтобы в верху стоял элемент с наивысшим приоритетом всегда. просто каждый раз, когда ты вытаскиваешь элемент, он всегда и будет с наивысшим приоритетом. куча = очередь с приоритетом )

[@ВолодимирБарибін-е8у]

@@CODEBLOG спасибо, и куча так же может быть на основе массива, списка, двухсвязного списка и тд, правильно?

[@CODEBLOG]

@@ВолодимирБарибін-е8у На самом деле это древовидная структура, просто особенность ее строения такая, что мы можем поместить ее в массив. На связных списках будет сложно реализовывать, потому что нужен именно доступ по индексу