Алгоритмы и структуры данных: Куча (Heap)

Стрим, помашите мне ручкой в чат. Скажите, что вы меня видите, что вы меня слышите. Это у нас первая трансляция на этом канале, поэтому там фейерверки со всех сторон. Вот это всё, лайков обязательно наваливай, друзья. Меня зовут Александр Романович Тиков, я объясняю, как вообще прога.

И сегодня у нас лекция по алгоритмам, внезапно резкая, сложная. Вот более простые будут дропнуты, мы сразу познакомимся и начнём тут.

Ну значит, суету наводить на этот канал надо подписаться, если тебя интересует Питон, если тебя интересуют алгоритмы, если тебя интересует программирование. Что-то из этого, любое одно из трёх или два из трёх или три из трёх. Вот как вообще там, типа, прога, как работу найти с прогой, связанную, как научиться кодить, как научиться думать головой и так далее. Всё это на примере проги и кода.

Если ты не умеешь кодить, но хотел бы, тебе сюда. Если ты умеешь кодить и хотел бы кодить круче, тебе сюда и так далее. Сегодня мы рассмотрим кучу.

То есть, п это вообще что такое? Это данных такая прекрасная. Вот мы сегодня про эту кучу будем говорить, итеративности.

Вот, скажем так, стрим будет длиться примерно около полутора часов, может чуть меньше, может чуть больше. Ну вот примерно, ну и соответственно сразу можем с вами приступать. Погнали, что ли? Погнали.

Да, так давайте я страничку обновлю, убежусь, что всё работает. Напишите, пожалуйста, в чат, что вы меня видите и слышите, реально, что всё ок, вот что трансляция началась. Да, вот вы спрашиваете, динамическая память будет? Спрашивает, вот всё хорошо.

А смотри, для кучи динамическую память. Ну, посмотрим, ты в смысле хочешь, чтобы я размер типа кучи изменял прямо по мере того, как типа я в неё добавляю, вычетаю? Или ты просто во общем спрашиваешь, в принципе, концептуально будет ли сегодня?

Ну, хочу ли я изменять? Э, не знаю, посмотрим, как укладываться будем. Давай к моменту, когда дойдём, там и поговорим. Я не знаю пока.

А, Поли, поехали. Значит, куча. Давай для начала вообще осознаем, откуда у нас потребность в куче взялась, зачем она вообще нужна и что мы вообще хотим здесь.

Ну давай попробуем понять, что мы вообще часто делаем с данными. Такой вопрос: мы данные в структуру данных, в какую-то, какие вообще структуры данных тебе знакомы?

Ну, например, давай скажем, что у тебя есть вот Python list, да, то есть список обычный, Питонский список. То есть по сути это что-то типа массива, динамическая шка и так далее.

Ну давай уберём, скажем, не Python, здесь просто скажем, короче, массив. Вот в этот массив можно добавлять данные, можно убирать данные, что-нибудь можно из него добывать.

Вот у нас очень часто стоит такая задача, что нам надо доставать, например, максимумы. Очень часто приходится доставать максимумы или часто приходится доставать минимумы. Или, ну короче, что-нибудь делать.

Я хочу с вами сегодня порассуждать. Давайте мы попробуем. Ну я хочу, например, добавить элемент. Давайте вот insert, добавление элемента.

Добавить сколько операций уходит на то, чтобы добавить элемент в обычный массив? Вы давайте, я буду задавать вопросы, будете в чат отвечать. Чисто проверка ваших знаний, проверка понимания, что как вообще у вас работает голова.

Добавление в обычный Python list. Сколько занимает времени, сил? Давайте в чате задержка минимальная, поэтому вы пишите.

А вы хотите добавить просто, чтобы в массиве был этот элемент? Куда хотите, туда и добавляйте. Можете добавлять в конец, можете добавлять в место, короче, куда-то добавить элемент. Вот куда-то.

Давайте, как мы решаем этот вопрос? Мы хотим добавить элемент куда-нибудь, чтобы оно лежало в массиве. Он говорит, Михаил, почему он? Ты хочешь, чтобы оно просто вот где-то в итоге в массиве было? Ты хочешь потратить типа ун?

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

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

По мере того, как им не хватает памяти, в какой-то момент надо понимать, что там на самом деле не одна операция, там на самом деле в среднем две, амортизированная оценка две операции. Но это от одного. Короче, от единицы просто, андем один элемент в конец.

Хорошо, если я хочу удалить элемент из массива. Давайте подумаем, какой первый, последний. Ну давайте, да, давайте один элемент удалим. Удаление элемента, сколько операций требует удаление элемента любого?

Хочу удалить какой-то элемент, сколько требует времени, сил добавления какого-нибудь элемента? Вот п, да, условный. Вот я сейчас хочу применить. Я хочу удалить какой-то элемент. Давайте придумаем, как удалять элементы.

Сколько времени занимает удаление элемента? Может кто-то кроме Михаила включиться тоже в обсуждение? Привет, кондиционер, Данила. Давайте прямо отвечайте на вопросы, господа, у нас сегодня семинар, а не лекция, так что вы тоже разговариваете. Поехали.

Сколько времени у меня уходит на удаление элемента из просто Питон списка любого? Отн говорят. Ну давайте посмотрим. У нас есть, допустим, какой-нибудь список, в НМ есть 3, 4, 5, 7, 8, 12 и 13. Я хочу удалить вот эту пятёрку. Что мне надо сделать для того, чтобы удалить пятёрку?

Ну как бы первый вариант, который кажется, вы имеете в виду, да, он пишет, типа, удаляем пятёрку, потом делаем сдвиг всех. То есть, сево, то есть вот эти все элементы сдвигаем. Пятёрку удалили, потом нам надо практически весь массив сдвигать. Чем ближе к началу элемент, который мы удаляем, тем больше нам придётся сдвигать.

Это о от [музыка]. Да, о от единицы удаление занимает задача. Как удалять элемент за о от единицы? Главная задача, чтобы его просто не было в массиве. Вот просто я хочу, чтобы это какая-то куча чисел и шп элемент к чёрту пропал из массива.

Ну не куча чисел, в смысле куча, а в смысле просто много чисел были как-то напи в массив. Я просто хочу вот их хранить без какого-то порядка, без какой-то сортировки. Сортировка вообще не волнует, порядок не волнует. Хочу удалять элемент.

Как удалять какой-то элемент, чтобы при этом не пришлось весь массив двигатели? Что-то там с ним операции это более много. Ну дырку надо занять. Да, у нас массив всё-таки хранится как некоторая последовательность элементов в памяти, они все подряд, как от единиц.

Это сделать? Ну то есть давайте сотру все эти стрелочки, думать прид. Да, сегодня, к счастью или к сожалению, заставлять вас подумать, что-то придумывать для того, чтобы вы научились самостоятельно решать те задачи, которые перед вами потом будут возникать.

Пум-пурум-пурум-пурум. Пум, известен индекс, как-то перезайти. О, ладно, здесь думаете долго, не нравится. 13 просто вот сюда. Давайте переместимся не с начала, а с конца.

А удаление с конца - это вот единица, также как он, потому что, ну, мы просто потёрли один элемент, ничего сдвигать не надо. Ну типа у меня пришла вот, ну, идея удалить пятёрку, я её удалил.

Ну поменял местами, короче, 513, потом с конца удалил, всё, вот поменять местами от единицы, удалить тоже от единицы. Всё, победа.

