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

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

Опубликовано 12 минут на чтение Слайды
Оглавление

Часто возникает необходимость «сортировать» динамический набор данных. Самым ярким примером такой задачи является очередь с приоритетом. По сути задача сводится к последовательному выбору минимумов из множества, при этом допускающего добавление к множеству новых элементов. Конечно, эту задачу можно решить с помощью сортировки начального множества, а новые элементы можно включать с помощью бинарной вставки. Однако, есть структуры данных, позволяющие реализовать необходимые операции за меньшую стоимость. Такая структура называется куча (heap).

Определение и базовые операции

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

graph TD A((1)) A---B((3)) A---C((2)) A---D((4)) B---E((4)) C---F((8)) C---G((8)) C---H((5)) D---I((5)) D---J((4)) E---K((9)) E---L((17)) H---M((9)) H---N((21)) J---O((10))
Рис. 1.

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

  • получение минимума (peek);
  • извлечение минимума (pop);
  • добавление элемента (push);

Собственно минимум в такой структуре всегда находится в корне, поэтому его получение имеет сложность \(O(1)\). А две другие операции требуют операций для восстановления кучи.

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

Нарушение свойства кучи «любой элемент не меньше своего родителя» в одном из её элементов будем называть аномалией. Аномалии могут возникнуть по двум причинам: большой элемент оказался слишком высоко в дереве или, наоборот, маленький элемент оказался слишком низко в дереве.

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

Первый случай является результатом извлечения минимума следующим способом: так как непустое дерево не может существовать без корня, поместим на место корня любой листовой элемент (удалив его предварительно).

graph TD A((10)) A---B((3)) A---C((2)) A---D((4)) B---E((4)) C---F((8)) C---G((8)) C---H((5)) D---I((5)) D---J((4)) E---K((9)) E---L((17)) H---M((9)) H---N((21)) J---O((10)) style A fill:lightGreen style O fill:pink,opacity:0.2
Рис. 2.

Таким образом у нас появилась аномалия в корне. Для её устранения необходимо выбрать минимальный элемент из первого уровня дерева и поменять его с корнем.

graph TD A((2)) A---B((3)) A---C((10)) A---D((4)) B---E((4)) C---F((8)) C---G((8)) C---H((5)) D---I((5)) D---J((4)) E---K((9)) E---L((17)) H---M((9)) H---N((21)) style A fill:lightGreen style C fill:pink
Рис. 3.

При этом аномалия смещается вместе с корнем в узел меньшего сына. Но эта ситуация аналогична предыдущей, только для поддерева от этого узла и решается тем же способом.

graph TD H((9)) H---M((10)) H---N((21)) style H fill:lightGreen style M fill:pink
Рис. 5.

При этом очевидно, что подобный спуск не может вызвать аномалии в других частях кучи. Такая перестановка называется погружением элемента (sift down). Очевидно, что сложность такой операции не превышает высоты кучи при ограниченной степени ветвления дерева (но об этом позже).

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

Другая аномалия является следствием добавления нового элемента. Новый элемент мы можем добавить как лист к одному из узлов дерева.

graph TD A((2)) A---B((3)) A---C((5)) A---D((4)) B---E((4)) C---F((8)) C---G((8)) C---H((9)) D---I((5)) D---J((4)) E---K((9)) E---L((17)) H---M((10)) H---N((21)) J---O((2)) style O fill:lightGreen
Рис. 6.

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

graph TD A((2)) A---B((3)) A---C((5)) A---D((2)) B---E((4)) C---F((8)) C---G((8)) C---H((9)) D---I((5)) D---J((4)) E---K((9)) E---L((17)) H---M((10)) H---N((21)) J---O((4)) style A fill:pink style D fill:lightGreen style J fill:pink style O fill:pink
Рис. 7.

Такая перестановка называется всплытием элемента (sift up) и также имеет сложность не превышающую глубины кучи, вне зависимости от степени ветвления.

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

Всё бы хорошо, но работа с деревьями произвольной формы не самое приятное занятие для компьютера. Чаще всего это сводится к куче указателей и нелокальности данных. Но, если добавить дополнительных ограничений на кучу, то её можно очень компактно расположить в памяти без единого указателя. Во-первых, необходимо ограничить степень ветвления двумя. Кроме того добавим следующие ограничения:

  • глубина всех листьев отличается не более, чем на \(1\);
  • последний слой заполняется слева направо без пропусков;

Тогда узлы такого дерева могут быть однозначно пронумерованы:

graph TD A((0)) A---B((1)) A---C((2)) B---D((3)) B---E((4)) C---F((5)) C---G((6)) D---H((7)) D---I((8)) E---J((9)) E---K((10)) F---L((11)) F---M((12)) G---N((13)) G---O((14)) style M opacity:0.2 style N opacity:0.2 style O opacity:0.2
Рис. 8.

