Семинар 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?