А хорошо, следующая операция, которую я хочу, это я хочу добывать максимальный элемент. Get Max, делать, найти максимум. Сколько операций требуется для поиска максимума в обычном Python list? Давайте я пока табличку составлю, в которой будут все эти операции: операция добавления insert, операция удаления remove и операция Get Max.

Мммм, в общем случае ун, если у нас массив тупой, не отсортированный. Отлично, значит, мы научились итить иреть за от единички и удалять за от N.

Хорошо, теперь давайте мы с вами представим, что нам приходится сделать много этих операций. А, ну вместо Get Max можно ещё было бы ввести операцию Pop Max. Давайте я её где-нибудь напишу. В принципе, они идентичны.

Pop Max - это по сути, что такое? Это как бы, ну давайте функцию Pop Max определим. Она будет, значит, в X сохранять Get Max, а потом будет, собственно, X, а потом будет соб всякую специфику, типа там хип, точка и так далее.

Ну то есть не запариваюсь здесь про ОО и всё остальное, но так-то куча пишется, конечно, как класс, полноценный класс, внутри которого вы реализуете все функции кучи, бла-бла-бла.

Ну вот, собственно, массив тоже такая конструкция, которой вы применяете всё это. Ну то есть у вас там есть условно массив А, у которого определены вот эти все операции: Remove, Get Max и так далее, и вы вот Pop Max для А.

Вот так примерно выглядит. То есть Pop Max - это типа взяли максимум и за одним выкинули его из массива.

Ну и вот, давайте такая последовательность. Задача такая: мне дали N чисел в каком-то порядке, подают их по очереди. Я их должен все считать, все их сохранить, а потом по очереди что-то я буду делать с их максимумами.

То есть мне почему-то важно именно вот в какой-то последовательности извлекать их максимумы и по пути что-то с этими максимумами делать.

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

Ну можно придумать какую-нибудь задачу, в которой мне, короче, на каждом шаге нужно максимум, типа там, я не знаю, какой-нибудь там чувак из племени Тумба-Юмба даёт нам числа и иногда, время от времени, говорит: "А какое сейчас максимальное число среди тех, которые я вам дал?" И вы такие: "А вот оно, число максимальное". Вы говорите: "О'кей, хорошо".

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

Ну и давайте скажем, что в этой задаче у нас, допустим, N запросов на добавление, то есть нам дают N чисел и N запросов на удаление. На удаляем мы сразу после того, как Get Max взяли. Тогда у нас решение этой задачи с помощью Python.

Сколько времени операций? Это к вам вопрос. А поставьте плюс в чат все, кто понимает, что там работает за O от N, и минус, кто не понимает, почему Get Max работает за O от N. Это сложная задача.

Мы сразу такие, типа, с места в карьер прыгнули в какие-то, ну, нормальные задачки. Хорошо, есть плюсики, отлично.

Ну я вижу, что плюсики, конечно же, поставит Михаил, Капитан и Данила, потому что они ответили, он сами. Ну может кто-то минус, например, влепит и скажет, что-то сложно.

Сколько времени займёт выполнение решения задачи, в которой N запросов таких, N таких и N таких? Ну просто проверяем, как вы с ошиками вообще возитесь. O от скольки? Так-так-так-так-так, не сошёл с ума, говорит 3N.

Нет, смотри, какая проблема. Если мы используем, то каждая операция Get Max занимает O от 1. Каждая операция Get Max занимает O от 1. Что это значит? Это значит, что мы потратим N запросов insert, каждый по O от 1.

Мы потратим N запросов Remove, каждый по O от 1. Мы потратим N запросов Get Max, каждый по O от 1. То есть итоговая общая затрата у нас - это O от N к. Так, хорошо, хорошо, говорят, просто Get Max поддерживать нам несложно.

Хорошо, давайте заведём дополнительную переменную. Get Max можем делать за O от 1, неплохо. И это хорошая идея.

Вот давайте поставьте плюс в чат, кто понимает идею Prototype Rail Gun. Давайте мы заведём модифицированную структуру данных, в которой мы будем те же самые три операции делать, посмотрим, что у нас с ними происходит.

То есть у нас есть insert, Remove, Get Max. Давайте мы здесь заведём дополнительную переменную, Python list обычный, да, а плюс храним максимум. Хранить максимум не сложно, правда?

И будем ть страдать здесь. Ну типа смотрите, если мы храним максимум, то Get Max у нас сразу O от 1 работает, правильно?

Хорошо, insert. За сколько работает? Что сюда написать? Я хочу добавить один элемент. У меня есть массив 3, 4, 7, 21, 8. Я хочу добавить число, допустим, 18. У меня при этом есть переменная Max, которая хранит в себе число 21.

Отдельная переменная, которая позволяет, такая типа расширенный массив, да, такой массив и ещё одна ячейка специально для хранения максимума. Вот такую структуру данных буду использовать.

А тогда добыть максимум - это просто Max, спасибо, как бы, очень просто. А вот добавление как у меня будет выглядеть? Типа в таком случае insert я определяю следующим образом: если новое значение, давайте insert value, новое значение.

Да, если value меньше либо равно максимальному значению, ну типа у меня там есть моя вот эта вот структура данных, да, точка Max, тогда ничего интересного. Тогда мы просто в массив A как обычно добавляем.

А вот иначе должно произойти что-то интересное. Если я новое значение добавляю и оно больше максимального, то я, получается, могу в массив A добавить, конечно же. Но одновременно с этим я ещё должен максимальное значение поменять на value.

Ну то есть обычный поиск максимума на ходу ещё происходит прямо по мере того, как мы добавляем элементы. Мы ещё за одним максимум перезаписывать код, то он тоже O от 1 работает, так что ничего интересного.

Неужели мы нашли идеальную структуру данных и как бы вообще не паримся? O от 1.

За сколько работает? Я хочу удалять элемент. Хочу удалить какой-нибудь элемент. Чаще всего я буду хотеть удалить именно максимальный элемент, потому что у меня Pop Max будет срабатывать, который достаёт Max и удаляет этот Max.

Соответственно, что я хотел бы вот здесь делать? Я хочу, чтобы эта структура данных при этом сохраняла свои внутренние свойства. Что значит? Мне надо, получается, в Remove удалить элемент.

Как я это в прошлый разделал? Допустим, если я захотел удалить, вот всё, 18 добавилось сюда, допустим, я захотел удалить число 7. Что надо сделать для этого? Надо 7 и 18 поменять местами и потом удалить семёрку, правильно?

18 останется здесь. А что если, ну, удалим секу? Хорошо. А что если я, Ича, задать? Ещё раз часто буду хотеть удалять максимумы. Я захотел удалить 21. Что тогда надо сделать? Надо поменять 21 на 18 местами.

Теперь здесь будет 18, а здесь будет 21. Потом надо удалить 21, но я испортил только что свою структуру данных, потому что сейчас у меня массив и максимум не синхронизированы.

То есть у меня появляется проблема. А, да, Данила, вы правы в том смысле, что если он уже заполнен и нужно в конец что-то добавить, нужно сделать реа лог и так далее.

Мы говорим, что это Python list, он сам делает реа лог. Иногда он тратит не одну операцию, а типа дофига, ну N операций, потому что реа лог, да, перековать всего и так далее.

Но если там аккуратненько посчитать, я сейчас на это не буду время тратить, то там на самом деле получается, что в среднем тратится две операции на каждый элемент. В плане элементы достаточно редко реа лог делать.

