Алгоритмы теория и практика Методы - 56 урок. Очереди с приоритетами
Ссылка на плейлист со всеми уроками "Алгоритмы теория и практика Методы" - https://www.youtube.com/watch?v=30PzSv4ZIBU&list=PLoWGNURguz9Xk248HDiJICojc-0rlayUW ________________ Автор: Александр Куликов, Сергей Лебедев, Алексей Левин, Павел Маврин Лицензия: https://creativecommons.org/licenses/by-sa/4.0/ Источник: https://stepik.org/course/217 ___________________ Задание для закрепления: Выберите все верные утверждения из списка: * Массив A[1..7]=[3, 8, 4, 9, 7, 5, 6]A[1..7]=[3,8,4,9,7,5,6] является мин-кучей. * Массив A[1..3]=[4, 2, 5]A[1..3]=[4,2,5] является макс-кучей. * Массив A[1..12]=[3, 20, 6, 30, 21, 30, 5, 31, 60, 30, 31, 31]A[1..12]=[3,20,6,30,21,30,5,31,60,30,31,31] является мин-кучей. * Массив A[1..3]=[10, 14, 11]A[1..3]=[10,14,11] является мин-кучей. ________________________ Задание для закрепления: Тест: dd-ичная куча В двоичной куче у каждой вершины до двух детей; в dd-ичной — до dd. Отметьте все верные утверждения про dd-ичные кучи (в оценках ниже параметр dd присутствует под O(\cdot), \Omega(\cdot), \Theta(\cdot)O(⋅),Ω(⋅),Θ(⋅), поскольку dd может зависеть от nn). Выберите все подходящие ответы из списка * Родителем вершины ii является вершина \lceil (i-1)/d \rceil⌈(i−1)/d⌉. * Детьми вершины ii являются вершины \{(i-1)d+1, \ldots, \min\{n, (i-1)d+d\}\}{(i−1)d+1,…,min{n,(i−1)d+d}}. * Высота есть \Theta(d\log n)Θ(dlogn). * Время работы операции {\tt SiftUp}SiftUp есть \Theta(d\log_d n)Θ(dlog d n). * Родителем вершины ii является вершина \lceil i/d \rceil⌈i/d⌉. * Детьми вершины ii являются вершины \{id+2, \ldots, \min\{n, id+d+1\}\}{id+2,…,min{n,id+d+1}}.
Ссылка на плейлист со всеми уроками "Алгоритмы теория и практика Методы" - https://www.youtube.com/watch?v=30PzSv4ZIBU&list=PLoWGNURguz9Xk248HDiJICojc-0rlayUW ________________ Автор: Александр Куликов, Сергей Лебедев, Алексей Левин, Павел Маврин Лицензия: https://creativecommons.org/licenses/by-sa/4.0/ Источник: https://stepik.org/course/217 ___________________ Задание для закрепления: Выберите все верные утверждения из списка: * Массив A[1..7]=[3, 8, 4, 9, 7, 5, 6]A[1..7]=[3,8,4,9,7,5,6] является мин-кучей. * Массив A[1..3]=[4, 2, 5]A[1..3]=[4,2,5] является макс-кучей. * Массив A[1..12]=[3, 20, 6, 30, 21, 30, 5, 31, 60, 30, 31, 31]A[1..12]=[3,20,6,30,21,30,5,31,60,30,31,31] является мин-кучей. * Массив A[1..3]=[10, 14, 11]A[1..3]=[10,14,11] является мин-кучей. ________________________ Задание для закрепления: Тест: dd-ичная куча В двоичной куче у каждой вершины до двух детей; в dd-ичной — до dd. Отметьте все верные утверждения про dd-ичные кучи (в оценках ниже параметр dd присутствует под O(\cdot), \Omega(\cdot), \Theta(\cdot)O(⋅),Ω(⋅),Θ(⋅), поскольку dd может зависеть от nn). Выберите все подходящие ответы из списка * Родителем вершины ii является вершина \lceil (i-1)/d \rceil⌈(i−1)/d⌉. * Детьми вершины ii являются вершины \{(i-1)d+1, \ldots, \min\{n, (i-1)d+d\}\}{(i−1)d+1,…,min{n,(i−1)d+d}}. * Высота есть \Theta(d\log n)Θ(dlogn). * Время работы операции {\tt SiftUp}SiftUp есть \Theta(d\log_d n)Θ(dlog d n). * Родителем вершины ii является вершина \lceil i/d \rceil⌈i/d⌉. * Детьми вершины ii являются вершины \{id+2, \ldots, \min\{n, id+d+1\}\}{id+2,…,min{n,id+d+1}}.