Для \(i\)-го узла следует, что его родитель будет иметь индекс \(\lfloor (i - 1) / 2 \rfloor\), а его сыновья — \(2i + 1\) и \(2i + 2\). Это позволяет хранить элементы такого дерева в массиве, однозначно определяя связи в дереве через индексы. Такая структура и называется двоичной кучей.

Давайте рассмотрим реализацию этой структуры.

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 pop(self):
        if len(self._items) > 0:
            x = self._items[0]
            self._items[0] = self._items[len(self._items)-1]
            self._items.pop()
            self._sift_down(0)
            return x

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

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

            self._items[i], self._items[j] = self._items[j], self._items[i]
            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, который возвращает индекс меньшего сына, если хотя бы один из сыновей существует, отдавая предпочтение правому сыну среди равных (?).

Заметим, что двоичная куча представляет собой полностью сбалансированное двоичное дерево, а значит его высота равна \(\lfloor 1 + \log n \rfloor\), где \(n\) — количество его узлов. Таким образом сложность операций извлечения минимума и добавление элемента равна \(O(\log n)\).

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

Помимо описанных операций, часто требуется поддержка таких операций как уменьшение ключа (decrease_key), удаление (delete) и слияние (meld). Первая операция предоставляет возможность уменьшить значение определённого элемента. По сути можно просто обновить значение ключа в дереве, после чего выполнить всплытие этого элемента. Операция удаления в целом аналогична извлечению минимума, то есть удаляемый элемент заменяется последним листом, после чего выполняется погружение этого элемента.

Локаторы

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

Поддерживать такие локаторы достаточно просто: по сути все операции изменения кучи можно реализовать с помощью примитива \(swap(i, j)\), обменивающего два элемента в массиве. Тогда в рамках этой операции можно также обменивать значения по локаторам.

class BinaryHeapWithLocators:
    _items = []
    _locators = []

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

    def push(self, x):
        p = len(self._locators)
        self._locators.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._locators[p]
        self._items[i] = (self._items[i][0] - x, p)
        self._sift_up(i)

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

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

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

    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][0] < self._items[r_son][0]:
            return l_son

        return r_son

В целом такое решение выглядит неплохо, пока куча не начинает использоваться как очередь. Использование же её как очереди означает то, что при более или менее постоянном размере кучи через неё будет проходить большое число сообщений. В этих условиях такая реализация локаторов будет сильно разрастаться. По факту массив локаторов будет увеличиваться с каждым новым элементом и никогда не будет уменьшаться. Для работы в таком режиме необходимо переиспользовать локаторы удалённых элементов.

Слияние

Операция слияния также часто востребована, однако, двоичная куча не позволяет эффективно её реализовать. Если требуется слияние, то необходимо воспользоваться другими имплементациями, например, биномиальной или левацкой кучами.

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

В текущей реализации куча инициализируется пустой. Добавление элемента имеет сложность \(O(\log n)\), таким образом добавление \(n\) элементов будет стоить \(O(n \log n)\). Пытливый читатель заметит, что сложность добавления зависит от совсем другого \(n\), а именно от количества элементов в куче, но это не имеет особого значение, потому что сложность всех операций будет равна \[ 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). \] Воспользуемся неравенством Йенсена: \[ T(n) = 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)\). Представим его в виде бинарного дерева.

graph TD A((4)) A---B((2)) A---C((12)) B---D((83)) B---E((45)) C---F((3)) C---G((21)) D---H((67)) D---I((11)) E---J((32)) E---K((37)) F---L((9)) F---M((1)) G---N((15)) G---O((7))
Рис. 9.

Начиная с последнего элемента будем выполнять процедуру погружения элемента. Собственно с листями ничего не произойдёт, потому как их больше некуда погружать. Так что начинать надо с 6-го элемента.

graph TD A((4)) A---B((2)) A---C((12)) B---D((83)) B---E((45)) C---F((3)) C---G((7)) D---H((67)) D---I((11)) E---J((32)) E---K((37)) F---L((9)) F---M((1)) G---N((15)) G---O((21)) style G fill:lightGreen style O fill:pink
Рис. 10.

Продолжим итерирование по элементам 2-го слоя. ПОд конец получим следующее дерево.

graph TD A((4)) A---B((2)) A---C((12)) B---D((11)) B---E((32)) C---F((1)) C---G((7)) D---H((67)) D---I((83)) E---J((45)) E---K((37)) F---L((9)) F---M((3)) G---N((15)) G---O((21)) 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
Рис. 11.

Продолжив погружение элементов вплоть до нулевого, получим дерево, в каждой вершине удовлетворяющее условиям кучи.

graph TD A((1)) A---B((2)) A---C((3)) B---D((11)) B---E((32)) C---F((4)) C---G((7)) D---H((67)) D---I((83)) E---J((45)) E---K((37)) F---L((9)) F---M((12)) G---N((15)) G---O((21)) 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
Рис. 12.