Как жить-то вообще? Я что-то вот, ну, не очень понимаю. Я удалил 21, и у меня максимум как бы сбился. То есть у меня теперь максимум не 21.

То есть Remove он на самом деле получается теперь как старый Remove плюс старый Get Max, потому что надо одновременно сделать и то, и то. Нам надо удалить старую переменную сначала 21, как раньше мы её удаляли, а потом нам надо пересчитать максимум, потому что мы его потеряли только что, когда мы удалили максимальный элемент.

Мы не знаем теперь, какой максимальный. Какие у вас есть идеи решения? Ну давайте хранить не только максимальный, а максимальный и предмаксимальный. Тогда Remove одного элемента - это не проблема.

Просто вместо максимума пере запишем предмаксимум. А, ой, предмаксимум придётся пересчитывать. Ну короче, как будто идея хорошая, но тратит на Remove тогда операций, потому что надо пересчитать максимум.

Да, неприятно, неприятно. Ещё идеи? Какие у вас ещё есть идеи? Хочу, чтобы задача про Тумба-Юмба, в которой операций входа, операций выхода, добавление вот этих элементов, вычитание элементов. Это интересно. Мак пересчитывать интересно, согласен.

Хорошо, давайте мы да Мак посмотрим. Типа, мы помним стек максимумов. То есть на каждом шаге мы помним, какой добавили. Даже не, ну короче, это не Макс стек. Да, стек максимумов - это мы что, получается, на каждом шаге добавляем элементы.

Да, ну такие, типа, у нас, допустим, были элементы 7, 13, 21, потом 14, потом 10, потом 11 вот в таком порядке. Тогда у нас в стеке максимумов лежит 7, 13, 21, потом 14 не кладётся туда, потому что оно уже не заменяет, правильно?

10 тоже не кладётся, 11 тоже не кладётся. Потом внезапно поступила операция Get Max, мы такие 21, верхушка стека, всё правильно. Get Max за единичку, правда.

Потом поступила ещё одна операция insert. Если элемент больше, то мы его засовывали, он меньше, то не засовывает в массив, правильно?

Но тогда операция вызывает проблемы, что вот давайте, допустим, 21, мне пришла команда: "Я хочу удалить вот этот элемент". Сразу после того, как я его достал, Get Max, я такой: "Спасибо, зама, теперь хочу удалить".

Если я удаляю 21, я попа верхушку стека, и у меня остаётся 13, но 13 - это на самом деле не настоящий максимум. Это проблема. У нас типа нам надо теперь снова пересчитывать максимум, потому что 13 было последователь ма.

Нам надо, чтобы после 21 мы прыгнули к 14, к максимуму, не позволит нам это сделать. Нам надо, чтобы мы хранили, получается, все числа 21, а потом нам надо хранить это же число следующее 14, чтобы к нему перейти.

А потом, если 14 вызывают, нам надо следующее 13, чтобы за единичку мы их могли доставать. Нам надо, чтобы они были где-то отсортированы: 21, потом 14, потом 13.

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

Знаете, когда говорят: "У нас Color coding", но на самом деле у них не Color coding, у них просто Color и всё. Много разных цветов, но эти цвета ничего не значат. Тут хотя бы разница английский, русский.

Да, хотя тоже на самом деле хотелось бы, наверное, хит написать фиолет. Так вот, так, а sorted Python list. Давайте вот такую идею возьмём.

Давайте хранить отсортированный список. Это тоже структура данных. Смотрите, мы сейчас с вами возим с на простых структурах данных, уже знакомых вам, для того чтобы понять задачу вообще, в чём суть задачи, откуда куча родилась, вообще зачем она нужна, вообще что это такое, чем она интересна, чем она полезна, чем она прикольна.

Максимум, предмаксимум в стеке. Если вы будете только максимум, предмаксимум хранить, это не спасёт, потому что при удалении максимума вам придётся тяжело и больно пересчитывать предмаксимум. Всё равно за O от N, то есть не меняется особо.

Храним Max, храним предмакс, ещё стек. Ну то есть я могу придумать последовательность входных данных, на которых только максимум, предмаксимума не хватит. Там аналогичная проблема будет.

Давайте с сортированным листом разберёмся. А представьте себе, что у вас есть отсортированный список. Что вы можете мне назвать из этих трёх? Или Get Max, у чего вы знаете сразу ответ, не думая, в сортированного списка, что легко добывается?

Что легко добывается в сортированного списка? Просто обычный Python list, если мы юзаем. Гу, какой набор? Что, что легко посчитать в сорт от листе? Max или может быть Remove или может быть insert или может быть, ну что?

Что приятно тут считается в сорт от листе? Минимум, максимум, говорят, за O от единички. Да, минимум нам не нужен.

Ну в принципе, если минимум, то переворачиваем всю задачу. Да, донос на минус единиц, и у нас теперь минимумы ищутся. Ладно, короче, максимум за O от единиц, согласен, сорт легко.

Очень, что ещё знаем? Insert как работают? Почему? Почему? Что у нас получается? Он хранит числа по убыванию, да, например, или по возрастанию. Лучше по возрастанию, потому что мы регулярно будем хотеть убирать Max.

145, 200. Вот такой у нас массив, он сейчас хранится в отсортированном виде. Я хочу добавить в него элемент 20. Как добавлять 20? Нам надо двигать элементы каждый раз, да, получается какая-то.

То есть, несмотря на то, что найти место для двадцати не очень сложно, можно просто бин поиском, да, быстренько пробежаться от левого до правого края, найти место, куда засунуть. Но чтобы засунуть 20 в середину, нам надо все остальные элементы.

Это было бы очень удобно, а односвязный или двусвязный список засунуть тогда в середину. Было бы очень удобно, просто разорвали, засунули с кайфом. Да, но у нас вот так оно как есть.

Окей, хорошо, ну 20 засовывается, получается, куда-то сюда. Хотим засунуть, для этого надо ВС сдвинуть, получается, операций. Да, как-то упростить здесь. Как именно мы будем зать? Мы будем 20 сравнивать с ми, меньше со 145, меньше с 1,5, меньше с 2.

Ну всё, значит, пока меньше, мы 200 двигаем. 20 сюда сейчас претендует 20 и 145. Ну короче, просто сделали. Окей, хорошо.

Да, поиск места конкретно место получается нельзя неудобно. Не интересно, какое дерево. Как вы хотите, что вы хотите с деревом? Remove здесь тоже работает неприятно, потому что вы элемент как бы стёрли.

Например, 21 вы хотите затереть. Да, все придётся двигать, то есть тоже O от N, и у вас в итоге решение задачи получается всё равно за квадрат, да, O от N в квадрате.

То есть мы улучшили сильно Get Max, но ухудшили как бы ситуацию с вот хранением максимума. Читерская штука, мы как бы перетащили нагрузку с Get Max на Remove, по сути, но всё равно у нас проблема.

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

То есть у вас какие-то данные, задачи, в которых вам добавляют, ну, данные не очень часто, типа пользователь регистрируется дополнительный.

Ну или давайте так, у вас задача такая: у вас выручка поступает раз в день, информация о том, какую выручку ваша компания за сегодня заработала, или там продажи, допустим, у вас происходят раз в час, и у вас раз в час прилетает операция insert, операция Remove прилетает вообще, ну, иногда во время maintenance только.

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

Получается, что такая структура подошла бы вот, а такая структура не подходит, если вы часто делаете Get максимумы. Такая структура подходит, если вы редко делаете инсерты и Ревы и часто делаете Get Max.

