Тотальный гайд на Heap & Priority Queue для собеса в IT и Leetcode алгоритмов (уникальный, практика)

Telegram: t.me/dev_pushkin
Leetcode: leetcode.com/idfumg
GitHub: github.com/idfumg
C++: gist.github.com/idfumg/6a16c4...
Py: gist.github.com/idfumg/5b08e0...
Go: gist.github.com/idfumg/435fab...
Всем, кому интересно полностью разобраться, что такое Priority Queue и Heap, Heap Sort, как они работают, какая у них сложность и как реализовать и применять их самому, для вас есть видео на KZbin канале. Постарался максимально полно описать все, что нужно про нее знать. Привел пример про time complexity построения Heap, почему она O(n) и почему это так при условии ее построения через Heapify Down. Протестировал ее работоспособность на Leetcode, применив реализованную нами Heap, а не из стандартной библиотеки. Встречается прямо очень часто в самых разных задачах или как часть решения более сложных задач.
Алгоритмы - это интересно и не сложно. Пробуем решать задачи на Leetcode, разговариваем, наглядно рисуем решения, узнаем что-то новое.
Time Complexity: stackoverflow.com/questions/9...
#c++ #python #go #golang #priority_queue #heap #programming #data_structures #algorithms #computerscience

[@umni_kot]

Спасибо рекомендациям ютуб что посоветовал ваше видео. И спасибо за ценный материал. Буду еще смотреть ваши видосы

[@stasstas808]

Отличное видео! Спасибо!

[@tejinaji]

Спасибо за труд, пересмотрю на репите)

[@user-qo1oz1en2w]

Отличное объяснение! Спасибо за труды. Правда не понял восторга от применения heap-а в задаче с k-ым максимальным. Сложность будет сложность вроде таже, что и сортировкой, nlog(n). Поправьте, если ошибаюсь

[@user-qo1oz1en2w]

Хотя нет, инициализируем за k, потом добавляем (n-k) элементов, то есть O(k + (n-k)log(n)), прирост действительно неплохой при больших k

[@dev_pushkin]

Привет! Хороший вопрос. У нас есть n элементов и окно размера k. И оно так и останется максимального размера k в течение работы. Каждый новый элемент добавляется в окно и если инвариант нарушается в окне (window size == k + 1), мы убираем лишний (снова k). То есть глубина нашего дерева будет всегда log(k). Для каждого элемента мы свапнем его максимум log(k) раз. В целом тут k может быть равно n и тогда в крайнем случае действительно будет nlog(n). В среднем случае (считаем, что k чаще не очень большая) будет nlog(k). Например, если log(k) == 2 - мы рядом с "линейной сложностью" с константой C == 2. Тут есть еще один ньюанс. Heap на массиве - чрезвычайно cache friendly data structure и может при не большом k (