Простая двоичная куча

А я угадаю этот минимум за O(1) Назад

Двоичная куча

План

  1. задача и применение
  2. куча: определение и базовые операции
  3. двоичная куча: определение и индексация
  4. реализация базовых операций
  5. другие операции и итераторы
  6. эффективное построение кучи
  7. пирамидальная сортировка

Задача и применение

Задача

Очередь с приоритетом
вектор с координатами из линейно упорядоченного множества, на котором определены две операции:
  • добавление элемента
  • извлечение минимума

Применение

Решения?

Куча

Определение

Куча (heap)
дерево, в котором любой элемент не меньше своего родителя.

Пример 

</figcaption>

Базовые операции

На таком дереве несложно реализовать три основные операции, производимые с куче:

Восстановление свойств кучи

Аномалия
нарушение свойства кучи любой элемент не меньше своего родителя в одном из её элементов.

Аномалии могут возникнуть по двум причинам:

Погружение элемента 

style A fill:pink

</figcaption>

Погружение элемента 

style A fill:lightGreen
style C fill:pink

</figcaption>

Погружение элемента 

style C fill:lightGreen
style H fill:pink

</figcaption>

Погружение элемента 

style H fill:lightGreen
style M fill:pink

</figcaption>

Извлечение минимума (pop)

  1. сохраним значение корня
  2. запишем поверх корня любой листовой элемент
  3. удалим этот лист из дерева
  4. выполним погружение корня
  5. вернём сохранённое значение корня

Всплытие элемента 

style O fill:pink

</figcaption>

Всплытие элемента 

style J fill:pink
style O fill:lightGreen

</figcaption>

Всплытие элемента 

style D fill:pink
style J fill:lightGreen

</figcaption>

Всплытие элемента 

style A fill:pink
style D fill:lightGreen

</figcaption>

Добавление элемента (push)

  1. добавляем новый элемент листом
  2. выполняем всплытие этого элемента

Двоичная куча

Двоичная куча

Добавим следующие ограничения:

Двоичная куча 

style M opacity:0.2
style N opacity:0.2
style O opacity:0.2

</figcaption>

Индексация

Для \(i\)-го узла

Высота дерева: \(\lceil 1 + \log n \rceil\)

Реализация

Реализация 

class BinaryHeap:
    _items = []
    def peek(self):
        if len(self._items) > 0:
            return self._items[0]
    def push(self, x):
        self._items.append(x)
        self._sift_up(len(self._items) - 1)

Реализация 

    def _sift_up(self, i):
        while i > 0:
            j = (i - 1) // 2
            if self._items[j] <= self._items[i]:
                break
            self._swap(i, j)
            i = j

Реализация 

    def pop(self):
        if len(self._items) > 0:
            x = self._items[0]
            self._swap(0, len(self._items)-1)
            self._items.pop()
            self._sift_down(0)
            return x

Реализация 

    def _sift_down(self, i):
        while True:
            j = self._min_son(i)
            if not j or self._items[i] <= self._items[j]:
                break
            self._swap(i, j)
            i = j

Реализация 

    def _min_son(self, i):
        l_son = i * 2 + 1
        r_son = i * 2 + 2
        if len(self._items) <= l_son:
            return None
        if len(self._items) <= r_son or self._items[l_son] < self._items[r_son]:
            return l_son
        return r_son

Оптимизации

Метод _min_son возвращает индекс меньшего сына, если хотя бы один из сыновей существует, отдавая предпочтение правому сыну среди равных

Другие операции и итераторы

Другие операции

Итераторы

Динамические указатели на элементы структуры, поддерживаемые самой структурой.

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

Реализация с итераторами 

class BinaryHeapWithIterators:
    _items = []
    _iterators = []

    def peek(self):
        if len(self._items) > 0:
            return self._items[0][0]

Реализация с итераторами 

    def push(self, x):
        p = len(self._iterators)
        self._iterators.append(len(self._items))
        self._items.append((x, p))
        self._sift_up(len(self._items) - 1)
        return p

Реализация с итераторами 

    def pop(self):
        if len(self._items) > 0:
            x = self._items[0]
            self._swap(0, len(self._items)-1)
            self._items.pop()
            self._sift_down(0)
            return x[0]

Реализация с итераторами 

    def decrease(self, p, x):
        i = self._iterators[p]
        self._items[i] = (self._items[i][0] - x, p)
        self._sift_up(i)

Реализация с итераторами 

    def _swap(self, i, j):
        self._iterators[self._items[i][1]] = j
        self._iterators[self._items[j][1]] = i
        self._items[i], self._items[j] = self._items[j], self._items[i]

Слияние

\[ T(n, m) = O(n \log m) \]

Эффективные реализации:

Эффективное построение кучи

Добавление элементов в пустую кучу

\[ T(n) = O\left(\log 1 + \log 2 + \ldots + \log(n - 1)\right) = \] \[ = O\left(n \left(\frac{\log 1 + \log 2 + \ldots + \log(n - 1)}{n}\right)\right) = \] по неравенству Йенсена: \[ = O\left(n \log\left(\frac{1 + 2 + \ldots + n - 1}{n}\right)\right) = O\left(n \log\left(\frac{n - 1}{2}\right)\right) = O(n \log n). \]

Эффективное построение кучи

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

Пусть дан массив начальных элементов \((4, 2, 12, 83, 45, 3, 21, 67, 11, 32, 37, 9, 1, 15, 7)\)

Эффективное построение кучи 

</figcaption>

Эффективное построение кучи 

style G fill:lightGreen
style O fill:pink

</figcaption>

Эффективное построение кучи 