Ну как бы логично вот такую взять, да. Ну, собственно, с чем-то познакомились, с чем-то познакомились. Давайте-ка мы теперь посмотрим на то, как выглядит куча.

Давайте мы возьмём кучу. Куча - это что такое? Такая структура данных. А давайте я тут вот напишу ку хип и под неё зарезервировать, сохранить.

Ну короче, давайте как-нибудь мы. Да ладно, всё, я решил, что я буду эту табличку сохраню в углу где-то. Давайте insert, Remove и Get Max. Вот такая табличка, и у нас есть тут ещё раз лист, лист с максимумом и sorted list.

Вот такая табличка, и у нас здесь, соответственно, 1N, здесь 1, N1, а здесь у нас N, N1. Всё, хочу место на доске просто себе освободить. Всё же видно, да? Да, всё видно.

Хорошо, прекрасно, всё это я стираю, и мы с вами сейчас исследуем, собственно, структуру данных, которую мы хотели.

Сейчас потребуется немножко отойти от нарратива. Я это просто сохраню, но вместо этого просто поем. Чит, куча - это дерево, где в узлах хранятся числа и соблюдается следующее условие.

Конкретно Макс кучу будем сейчас писать, потому что у нас операция Get Max соблюдается следующее условие, что родитель больше либо равен своих детей.

Ну то есть, например, если здесь написано число 4, то здесь могут быть написаны числа 5 и 3. Если здесь написано число 9, то здесь будет написано число 8, например, и 2. Здесь может быть написано число 11, тогда здесь будет 10, и здесь может быть написано, например, 5, 4, 3, 20.

Здесь, например, 10, и здесь 31. Вот куча, Макс куча, которой соблюдается условия. Поставьте плюс в чат, если понятно условие.

Поглядывай кучу. Специально числа написал такие, чтобы понятно было, что в каком-то стандартном понимании. То есть она не то, что там 1, 2, 3, 4, 5. То есть вот тут единичка, вот тут десятка, тут тоже десятка.

Вообще пофиг. Самое главное, чтобы у неё чисто было упорядочивание вот такого плана, то есть родители всегда старше детей. А вот ваши какие-нибудь двоюродные дяди или тёти могут быть даже младше вас. Это нормально абсолютно.

Главное, чтобы родители были больше детей. Всё. Ну давайте, мся, сразу что мы в куче можем. Тода добыть сразу вот что в куче очевидно, что не требует вообще даже мышления.

Слишком легко для кучи найти, что? Какая операция здесь бесплатная? Максимум - это корень. Всё, победа. Да, Get Max за единичку работает, очевидно.

Вот он максимум, почему он максимум? Потому что это прародитель всех, вообще всех, всех. Он больше либо равен этих, больше этих, больше этих. В общем, он больше всех, это максимум абсолютно точно.

По сути, это на самом деле апгрейды что-то поменьше, но не совсем сортированного. А давайте поймём, как работает insert, как работает Remove.

Давайте мы для insert и Remove, для красоты сделаем эту кучу не до конца заполненной. Ну чтобы не надо было целый новый уровень там открывать. Давайте скажем, что у нас, ну, не хватает здесь пустые места, короче, есть.

За сколько тогда можно сделать, например, insert? Например, я хочу сделать insert числа, например, 12. Ну кажется, ничего сложного, да? Insert легко, просто дописывает сюда и вроде всё, да, но нет.

Кажется, что insert работает за одну операцию, потому что делов-то дописать в кучу и всё. Но у нас вот в самом первом шаге array был просто массив, в нём просто хранились числа и можно было в конец-то дописать и не париться, потому что не было никакой структуры у этих чисел.

И добавив одно дополнительное число, мы сохраняли то, что там нет структуры. А сейчас у нас есть какая-то структура, и добавив одно дополнительное число, ты не сохраняешь эту структуру, ты её портишь, теряешь, короче, ломаешь.

Плохо как там это число 12. Теперь, короче, мы кучу испортили. У нас теперь не соблюдается правила. А где у нас правила не соблюдается? У нас правила не соблюдается между девяткой и двенадцатью.

12 лежит на первом уровне, на самом нижнем и возражает своему родителю. Оно говорит: "Как так получилось, что ты мой начальник, а я больше тебя?" Скиловик в иерархии в компании, и он получается круче, чем его начальство.

Да, ситуация сплошь рядом встречающаяся, но вот так получилось. То есть мне нужно, чтобы все знаки неравенств были правильными, чтобы 31 было больше, чем 20, 20 было больше, чем 18, больше, чем 11, 11 было больше, чем 10.

То есть все знаки здесь работают сверху вниз, да, а вот в одном месте не сработали. Вот тут вот как бы проблема. Тогда мы, в общем, кроме обычного добавления, запускаем sift Up.

Что такое sift Up? Это, ну, sift, английская sift, это просеивание. Что такое Up? Ну это вверх, как бы, да, это типа не надо переводить, наверное.

Процедура, операция, функция просеивания. Что с ней происходит? Конкретно что она будет делать? Она будет 12 толкать вверх, как пузырёк всплывающий, пока там конфликты возникают.

Значит, смотрите, 12 и 10, они друг с другом поругались, и в итоге написали петицию в контролирующий орган. Контролирующий орган посмотрел и сказал: "Реально непорядок, не должно быть такого, чтобы сотрудник был умнее, чем начальник".

Поэтому вас понижаем, а вас повышаем. Теперь между ними всё в порядке, неравенство соблюдено, правильно?

Но у нас возникла следующая проблема. 12 и 10. Мы хотим, получается, поменять местами теперь 12 и 10. То есть вот эти вот два элемента должны поменяться.

Ну делаем ещё одну операцию замены, получается, что 10 попадает сюда, а 12 остаётся здесь. Теперь у нас соблюдается неравенство между 12 и 10.

Вопрос: вот с этим неравенством, что может ли такое быть, что 12 переназначить наверх, и теперь вот это неравенство сломалось между десяткой и восьмёркой?

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

Может ли такое быть? Вопрос ко мне. Не могло, говорят. Почему? Доказательство бы какое-нибудь, ну хотя бы маломальский.

Ну то есть можно на вот эти левые ветки не обращать внимания. В какой момент нам следует остановиться? Когда нам следует закончить процесс просеивания sift Up?

Ну в одном из двух случаев очевидно, да. Один случай - это когда мы оказались меньше, чем наш начальник, и мы такие: "Всё, удовлетворены, в этой позиции нам комфортно работается".

А вторая ситуация - это если мы стали Богом, и теперь мы начальник всего, и тогда бесполезно делать уже. Куда дальше?

Всё, соответственно, либо дошли до корня, либо упёрлись в точку, где меньше либо равно, больше либо равно. Вот это не работает. Всё хорошо.

Один из двух вариантов. Вопрос: sift по асимптоти. Сколько занимает? Ну то есть вопрос: сколько сейчас занял наш insert? Сколько мы реально операций сделали?

Одна операция добавления, а потом вот этот sift. Sift - это насколько тяжело было нам, давайте осознаем для этого. Давайте попробуем построить дерево размером N и понять, сколько шагов нам придётся вот здесь сделать.

Максимум. Максимум вот здесь три шага. Как понять количество шагов? Это глубина дерева. Что такое глубина дерева? Если в дереве N элементов, N элементов.

