Семинар 1. Куча

Задачи с практики

1. В биномиальную кучу размера \(n\) добавляется один элемент. Как быстро понять, сколько операций слияния биномиальных деревьев произойдет?

2. Добавьте в биномиальную кучу операцию увеличения ключа за время \(\mathcal O(\log n)\). Сработает ли она в других кучах?

3. Придумайте структуру на основе кучи, которая умеет делать insert(x), getMedian(), deleteMedian() за время \(\mathcal O(\log n)\).

4. Пусть подряд выполняется \(n\) операций insert в изначально пустую биномиальную кучу. Какое среднее время выполнения операции?

5. Рассмотрим структуру данных Weak Heap. Она хранится как обычная бинарная куча за тем исключением, что у корня есть только правый сын. Таким образом, ее можно хранить в 0-индексированном массиве, так что у вершины \(i\) дети \(2i\) и \(2i+1\), кроме корня в индексе \(0\) с одним ребёнком \(1\).

   Кроме того, чтобы удобно было менять поддеревья местами, для каждого \(i\) хранится дополнительный бит \(r_i\), обозначающий, что вершина \(2i\) — левый сын вершины \(i\), если \(r_i=0\), и правый, если \(r_i=1\). Также у Weak Heap есть инвариант (более слабый, чем у кучи): все вершины в правом поддереве каждой вершины \(v\) имеют не меньший ключ, чем у \(v\). Ключи в левом поддереве могут быть произвольными — как меньше, так и больше.

   Операции add и extractMin, как и в бинарной куче, выражаются через siftUp и siftDown:

   • extractMin() — это

   {
       --n;
       swap(h[0], h[n]);
       siftDown(0);
   }
   

   • add(x) — это

   {
       ++n;
       h[n - 1] = x;
       siftUp(n - 1);
   }
   

   A. Придумайте, как найти минимум в Weak Heap за \(\mathcal O(1)\).

   B. Сделайте siftUp за \(\mathcal O(\log n)\).

   C. Найдите второй минимум за \(\mathcal O(\log 𝑛)\).

   D. Как наиболее эффективно сделать siftDown?