style F fill:lightGreen
style M fill:pink

</figcaption>

Эффективное построение кучи 

style E fill:lightGreen
style J fill:pink

</figcaption>

Эффективное построение кучи 

style D fill:lightGreen
style I fill:pink

</figcaption>

Эффективное построение кучи 

style D fill:lightGreen
style E fill:lightGreen
style F fill:lightGreen
style G fill:lightGreen
style H fill:lightGreen
style I fill:lightGreen
style J fill:lightGreen
style K fill:lightGreen
style L fill:lightGreen
style M fill:lightGreen
style N fill:lightGreen
style O fill:lightGreen

</figcaption>

Эффективное построение кучи 

style C fill:lightGreen
style D fill:lightGreen
style E fill:lightGreen
style F fill:lightGreen
style G fill:lightGreen
style H fill:lightGreen
style I fill:lightGreen
style J fill:lightGreen
style K fill:lightGreen
style L fill:lightGreen
style M fill:lightGreen
style N fill:lightGreen
style O fill:lightGreen

</figcaption>

Эффективное построение кучи 

style B fill:lightGreen
style C fill:lightGreen
style D fill:lightGreen
style E fill:lightGreen
style F fill:lightGreen
style G fill:lightGreen
style H fill:lightGreen
style I fill:lightGreen
style J fill:lightGreen
style K fill:lightGreen
style L fill:lightGreen
style M fill:lightGreen
style N fill:lightGreen
style O fill:lightGreen

</figcaption>

Эффективное построение кучи 

style A fill:lightGreen
style B fill:lightGreen
style C fill:lightGreen
style D fill:lightGreen
style E fill:lightGreen
style F fill:lightGreen
style G fill:lightGreen
style H fill:lightGreen
style I fill:lightGreen
style J fill:lightGreen
style K fill:lightGreen
style L fill:lightGreen
style M fill:lightGreen
style N fill:lightGreen
style O fill:lightGreen

</figcaption>

Эффективное построение кучи 

</figcaption>

\(\alpha\) и \(\beta\) являются кучами

Эффективное построение кучи

Для \(k\)-го (снизу) слоя будет произведено не более чем \(n / 2^k\) операций погружения. При этом каждая операция погружения будет иметь сложность \(O(k)\). \[ T(n) = \sum_{k = 0}^{\log n} \frac{n}{2^k} O(k) = O\left(\sum_{k = 0}^{\log n} \frac{n}{2^k} k\right) = O\left(n \sum_{k = 0}^{\log n} \frac{k}{2^k} k\right) \leqslant \] \[ \leqslant O\left(n \sum_{k = 0}^{\infty} \frac{k}{2^k} \right) = O(nc) = O(n) \]

Рекурентная формула

\[ T(1) = 1 \quad\text{и}\quad T(h) \leqslant O(2T(h - 1) + ch), \] \(h\) — высота преобразуемого дерева, \(c\) — некоторая константа \[ T(h) \leqslant O(c(2^{h + 1} - h - 2)) \leqslant O(c2^{h + 1}) \leqslant O(2cn). \]

Пирамидальная сортировка

Пирамидальная сортировка 

style O fill:lightGreen, opacity:0.5
style A fill:pink

</figcaption>

Пирамидальная сортировка 

style O fill:lightGreen, opacity:0.5
style A fill:yellow
style B fill:yellow
style D fill:pink

</figcaption>

Пирамидальная сортировка 

style O fill:lightGreen, opacity:0.5
style N fill:lightGreen, opacity:0.5
style A fill:pink

</figcaption>

Пирамидальная сортировка 

style O fill:lightGreen, opacity:0.5
style N fill:lightGreen, opacity:0.5
style A fill:yellow
style C fill:yellow
style F fill:yellow
style L fill:pink

</figcaption>

Пирамидальная сортировка 

style O fill:lightGreen, opacity:0.5
style N fill:lightGreen, opacity:0.5
style M fill:lightGreen, opacity:0.5
style A fill:pink

</figcaption>

Пирамидальная сортировка 

style O fill:lightGreen, opacity:0.5
style N fill:lightGreen, opacity:0.5
style M fill:lightGreen, opacity:0.5
style A fill:yellow
style C fill:yellow
style G fill:pink

</figcaption>

Задания

  1. Реализуйте кучу с итераторами, переиспользующую свободные ячейки массива итераторов. Напишите тест, позволяющий проверить, что при многократном цикле push-pop память структуры не растёт.
  2. Реализуйте конструктор, принимающий массив данных и преобразующий их в кучу за линейное время.
  3. Реализуйте пирамидальную сортировку.

Дополнительное чтение

  1. Ryan Hayward, Ryan, and McDiarmid, Colin. “Average Case Analysis of Heap Building.” Journal of algorithms, vol. 12, no. 1, 1991, pp. 126–153.
  2. Atkinson, M.D., Sack, J.-R., Santoro, N., and Strothotte, T. “Min-max heaps and generalized priority queues.” Programming techniques and Data structures. Comm. ACM, vol. 29, no. 10, 1986, pp. 996–1000.
  3. Brodal, Gerth S. “Worst-Case Efficient Priority Queues.” Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, 1996, pp. 52–58.

Ссылки

  1. Вирт, Никлаус. Алгоритмы и структуры данных. Новая версия для Оберона. Перевод Ткачев, Ф. В., М.: ДМК Пресс, 2016.
  2. Асанов, М. О., Баранский, В. А., и Расин, В. В. Дискретная математика: графы, матроиды, алгоритмы. 2-е издание, СПб.: Издательство «Лань», 2010.

Спасибо за внимание