Давайте осознаем, что такое дерево размером K, допустим. Ну то есть, допустим, я хочу, чтобы у меня дерево было высотой. Построим полное бинарное дерево, в котором ровно K уровней.

Например, давайте один уровень равно один, одна вершина. Два уровня уже три вершины. Если у нас три уровня, то смотрите, на третьем уровне добавляется.

Пче, то есть три уровня, это у нас 3 плюс 4, 5, 7, 8, 12 и 13. Я хочу удалить вот эту пятёрку. Что мне надо сделать для того, чтобы удалить пятёрку?

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

Чем ближе к началу элемент, который мы удаляем, тем больше нам придётся сдвигать. Это о от [музыка]. Да, о от единицы удаление занимает задача.

Как удалять элемент за о от единицы? Главная задача, чтобы его просто не было в массиве. Вот просто я хочу, чтобы это какая-то куча чисел и шп элемент к чёрту пропал из массива.

Ну не куча чисел, в смысле куча, а в смысле просто много чисел были как-то напи в массив. Я просто хочу вот их хранить без какого-то порядка, без какой-то сортировки. Сортировка вообще не волнует, порядок не волнует. Хочу удалять элемент.

Как удалять какой-то элемент, чтобы при этом не пришлось весь массив двигатели? Что-то там с ним операции это более много. Ну дырку надо занять. Да, у нас массив всё-таки хранится как некоторая последовательность элементов в памяти, они все подряд, как от единиц.

Это сделать? Ну то есть давайте сотру все эти стрелочки, думать прид. Да, сегодня, к счастью или к сожалению, заставлять вас подумать, что-то придумывать для того, чтобы вы научились самостоятельно решать те задачи, которые перед вами потом будут возникать.

Пум-пурум-пурум-пурум. Пум, известен индекс, как-то перезайти. О, ладно, здесь думаете долго, не нравится. 13 просто вот сюда. Давайте переместимся не с начала, а с конца.

А удаление с конца - это вот единица, также как он, потому что, ну, мы просто потёрли один элемент, ничего сдвигать не надо. Ну типа у меня пришла вот, ну, идея удалить пятёрку, я её удалил.

Ну поменял местами, короче, 513, потом с конца удалил, всё, вот поменять местами от единицы, удалить тоже от единицы. Всё, победа.

А хорошо, следующая операция, которую я хочу, это я хочу добывать максимальный элемент. Get Max, делать, найти максимум. Сколько операций требуется для поиска максимума в обычном Python list? Давайте я пока табличку составлю, в которой будут все эти операции: операция добавления insert, операция удаления remove и операция Get Max.

Мммм, в общем случае ун, если у нас массив тупой, не отсортированный. Отлично, значит, мы научились итить иреть за от единички и удалять за от N.

Хорошо, теперь давайте мы с вами представим, что нам приходится сделать много этих операций. А, ну вместо Get Max можно ещё было бы ввести операцию Pop Max. Давайте я её где-нибудь напишу. В принципе, они идентичны.

Pop Max - это по сути, что такое? Это как бы, ну давайте функцию Pop Max определим. Она будет, значит, в X сохранять Get Max, а потом будет, собственно, X, а потом будет соб всякую специфику, типа там хип, точка и так далее.

Ну то есть не запариваюсь здесь про ОО и всё остальное, но так-то куча пишется, конечно, как класс, полноценный класс, внутри которого вы реализуете все функции кучи, бла-бла-бла.

Ну вот, собственно, массив тоже такая конструкция, которой вы применяете всё это. Ну то есть у вас там есть условно массив А, у которого определены вот эти все операции: Remove, Get Max и так далее, и вы вот Pop Max для А.

Вот так примерно выглядит. То есть Pop Max - это типа взяли максимум и за одним выкинули его из массива.

Ну и вот, давайте такая последовательность. Задача такая: мне дали N чисел в каком-то порядке, подают их по очереди. Я их должен все считать, все их сохранить, а потом по очереди что-то я буду делать с их максимумами.

То есть мне почему-то важно именно вот в какой-то последовательности извлекать их максимумы и по пути что-то с этими максимумами делать.

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

Ну можно придумать какую-нибудь задачу, в которой мне, короче, на каждом шаге нужно максимум, типа там, я не знаю, какой-нибудь там чувак из племени Тумба-Юмба даёт нам числа и иногда, время от времени, говорит: "А какое сейчас максимальное число среди тех, которые я вам дал?" И вы такие: "А вот оно, число максимальное". Вы говорите: "О'кей, хорошо".

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

Ну и давайте скажем, что в этой задаче у нас, допустим, N запросов на добавление, то есть нам дают N чисел и N запросов на удаление. На удаляем мы сразу после того, как Get Max взяли. Тогда у нас решение этой задачи с помощью Python.

Сколько времени операций? Это к вам вопрос. А поставьте плюс в чат все, кто понимает, что там работает за O от N, и минус, кто не понимает, почему Get Max работает за O от N. Это сложная задача.

Мы сразу такие, типа, с места в карьер прыгнули в какие-то, ну, нормальные задачки. Хорошо, есть плюсики, отлично.

Ну я вижу, что плюсики, конечно же, поставит Михаил, Капитан и Данила, потому что они ответили, он сами. Ну может кто-то минус, например, влепит и скажет, что-то сложно.

Сколько времени займёт выполнение решения задачи, в которой N запросов таких, N таких и N таких? Ну просто проверяем, как вы с ошиками вообще возитесь. O от скольки? Так-так-так-так-так, не сошёл с ума, говорит 3N.

Нет, смотри, какая проблема. Если мы используем, то каждая операция Get Max занимает O от 1. Каждая операция Get Max занимает O от 1. Что это значит? Это значит, что мы потратим N запросов insert, каждый по O от 1.

Мы потратим N запросов Remove, каждый по O от 1. Мы потратим N запросов Get Max, каждый по O от 1. То есть итоговая общая затрата у нас - это O от N к. Так, хорошо, хорошо, говорят, просто Get Max поддерживать нам несложно.

Хорошо, давайте заведём дополнительную переменную. Get Max можем делать за O от 1, неплохо. И это хорошая идея.

Вот давайте поставьте плюс в чат, кто понимает идею Prototype Rail Gun. Давайте мы заведём модифицированную структуру данных, в которой мы будем те же самые три операции делать, посмотрим, что у нас с ними происходит.

То есть у нас есть insert, Remove, Get Max. Давайте мы здесь заведём дополнительную переменную, Python list обычный, да, а плюс храним максимум. Хранить максимум не сложно, правда?

И будем ть страдать здесь. Ну типа смотрите, если мы храним максимум, то Get Max у нас сразу O от 1 работает, правильно?

Хорошо, insert. За сколько работает? Что сюда написать? Я хочу добавить один элемент. У меня есть массив 3, 4, 7, 21, 8. Я хочу добавить число, допустим, 18. У меня при этом есть переменная Max, которая хранит в себе число 21.

Отдельная переменная, которая позволяет, такая типа расширенный массив, да, такой массив и ещё одна ячейка специально для хранения максимума. Вот такую структуру данных буду использовать.

А тогда добыть максимум - это просто Max, спасибо, как бы, очень просто. А вот добавление как у меня будет выглядеть? Типа в таком случае insert я определяю следующим образом: если новое значение, давайте insert value, новое значение.

Да, если value меньше либо равно максимальному значению, ну типа у меня там есть моя вот эта вот структура данных, да, точка Max, тогда ничего интересного. Тогда мы просто в массив A как обычно добавляем.