Заметим, что для любого рассмотренного элемента, поддерево с корнем в этом элементе удовлетворяет условиям кучи. Таким образом для каждого вновь рассматриваемого элемента мы имеем следующее:

graph TD A((x)) A---B{α} A---C{β}
Рис. 13.

Где \(\alpha\) и \(\beta\) являются кучами, и аномалия возможна только в вершине \(x\). Отметим также, что для \(i\)-го элемента максимальная глубина его погружения будет равна разнице между его глубиной и глубиной всего дерева \(O(\log n - \log i)\). Тогда суммарное сложность всех операций будет состоять из одной операции погружения корня, двух операций погружения его сыновей, четырёх операций погружения внуков и так далее. Для \(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 O\left(n \sum_{k = 0}^{\infty} \frac{k}{2^k} \right) \]

Ряд является сходящимся, а значит можно принять его за константу и отбросить по свойству \(O\). В итоге получаем \(T(n) = 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). \]

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

Пирамидальная сортировка является своего рода улучшением сортировки выбором, где, вместо линейного поиска минимума на каждом шаге, входной массив преобразуется в двоичную кучу и на каждом шаге из неё извлекается минимум, что требует \(\log n\) операций. Таким образом сложность всей сортировки равна \(O(n \log n)\) (?). Этот алгоритм можно реализовать без дополнительной памяти. Для этого на каждом шаге будем менять первый и последний элемент кучи, после чего будем считать, что куча становится на 1 элемент короче. После этого будем выполнять погружение корня. Таким образом мы получим убывающую последовательность минимумов в конце массива. На последнем шаге куча станет нулевой длинны, а массив будет отсортирован в порядке убывания.

graph TD A((21)) A---B((2)) A---C((3)) B---D((11)) B---E((32)) C---F((4)) C---G((7)) D---H((67)) D---I((83)) E---J((45)) E---K((37)) F---L((9)) F---M((12)) G---N((15)) G---O((1)) style O fill:lightGreen, opacity:0.5 style A fill:pink
Рис. 14.
graph TD A((2)) A---B((11)) A---C((3)) B---D((21)) B---E((32)) C---F((4)) C---G((7)) D---H((67)) D---I((83)) E---J((45)) E---K((37)) F---L((9)) F---M((12)) G---N((15)) G---O((1)) style O fill:lightGreen, opacity:0.5 style A fill:yellow style B fill:yellow style D fill:pink
Рис. 15.
graph TD A((15)) A---B((11)) A---C((3)) B---D((21)) B---E((32)) C---F((4)) C---G((7)) D---H((67)) D---I((83)) E---J((45)) E---K((37)) F---L((9)) F---M((12)) G---N((2)) G---O((1)) style O fill:lightGreen, opacity:0.5 style N fill:lightGreen, opacity:0.5 style A fill:pink
Рис. 16.
graph TD A((3)) A---B((11)) A---C((4)) B---D((21)) B---E((32)) C---F((9)) C---G((7)) D---H((67)) D---I((83)) E---J((45)) E---K((37)) F---L((15)) F---M((12)) G---N((2)) G---O((1)) 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
Рис. 17.
graph TD A((12)) A---B((11)) A---C((4)) B---D((21)) B---E((32)) C---F((9)) C---G((7)) D---H((67)) D---I((83)) E---J((45)) E---K((37)) F---L((15)) F---M((3)) G---N((2)) G---O((1)) 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
Рис. 18.
graph TD A((4)) A---B((11)) A---C((7)) B---D((21)) B---E((32)) C---F((9)) C---G((12)) D---H((67)) D---I((83)) E---J((45)) E---K((37)) F---L((15)) F---M((3)) G---N((2)) G---O((1)) 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
Рис. 19.

Одним из главных недостатков пирамидальной сортировки является то, что её невозможно сделать стабильной без дополнительной памяти. Поэтому она практически не встречается, в отличии от самой структуры данных.

Применение

Кучи имеют широкое применение в других алгоритмах. Наиболее известный, использующий кучу в виде очереди с приоритетом, алгоритм Дейкстры поиска кратчайшего пути в графе. Другой, не менее значимый алгоритм — параллельное слияние множества отсортированных массивов. Интересным применением кучи является структура под названием дуча или декартово дерево.

Вопросы

  1. ^ Почему надо отдавать предпочтение именно правому сыну, если они равны?
  2. ^ Какие допущения сделаны в рассуждениях? Почему эти допущения разрешены?
  3. ^ Можно ли улучшить оценку в лучшем случае? Если можно, то как? Если нельзя, то почему?

Задания

  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. https://webdocs.cs.ualberta.ca/~hayward/papers/heap.pdf
  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. http://cglab.ca/~morin/teaching/5408/refs/minmax.pdf
  3. Brodal, Gerth S. “Worst-Case Efficient Priority Queues.” Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, 1996, pp. 52–58. http://tildeweb.au.dk/au121/papers/soda96.pdf

Ссылки

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