А вот иначе должно произойти что-то интересное. Если я новое значение добавляю и оно больше максимального, то я, получается, могу в массив A добавить, конечно же. Но одновременно с этим я ещё должен максимальное значение поменять на value.

Ну то есть обычный поиск максимума на ходу ещё происходит прямо по мере того, как мы добавляем элементы. Мы ещё за одним максимум перезаписывать код, то он тоже O от 1 работает, так что ничего интересного.

Неужели мы нашли идеальную структуру данных и как бы вообще не паримся? O от 1.

За сколько работает? Я хочу удалять элемент. Хочу удалить какой-нибудь элемент. Чаще всего я буду хотеть удалить именно максимальный элемент, потому что у меня Pop Max будет срабатывать, который достаёт Max и удаляет этот Max.

Соответственно, что я хотел бы вот здесь делать? Я хочу, чтобы эта структура данных при этом сохраняла свои внутренние свойства. Что значит? Мне надо, получается, в Remove удалить элемент.

Как я это в прошлый разделал? Допустим, если я захотел удалить, вот всё, 18 добавилось сюда, допустим, я захотел удалить число 7. Что надо сделать для этого? Надо 7 и 18 поменять местами и потом удалить семёрку, правильно?

18 останется здесь. А что если, ну, удалим секу? Хорошо. А что если я, Ича, задать? Ещё раз часто буду хотеть удалять максимумы. Я захотел удалить 21. Что тогда надо сделать? Надо поменять 21 на 18 местами.

Теперь здесь будет 18, а здесь будет 21. Потом надо удалить 21, но я испортил только что свою структуру данных, потому что сейчас у меня массив и максимум не синхронизированы.

То есть у меня появляется проблема. А, да, Данила, вы правы в том смысле, что если он уже заполнен и нужно в конец что-то добавить, нужно сделать реа лог и так далее.

Мы говорим, что это Python list, он сам делает реа лог. Иногда он тратит не одну операцию, а типа дофига, ну N операций, потому что реа лог, да, перековать всего и так далее.

Но если там аккуратненько посчитать, я сейчас на это не буду время тратить, то там на самом деле получается, что в среднем тратится две операции на каждый элемент. В плане элементы достаточно редко реа лог делать.

Как жить-то вообще? Я что-то вот, ну, не очень понимаю. Я удалил 21, и у меня максимум как бы сбился. То есть у меня теперь максимум не 21.

То есть Remove он на самом деле получается теперь как старый Remove плюс старый Get Max, потому что надо одновременно сделать и то, и то. Нам надо удалить старую переменную сначала 21, как раньше мы её удаляли, а потом нам надо пересчитать максимум, потому что мы его потеряли только что, когда мы удалили максимальный элемент.

Мы не знаем теперь, какой максимальный. Какие у вас есть идеи решения? Ну давайте хранить не только максимальный, а максимальный и предмаксимальный. Тогда Remove одного элемента - это не проблема.

Просто вместо максимума пере запишем предмаксимум. А, ой, предмаксимум придётся пересчитывать. Ну короче, как будто идея хорошая, но тратит на Remove тогда операций, потому что надо пересчитать максимум.

Да, неприятно, неприятно. Ещё идеи? Какие у вас ещё есть идеи? Хочу, чтобы задача про Тумба-Юмба, в которой операций входа, операций выхода, добавление вот этих элементов, вычитание элементов. Это интересно. Мак пересчитывать интересно, согласен.

Хорошо, давайте мы да Мак посмотрим. Типа, мы помним стек максимумов. То есть на каждом шаге мы помним, какой добавили. Даже не, ну короче, это не Макс стек. Да, стек максимумов - это мы что, получается, на каждом шаге добавляем элементы.

Да, ну такие, типа, у нас, допустим, были элементы 7, 13, 21, потом 14, потом 10, потом 11 вот в таком порядке. Тогда у нас в стеке максимумов лежит 7, 13, 21, потом 14 не кладётся туда, потому что оно уже не заменяет, правильно?

10 тоже не кладётся, 11 тоже не кладётся. Потом внезапно поступила операция Get Max, мы такие 21, верхушка стека, всё правильно. Get Max за единичку, правда.

Потом поступила ещё одна операция insert. Если элемент больше, то мы его засовывали, он меньше, то не засовывает в массив, правильно?

Но тогда операция вызывает проблемы, что вот давайте, допустим, 21, мне пришла команда: "Я хочу удалить вот этот элемент". Сразу после того, как я его достал, Get Max, я такой: "Спасибо, зама, теперь хочу удалить".

Если я удаляю 21, я попа верхушку стека, и у меня остаётся 13, но 13 - это на самом деле не настоящий максимум. Это проблема. У нас типа нам надо теперь снова пересчитывать максимум, потому что 13 было последователь ма.

Нам надо, чтобы после 21 мы прыгнули к 14, к максимуму, не позволит нам это сделать. Нам надо, чтобы мы хранили, получается, все числа 21, а потом нам надо хранить это же число следующее 14, чтобы к нему перейти.

А потом, если 14 вызывают, нам надо следующее 13, чтобы за единичку мы их могли доставать. Нам надо, чтобы они были где-то отсортированы: 21, потом 14, потом 13.

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

Знаете, когда говорят: "У нас Color coding", но на самом деле у них не Color coding, у них просто Color и всё. Много разных цветов, но эти цвета ничего не значат. Тут хотя бы разница английский, русский.

Да, хотя тоже на самом деле хотелось бы, наверное, хит написать фиолет. Так вот, так, а sorted Python list. Давайте вот такую идею возьмём.

Давайте хранить отсортированный список. Это тоже структура данных. Смотрите, мы сейчас с вами возим с на простых структурах данных, уже знакомых вам, для того чтобы понять задачу вообще, в чём суть задачи, откуда куча родилась, вообще зачем она нужна, вообще что это такое, чем она интересна, чем она полезна, чем она прикольна.

Максимум, предмаксимум в стеке. Если вы будете только максимум, предмаксимум хранить, это не спасёт, потому что при удалении максимума вам придётся тяжело и больно пересчитывать предмаксимум. Всё равно за O от N, то есть не меняется особо.

Храним Max, храним предмакс, ещё стек. Ну то есть я могу придумать последовательность входных данных, на которых только максимум, предмаксимума не хватит. Там аналогичная проблема будет.

Давайте с сортированным листом разберёмся. А представьте себе, что у вас есть отсортированный список. Что вы можете мне назвать из этих трёх? Или Get Max, у чего вы знаете сразу ответ, не думая, в сортированного списка, что легко добывается?

Что легко добывается в сортированного списка? Просто обычный Python list, если мы юзаем. Гу, какой набор? Что, что легко посчитать в сорт от листе? Max или может быть Remove или может быть insert или может быть, ну что?

Что приятно тут считается в сорт от листе? Минимум, максимум, говорят, за O от единички. Да, минимум нам не нужен.

Ну в принципе, если минимум, то переворачиваем всю задачу. Да, донос на минус единиц, и у нас теперь минимумы ищутся. Ладно, короче, максимум за O от единиц, согласен, сорт легко.

Очень, что ещё знаем? Insert как работают? Почему? Почему? Что у нас получается? Он хранит числа по убыванию, да, например, или по возрастанию. Лучше по возрастанию, потому что мы регулярно будем хотеть убирать Max.

145, 200. Вот такой у нас массив, он сейчас хранится в отсортированном виде. Я хочу добавить в него элемент 20. Как добавлять 20? Нам надо двигать элементы каждый раз, да, получается какая-то.

То есть, несмотря на то, что найти место для двадцати не очень сложно, можно просто бин поиском, да, быстренько пробежаться от левого до правого края, найти место, куда засунуть. Но чтобы засунуть 20 в середину, нам надо все остальные элементы.

Это было бы очень удобно, а односвязный или двусвязный список засунуть тогда в середину. Было бы очень удобно, просто разорвали, засунули с кайфом. Да, но у нас вот так оно как есть.

Окей, хорошо, ну 20 засовывается, получается, куда-то сюда. Хотим засунуть, для этого надо ВС сдвинуть, получается, операций. Да, как-то упростить здесь. Как именно мы будем зать? Мы будем 20 сравнивать с ми, меньше со 145, меньше с 1,5, меньше с 2.

Ну всё, значит, пока меньше, мы 200 двигаем. 20 сюда сейчас претендует 20 и 145. Ну короче, просто сделали. Окей, хорошо.

Да, поиск места конкретно место получается нельзя неудобно. Не интересно, какое дерево. Как вы хотите, что вы хотите с деревом? Remove здесь тоже работает неприятно, потому что вы элемент как бы стёрли.

Например, 21 вы хотите затереть. Да, все придётся двигать, то есть тоже O от N, и у вас в итоге решение задачи получается всё равно за квадрат, да, O от N в квадрате.

То есть мы улучшили сильно Get Max, но ухудшили как бы ситуацию с вот хранением максимума. Читерская штука, мы как бы перетащили нагрузку с Get Max на Remove, по сути, но всё равно у нас проблема.

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

То есть у вас какие-то данные, задачи, в которых вам добавляют, ну, данные не очень часто, типа пользователь регистрируется дополнительный.

Ну или давайте так, у вас задача такая: у вас выручка поступает раз в день, информация о том, какую выручку ваша компания за сегодня заработала, или там продажи, допустим, у вас происходят раз в час, и у вас раз в час прилетает операция insert, операция Remove прилетает вообще, ну, иногда во время maintenance только.

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

Получается, что такая структура подошла бы вот, а такая структура не подходит, если вы часто делаете Get максимумы. Такая структура подходит, если вы редко делаете инсерты и Ревы и часто делаете Get Max.

Ну как бы логично вот такую взять, да. Ну, собственно, с чем-то познакомились, с чем-то познакомились. Давайте-ка мы теперь посмотрим на то, как выглядит куча.

Давайте мы возьмём кучу. Куча - это что такое? Такая структура данных. А давайте я тут вот напишу ку хип и под неё зарезервировать, сохранить.

Ну короче, давайте как-нибудь мы. Да ладно, всё, я решил, что я буду эту табличку сохраню в углу где-то. Давайте insert, Remove и Get Max. Вот такая табличка, и у нас есть тут ещё раз лист, лист с максимумом и sorted list.

Вот такая табличка, и у нас здесь, соответственно, 1N, здесь 1, N1, а здесь у нас N, N1. Всё, хочу место на доске просто себе освободить. Всё же видно, да? Да, всё видно.

Хорошо, прекрасно, всё это я стираю, и мы с вами сейчас исследуем, собственно, структуру данных, которую мы хотели.

Сейчас потребуется немножко отойти от нарратива. Я это просто сохраню, но вместо этого просто поем. Чит, куча - это дерево, где в узлах хранятся числа и соблюдается следующее условие.

Конкретно Макс кучу будем сейчас писать, потому что у нас операция Get Max соблюдается следующее условие, что родитель больше либо равен своих детей.

Ну то есть, например, если здесь написано число 4, то здесь могут быть написаны числа 5 и 3. Если здесь написано число 9, то здесь будет написано число 8, например, и 2. Здесь может быть написано число 11, тогда здесь будет 10, и здесь может быть написано, например, 5, 4, 3, 20.

Здесь, например, 10, и здесь 31. Вот куча, Макс куча, которой соблюдается условия. Поставьте плюс в чат, если понятно условие.

Поглядывай кучу. Специально числа написал такие, чтобы понятно было, что в каком-то стандартном понимании. То есть она не то, что там 1, 2, 3, 4, 5. То есть вот тут единичка, вот тут десятка, тут тоже десятка.

Вообще пофиг. Самое главное, чтобы у неё чисто было упорядочивание вот такого плана, то есть родители всегда старше детей. А вот ваши какие-нибудь двоюродные дяди или тёти могут быть даже младше вас. Это нормально абсолютно.

Главное, чтобы родители были больше детей. Всё. Ну давайте, мся, сразу что мы в куче можем. Тода добыть сразу вот что в куче очевидно, что не требует вообще даже мышления.

Слишком легко для кучи найти, что? Какая операция здесь бесплатная? Максимум - это корень. Всё, победа. Да, Get Max за единичку работает, очевидно.

Вот он максимум, почему он максимум? Потому что это прародитель всех, вообще всех, всех. Он больше либо равен этих, больше этих, больше этих. В общем, он больше всех, это максимум абсолютно точно.

По сути, это на самом деле апгрейды что-то поменьше, но не совсем сортированного. А давайте поймём, как работает insert, как работает Remove.

Давайте мы для insert и Remove, для красоты сделаем эту кучу не до конца заполненной. Ну чтобы не надо было целый новый уровень там открывать. Давайте скажем, что у нас, ну, не хватает здесь пустые места, короче, есть.

За сколько тогда можно сделать, например, insert? Например, я хочу сделать insert числа, например, 12. Ну кажется, ничего сложного, да? Insert легко, просто дописывает сюда и вроде всё, да, но нет.

Кажется, что insert работает за одну операцию, потому что делов-то дописать в кучу и всё. Но у нас вот в самом первом шаге array был просто массив, в нём просто хранились числа и можно было в конец-то дописать и не париться, потому что не было никакой структуры у этих чисел.

И добавив одно дополнительное число, мы сохраняли то, что там нет структуры. А сейчас у нас есть какая-то структура, и добавив одно дополнительное число, ты не сохраняешь эту структуру, ты её портишь, теряешь, короче, ломаешь.

Плохо как там это число 12. Теперь, короче, мы кучу испортили. У нас теперь не соблюдается правила. А где у нас правила не соблюдается? У нас правила не соблюдается между девяткой и двенадцатью.

12 лежит на первом уровне, на самом нижнем и возражает своему родителю. Оно говорит: "Как так получилось, что ты мой начальник, а я больше тебя?" Скиловик в иерархии в компании, и он получается круче, чем его начальство.

Да, ситуация сплошь рядом встречающаяся, но вот так получилось. То есть мне нужно, чтобы все знаки неравенств были правильными, чтобы 31 было больше, чем 20, 20 было больше, чем 18, больше, чем 11, 11 было больше, чем 10.

То есть все знаки здесь работают сверху вниз, да, а вот в одном месте не сработали. Вот тут вот как бы проблема. Тогда мы, в общем, кроме обычного добавления, запускаем sift Up.

Что такое sift Up? Это, ну, sift, английская sift, это просеивание. Что такое Up? Ну это вверх, как бы, да, это типа не надо переводить, наверное.

Процедура, операция, функция просеивания. Что с ней происходит? Конкретно что она будет делать? Она будет 12 толкать вверх, как пузырёк всплывающий, пока там конфликты возникают.

Значит, смотрите, 12 и 10, они друг с другом поругались, и в итоге написали петицию в контролирующий орган. Контролирующий орган посмотрел и сказал: "Реально непорядок, не должно быть такого, чтобы сотрудник был умнее, чем начальник".

Поэтому вас понижаем, а вас повышаем. Теперь между ними всё в порядке, неравенство соблюдено, правильно?

Но у нас возникла следующая проблема. 12 и 10. Мы хотим, получается, поменять местами теперь 12 и 10. То есть вот эти вот два элемента должны поменяться.

Ну делаем ещё одну операцию замены, получается, что 10 попадает сюда, а 12 остаётся здесь. Теперь у нас соблюдается неравенство между 12 и 10.

Вопрос: вот с этим неравенством, что может ли такое быть, что 12 переназначить наверх, и теперь вот это неравенство сломалось между десяткой и восьмёркой?

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

Может ли такое быть? Вопрос ко мне. Не могло, говорят. Почему? Доказательство бы какое-нибудь, ну хотя бы маломальский.

Ну то есть можно на вот эти левые ветки не обращать внимания. В какой момент нам следует остановиться? Когда нам следует закончить процесс просеивания sift Up?

Ну в одном из двух случаев очевидно, да. Один случай - это когда мы оказались меньше, чем наш начальник, и мы такие: "Всё, удовлетворены, в этой позиции нам комфортно работается".

А вторая ситуация - это если мы стали Богом, и теперь мы начальник всего, и тогда бесполезно делать уже. Куда дальше?

Всё, соответственно, либо дошли до корня, либо упёрлись в точку, где меньше либо равно, больше либо равно. Вот это не работает. Всё хорошо.

Один из двух вариантов. Вопрос: sift по асимптоти. Сколько занимает? Ну то есть вопрос: сколько сейчас занял наш insert? Сколько мы реально операций сделали?

Одна операция добавления, а потом вот этот sift. Sift - это насколько тяжело было нам, давайте осознаем для этого. Давайте попробуем построить дерево размером N и понять, сколько шагов нам придётся вот здесь сделать.

Максимум. Максимум вот здесь три шага. Как понять количество шагов? Это глубина дерева. Что такое глубина дерева? Если в дереве N элементов, N элементов.

Давайте осознаем, что такое дерево размером K, допустим. Ну то есть, допустим, я хочу, чтобы у меня дерево было высотой. Построим полное бинарное дерево, в котором ровно K уровней.

Например, давайте один уровень равно один, одна вершина. Два уровня уже три вершины. Если у нас три уровня, то смотрите, на третьем уровне добавляется.

Пче, то есть три уровня, это у нас 3 плюс 4, 5, 7, 8, 12 и 13. Я хочу удалить вот эту пятёрку. Что мне надо сделать для того, чтобы удалить пятёрку?

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

Чем ближе к началу элемент, который мы удаляем, тем больше нам придётся сдвигать. Это о от [музыка]. Да, о от единицы удаление занимает задача.

Как удалять элемент за о от единицы? Главная задача, чтобы его просто не было в массиве. Вот просто я хочу, чтобы это какая-то куча чисел и шп элемент к чёрту пропал из массива.

Ну не куча чисел, в смысле куча, а в смысле просто много чисел были как-то напи в массив. Я просто хочу вот их хранить без какого-то порядка, без какой-то сортировки. Сортировка вообще не волнует, порядок не волнует. Хочу удалять элемент.

Как удалять какой-то элемент, чтобы при этом не пришлось весь массив двигатели? Что-то там с ним операции это более много. Ну дырку надо занять. Да, у нас массив всё-таки хранится как некоторая последовательность элементов в памяти, они все подряд, как от единиц.

Это сделать? Ну то есть давайте сотру все эти стрелочки, думать прид. Да, сегодня, к счастью или к сожалению, заставлять вас подумать, что-то придумывать для того, чтобы вы научились самостоятельно решать те задачи, которые перед вами потом будут возникать.

Пум-пурум-пурум-пурум. Пум, известен индекс, как-то перезайти. О, ладно, здесь думаете долго, не нравится. 13 просто вот сюда. Давайте переместимся не с начала, а с конца.

А удаление с конца - это вот единица, также как он, потому что, ну, мы просто потёрли один элемент, ничего сдвигать не надо. Ну типа у меня пришла вот, ну, идея удалить пятёрку, я её удалил.

Ну поменял местами, короче, 513, потом с конца удалил, всё, вот поменять местами от единицы, удалить тоже от единицы. Всё, победа.

А хорошо, следующая операция, которую я хочу, это я хочу добывать максимальный элемент. Get Max, делать, найти максимум. Сколько операций требуется для поиска максимума в обычном Python list? Давайте я пока табличку составлю, в которой будут все эти операции: операция добавления insert, операция удаления remove и операция Get Max.

Мммм, в общем случае ун, если у нас массив тупой, не отсортированный. Отлично, значит, мы научились итить иреть за от единички и удалять за от N.

Хорошо, теперь давайте мы с вами представим, что нам приходится сделать много этих операций. А, ну вместо Get Max можно ещё было бы ввести операцию Pop Max. Давайте я её где-нибудь напишу. В принципе, они идентичны.

Pop Max - это по сути, что такое? Это как бы, ну давайте функцию Pop Max определим. Она будет, значит, в X сохранять Get Max, а потом будет, собственно, X, а потом будет соб всякую специфику, типа там хип, точка и так далее.

Ну то есть не запариваюсь здесь про ОО и всё остальное, но так-то куча пишется, конечно, как класс, полноценный класс, внутри которого вы реализуете все функции кучи, бла-бла-бла.

Ну вот, собственно, массив тоже такая конструкция, которой вы применяете всё это. Ну то есть у вас там есть условно массив А, у которого определены вот эти все операции: Remove, Get Max и так далее, и вы вот Pop Max для А.

Вот так примерно выглядит. То есть Pop Max - это типа взяли максимум и за одним выкинули его из массива.

Ну и вот, давайте такая последовательность. Задача такая: мне дали N чисел в каком-то порядке, подают их по очереди. Я их должен все считать, все их сохранить, а потом по очереди что-то я буду делать с их максимумами.

То есть мне почему-то важно именно вот в какой-то последовательности извлекать их максимумы и по пути что-то с этими максимумами делать.

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

Ну можно придумать какую-нибудь задачу, в которой мне, короче, на каждом шаге нужно максимум, типа там, я не знаю, какой-нибудь там чувак из племени Тумба-Юмба даёт нам числа и иногда, время от времени, говорит: "А какое сейчас максимальное число среди тех, которые я вам дал?" И вы такие: "А вот оно, число максимальное". Вы говорите: "О'кей, хорошо".

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

Ну и давайте скажем, что в этой задаче у нас, допустим, N запросов на добавление, то есть нам дают N чисел и N запросов на удаление. На удаляем мы сразу после того, как Get Max взяли. Тогда у нас решение этой задачи с помощью Python.

Сколько времени операций? Это к вам вопрос. А поставьте плюс в чат все, кто понимает, что там работает за O от N, и минус, кто не понимает, почему Get Max работает за O от N. Это сложная задача.

Мы сразу такие, типа, с места в карьер прыгнули в какие-то, ну, нормальные задачки. Хорошо, есть плюсики, отлично.

Ну я вижу, что плюсики, конечно же, поставит Михаил, Капитан и Данила, потому что они ответили, он сами. Ну может кто-то минус, например, влепит и скажет, что-то сложно.

Сколько времени займёт выполнение решения задачи, в которой N запрос