Могучая куча

Heaping It On

В этой главе мы изучим

• In this chapter, you will learn:

• Два абстрактных типа данных — очередь и приоритезированную очередь. • The queue and priority queue data types.

• Изобретённую в 1964 году структуру данных — двоичную кучу — которую можно хранить в обычном массиве. • The binary heap data structure, invented in 1964, which can be stored in an array.

• Двоичную кучу с порядком убывания, в которой элемент, имеющий наибольшее числовое значение приоритета считается элементом с наивысшим приоритетом, и двоичную кучу с порядком возрастания, в которой наивысшим считается приоритет с минимальным числовым значением. • That in a max binary heap, an entry with a larger numeric priority is considered to have higher priority than an entry with a smaller numeric priority. In a min binary heap, entries with smaller numeric priority have higher priority.

• Как добавить пару (значение, приоритет) в двоичную кучу за O(log N) операций, где N — количество элементов в куче. • How to enqueue a (value, priority) entry to a binary heap in O(log N), where N (is the number of entries in the heap.

• Как и где найти в двоичной куче элемент с наивысшим приоритетом за O(1) операций. How to find the value with highest priority in a binary heap in O(1).

• Как снять с вершины двоичной кучи элемент с наивысшим приоритетом за O(log N) операций. • How to remove the value with highest priority from a binary heap in O(log N).

Что если мы будем хранить не просто набор значений, а набор пар, в котором каждому значению будет сопоставлен некоторый числовой приоритет? Будем считать, что чем выше приоритет, тем «важнее» для нас значение, так что на этот раз нам нужно уметь только добавлять пару (значение, приоритет) и получать из нашей структуры одно значение с наивысшим приоритетом, одновременно удаляя его оттуда (это называется операцией снятия). Instead of just storing a collection of values, what if you stored a collection of entries, where each entry has a value and an associated priority represented as a number? Given two entries, the one whose priority is higher is more important than the other. The challenge this time is to make it possible to insert new (value, priority) entries into a collection and be able to remove and return the value for the entry with highest priority from the collection.

Мы сейчас описали работу т. н. «приоритезированной очереди» — структуры данных, в которой эффективно реализованы две операции: добавления пары enqueue(значение, прироритет) и снятия (удаления + возврата) значения с наивысшим приоритетом значение = dequeue(). Приоритезированная очередь не похожа на уже изученные нами в предыдущей главе хеш-таблицы: нам не нужно заранее знать приоритет, чтобы снять наиболее приоритетное значение. This behavior defines a priority queue—a data type that efficiently supports enqueue(value, priority) and dequeue(), which removes the value with highest priority. The priority queue is different from the symbol table discussed in the previ‐ ous chapter because you do not need to know the priority in advance when requesting to remove the value with highest priority.

Допустим, ночной клуб переполнен, и у входа уже выстроилась очередь, как на иллюстрации 4-1. Для того, чтобы попасть внутрь, каждый вновь пришедший должен встать в конец очереди. Первым попадёт в клуб человек из начала очереди — он ждал дольше всех. Так работает собственно очередь — структура данных, в которой предусмотрена операция добавления последнего появившегося значения в конец очереди, enqueue(значение), и операция снятия первого значения по времени добавления, dequeue(). Иными словами, принцип работы очереди — «первым вошёл, первым вышел» («First in, first out», или FIFO), что в развёрнутом виде можно прочесть как «(элемент, который) первым вошёл (в очередь), первым вышел (из неё, как только к ней обратились)». When a busy nightclub becomes too crowded, a line of people forms outside, as shown in Figure 4-1. As more people try to enter the club, they have to wait at the end of the line. The first person to enter the nightclub from the line is the one who has waited the longest. This behavior represents the essential queue abstract data type, with an enqueue(value) operation that adds value to become the newest value at the end of the queue, and dequeue() removes the oldest value remaining in the queue. Another way to describe this experience is “First in, first out” (FIFO), which is short‐ hand for “First [one] in [line is the] first [one taken] out [of line].”

Иллюстрация 4-1. Ночной клуб. Ожидание в очереди.

Упомянутую в прошлой главе структуру данных — связный список — можно было бы смоделировать на Python довольно просто: каждый элемент списка — это пара (значение, следующий элемент). Весь список — это «матрёшка» таких пар, в каждой из которых, кроме последней, поле .next — это следующая пара, а в последней .next равен None. In the previous chapter, I described the linked list data structure, which I will use again with a Node that stores a value for the queue:

•    1      class Node:
     2        def __init__(self, val):
     3          self.value = val
     4          self.next = None
  

Из таких узлов можно выстроить и очередь. На иллюстрации 4-2 показан результат добавления в клубную очередь «Ивана», «Ирины» и «Игоря» (именно в таком порядке). «Иван» окажется первым, кого снимут из очереди, тогда в ней останется два посетителя, из которых первой окажется «Ирина». Using this structure, the Queue implementation in Listing 4-1 has an enqueue() oper‐ ation to add a value to the end of a linked list. Figure 4-2 shows the result of enqueu‐ ing (in this order) “Joe,” “Jane,” and “Jim” to a nightclub queue. “Joe” will be the first patron dequeued from the line, resulting in a queue with two patrons, where “Jane” remains the first one in line.

Иллюстрация 4-2. Три варианта представления очереди в ночной клуб

Уровень абстракции и модель памяти языка Python позволяет нам относиться к связным спискам и как к «матрёшкам», в которых весь «хвост» списка вложен в его первый элемент, и как к «бахроме», в которых каждый объект представлен изолированно, а в узлах хранятся только ссылки на эти объекты. Действительности, однако, соответствует именно вторая модель, «бахрома»: поэтому, например, фактический размер узла в списке (элемента типа Node) не зависит от размера поля .value. Поскольку обе модели тяжелы для восприятия, впредь мы будем пользоваться их упрощённым гибридом, «цепочкой», в которой явными ссылками представлены только элементы списка, а все остальные данные проще показывать как хранящиеся внутри соответствующих структур. Сами такие структуры мы время от времени будем называть узлами.

В примере 4-1 класс Queue имеет два метода — .enqueue() для добавления элемента в конец связного списка и .dequeue() для снятия элемента из его начала. Оба метода требуют константное время для работы, независимо от количества элементов в очереди. In Queue, the enqueue() and dequeue() operations perform in constant time, inde‐ pendent of the total number of values in the queue.

   1 class Queue:
   2   def __init__(self):                       # 1
   3     self.first = None
   4     self.last = None
   5 
   6   def is_empty(self):
   7     return self.first is None               # 2
   8 
   9   def enqueue(self, val):
  10     if self.first is None:                  # 3
  11       self.first = self.last = Node(val)
  12     else:
  13       self.last.next = Node(val)            # 4
  14       self.last = self.last.next
  15 
  16   def dequeue(self):
  17     if self.is_empty():
  18       raise RuntimeError('Queue is empty')
  19     val = self.first.value                  # 5
  20     self.first = self.first.next            # 6
  21     return val

• Пример 4-1. Реализация очереди при помощи связного списка. Listing 4-1. Linked list implementation of Queue data type

1. Поначалу и first, и last — это None. Initially, first and last are None.

2. Если first — пусто, очередь считается пустой. A Queue is empty if first is None.

3. Если очередь пуста, первый добавляемый элемент и есть последний. If Queue is empty, set first and last to newly created Node.

4. Если очередь непуста, добавляем элемент после текущего last; на этот новый элемент last должен указывать в дальнейшем. If Queue is nonempty, add after last, and adjust last to point to newly created Node.

5. Значение, которое нужно вернуть, хранится в first. first refers to the Node containing value to be returned.

6. Первый элемент исключается из списка, и first теперь указывает на следующий (или равно None, если такого не было). Set first to be the second Node in the list, should it exist.

Поменяем условия. Допустим, ночной клуб стал продавать своим завсегдатаям входные билеты произвольной стоимости, кто сколько заплатит, и проставлять эту стоимость на выданном билете. К примеру, один может купить пятидесятидолларовый билет, а другой — стодолларовый. Люди всё так же встают в очередь, когда клуб переполнен, но первым в него войдёт тот, чей билет дороже всех остальных билетов в очереди. Если самые дорогие билеты оказываются у нескольких человек, очередь на вход предоставляется одному из них. Безбилетники считаются обладателями бесплатного билета. Let’s change the situation: the nightclub decides to allow patrons to spend any amount of money to buy a special pass that records the total amount spent. For example, one patron could buy a $50 pass, while another buys a $100 pass. When the club becomes too crowded, people join the line to wait. However, the first person to enter the nightclub from the line is the one holding a pass representing the highest pay‐ ment of anyone in line. If two or more people in line are tied for having spent the most money, then one of them is chosen to enter the nightclub. Patrons with no pass are treated as having paid $0.

На иллюстрации 4-3 в середине очереди есть завсегдатай с самым дорогим — стодолларовым — билетом. Если сейчас двери откроются, он первым попадёт в клуб. За ним последуют двое с пятидесятидолларовыми билетами (в неустановленном пока порядке), следом — безбилетники; они тоже считаются равноправными (владельцами бесплатных билетов), так что их порядок также не определён. In Figure 4-3, the patron in the middle with a $100 pass is the first one to enter the club, followed by the two $50 patrons (in some order). All other patrons without a pass are considered to be equivalent, and so any one of them could be selected next to enter the club.

Иллюстрация 4-3. Кто больше заплатит, войдёт первым

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

Исправленные таким образом требования определяют абстрактный тип данных — приоритезированную очередь. Правда, в ней уже нельзя реализовать обе операции — enqueue() и dequeue() — за константное время. С одной стороны, если воспользоваться связным списком, то enqueue() останется O(1), а вот dequeue() придётся просматривать все элементы в поисках значения с наивысшим приоритетом, так что в худшем случае сложность ожидается O(N). С другой стороны, если всегда держать элементы в очереди упорядоченными по приоритету, dequeue() окажется O(1), а enqueue() в худшем случае потребует O(N) просмотров в поисках правильного места для вставки в список. This revised behavior defines the priority queue abstract data type; however, enqueue() and dequeue() can no longer be efficiently implemented in constant time. On one hand, if you use a linked list data structure, enqueue() would still be O(1), but dequeue() would potentially have to check all values in the priority queue to locate the one with highest priority, requiring O(N) in the worst case. On the other hand, if you keep all elements in sorted order by priority, dequeue() requires O(1), but now enqueue() requires O(N) in the worst case to find where to insert the new value.

По опыту судя, есть пять сравнительно простых способов организовать из набора объектов типа Entry приоритезированную очередь пар (значение, приоритет): Given our experience to date, here are five possible structures that all use an Entry object to store a (value, priority) entry:

Array

Неупорядоченный массив элементов безо всякой внутренней структуры — может, и так сойдёт. Операция enqueue() занимает константное время, а dequeue() мало того, что занимается поиском по всему массиву, так ещё и вынуждена переставлять его элементы после удаления одного. Вдобавок массив имеет фиксированный размер, так что очередь может ещё и переполниться. В Python такого типа данных нет. An array of unordered entries that has no structure and hopes for the best. enqueue() is a constant time operation, but dequeue() must search the entire array for the highest priority value to remove and return. Because array has a fixed size, this priority queue could become full.

Built-in

Вместо массива в Python можно использовать тип list, и воспользоваться встроенными методами поиска, добавления и удаления элементов. Если элементы в нём не упорядочивать, сложность операций останется той же, что и при использовании массива, разве что мультипликативная константа будет меньше и снимется ограничение по размеру. An unordered list manipulated using Python built-in operations that offers simi‐ lar performance to Array.

OrderA

Массив, элементы которого упорядочены по приоритету. Необходимый для enqueue() поиск места для вставки элемента по такому массиву можно убыстрить с помощью двоичного поиска (описан в примере 2-4), однако мы всё равно вынуждены копировать часть массива вручную, чтобы освободить нужную ячейку посреди других элементов. При этом dequeue() может иметь константную сложность, так как в массиве, упорядоченном по приоритетам, нужный элемент оказывается всегда в конце. Массив имеет фиксированный размер, так что очередь может ещё и переполниться. В Python такого типа данных нет An array containing entries sorted by increasing priority. On enqueue(), use Binary Array Search variation (from Listing 2-4) to locate where the entry should be placed, and manually shift array entries to make room. dequeue() is constant- time because the entries are fully ordered, and the highest priority entry is found at the end of the array. Because the array has a fixed size, this priority queue could become full.

Linked

Связный список, элементы которого всегда расположены по убыванию приоритета: начальный элемент имеет наивысший приоритет, все остальные — меньший либо равный приоритету предыдущего элемента. В этом варианте в операции enqueue() линейную сложность имеет поиск места для вставки элемента, а сама вставка и операция dequeue() константны. A linked list of entries whose first entry has highest priority of all entries in the list; each subsequent entry is smaller than or equal to the previous entry. This implementation enqueues new values into their proper location in the linked list to allow dequeue() to be a constant-time operation.

OrderL

Элементы хранятся в порядке приоритетов в Python-овском динамическом массиве типа list. Для поиска в enqueue() можно снова использовать двоичный поиск, но сама вставка (встроенными в list методами) требует перемещения в среднем половины элементов массива, и оттого линейна. Операция dequeue() ожидаемо константна, потому что элемент с наибольшим приоритетом находится в конце массива. A Python list containing ascending entries by increasing priority. On enqueue(), use Binary Array Search variation to dynamically insert the entry into its proper location. dequeue() is constant time because the highest priority entry is always at the end of the list.

Мы сравнили производительность всех описанных способов, для чего провели испытания, в которых благополучно вызвали 3·N/2 операции enqueue() и 3·N/2 операции dequeue()¹. Для каждого способа измерялось отношение общего времени работы к количеству операций, 3N, в результате получалось среднее время выполнения одной операции. Результаты, показанные в таблице 4-1, говорят следующее. Имитация «массива», в которой все действия реализованы явно, оказалась самым медленным вариантом, а использование встроенных методов list ускорило тест почти вдвое. Упорядоченное хранение элементов в «массиве» снова почти удвоило скорость, использование связных списков ускорило тест ещё примерно на 20%; однако реализация OrderL, посредством упорядоченных списков типа list и их встроенных методов, оказалась вне конкуренции. To compare these implementations, I devised an experiment that safely performs 3N/2 enqueue() operations and 3N/2 dequeue() operations. For each implementa‐ tion, I measure the total execution time and divide by 3N to compute the average operation cost. As shown in Table 4-1, a fixed-size array is the slowest, while built-in Python lists cut the time in half. An array of sorted entries halves the time yet again, and a linked list improves by a further 20%. Even so, the clear winner is OrderL.

• Таблица 4-1. Среднее время операции в наносекундах для объёма данных размера N Table 4-1. Average operation performance (time in ns) on problem instances of size N

Так или иначе, для всех упомянутых способов среднее время либо enqueue(), либо dequeue() прямо пропорционально N. А вот в столбце, помеченном как «Heap», числа ведут себя по-другому: среднее время выполнения пропорционально log(N). Этот столбец содержит результаты эксперимента над структурой данных Heap (т. н. кучей); на иллюстрации 4-4 хорошо видно, насколько она эффективней нашего победителя — упорядоченных списков Python. Хороший эмпирический признак логарифмической сложности — константное приращение времени выполнения при удвоении объёма входных данных. В таблице 4-1 объём входных данных как раз удваивается в каждой следующей строке — и среднее время работы одной операции с кучей увеличивается примерно на 0.8 наносекунд. For these approaches, the average cost of an enqueue() or dequeue() operation increases in direct proportion to N. The column, labeled “Heap” in Table 4-1, how‐ ever, shows the performance results using a Heap data structure; its average cost increases in direct proportion to log(N), as you can see from Figure 4-4, and it signif‐ icantly outperforms the implementation using ordered Python lists. You know you have logarithmic performance when you only see a constant time increase in runtime performance when the problem size doubles. In Table 4-1, with each doubling, the performance time increases by about 0.8 nanoseconds.

Простейший вариант кучи — т. н. «двоичную кучу» — изобрёл для своего алгоритма сортировки валлийско-канадский математик Дж. В. Дж. Вильямс (в русскоязычной литературе этот алгоритм обычно называют пирамидальной сортировкой). С помощью кучи можно добиться логарифмической сложности операций над приоритезированной очередью. В этой главе мы не станем больше обращать внимания на тип поставленного в очередь объекта: это могут быть строки, числа или вообще картинки, значения не имеет. Нам будет важен только числовой приоритет, который хранится в паре с объектом. Так что во всех иллюстрациях, где для простоты показан только приоритет, подразумевается и объект, который с этим приоритетом поставлен в очередь. В куче с порядком убывания у того из двух объектов приоритет выше, у кого он больше. The heap data structure, invented in 1964, provides O(log N) performance for the operations of a priority queue. For the rest of this chapter, I am not concerned with the values that are enqueued in an entry—they could be strings or numeric values, or even image data; who cares? I am only concerned with the numeric priority for each entry. In each of the remaining figures in this chapter, only the priorities are shown for the entries that were enqueued. Given two entries in a max heap, the one whose priority is larger in value has higher priority.

В нашем варианте куча будет иметь заранее заданный наибольший размер, M, и сможет хранить N < M элементов. Теперь давайте изучим её структуру, посмотрим, как она растёт (в рамках наибольшего размера) и убывает в процессе работы с ней, а также научимся хранить Nэлементов кучи в обычном массиве. A heap has a maximum size, M—known in advance—that can store N < M entries. I now explain the structure of a heap, show how it can grow and shrink over time within its maximum size, and show how an ordinary array stores its N entries.

Иллюстрация 4-4. Логарифмическая сложность операций над кучей куда эффективнее линейной сложности других подходов

метки не переводятся, в названии второго графика именно OrderL, а не Order, в иллюстрации ошибка -- FrBrGeorge 2022-08-25 19:01:26

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

Max Binary Heaps

Не вполне понятно зачем, но предположим, что наши данные отсортированы только частично. Например, на иллюстрации 4-5 изображена двоичная куча с частичным порядком — убыванием приоритетов²; у каждого элемента показан только приоритет. На уровне 0 находится единственный элемент, и приоритет его будет наивысшим среди всех элементов кучи. Если два элемента x → y связывает стрелка, то приоритет x больше либо равен приоритету y. It may seem like a strange idea, but what if I only “partially sort” the entries? Figure 4-5 depicts a max heap containing 17 entries; for each entry, only its priority is shown. As you can see, level 0 contains a single entry that has the highest priority among all entries in the max heap. When there is an arrow, x → y, you can see that the priority for entry x ≥ the priority for entry y.

Иллюстрация 4-5. Пример двоичной кучи с частичным убыванием

Частично упорядоченная по убыванию куча — это не сортированный список, в ней, например, нельзя сразу найти элемент с наименьшим приоритетом (если что, он на уровне 3). Зато у неё есть иные полезные свойства. На первом уровне кучи находятся два элемента, приоритет одного из которых — непременно наивысший для всех уровней, кроме приоритета элемента на уровне 0 (а не то равен и ему). Любой уровень k — кроме последнего — содержит 2^k элементов; иными словами, он полон. Неполным может быть только самый низкий уровень (в нашем примере там два из возможных шестнадцати элементов); заполняются уровни слева направо. Приоритет не уникален: в куче из примера приоритеты 8 и 14 встречаются более одного раза. These entries are not fully ordered like they would be in a sorted list, so you have to search awhile to find the entry with lowest priority (hint: it’s on level 3). But the resulting structure has some nice properties. There are two entries in level 1, one of which must be the second-highest priority (or tied with the highest one, right?). Each level k—except for the last one—is full and contains 2k entries. Only the bottommost level is partially filled (i.e., it has 2 entries out of a possible 16), and it is filled from left to right. You can also see that the same priority may exist in the heap—the priorities 8 and 14 appear multiple times.

В двоичной куче из каждого узла может исходить не более двух стрелок. Возьмём узел на уровне 0, приоритет которого равен 15. Он связан стрелками с двумя узлами на уровне 1: узел с приоритетом 13 — это его левый потомок, а узел с приоритетом 14 — правый потомок. Для узлов на первом уровне узел на нулевом уровне (с приоритетом 15) является, соответственно родительским. Each entry has no more than 2 arrows coming out of it, which makes this a max binary heap. Take the entry on level 0 whose priority is 15: the first entry on level 1 with priority 13 is its left child; the second entry on level 1 with priority 14 is its right child. The entry with priority 15 is the parent of the two children entries on level 1.

Опишем структурные свойства двоичной кучи: The following summarizes the properties of a max binary heap:

Частичный порядок

Приоритет узла не меньше приоритетов его левого и правого потомков (если они есть). Приоритет любого узла (кроме того, что на вершине кучи) не больше приоритета его родительского узла.

Heap-ordered property The priority of an entry is greater than or equal to the priority of its left child and its right child (should either one exist). The priority for each entry (other than the topmost one) is smaller than or equal to the priority of its parent entry.

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

Каждый уровень k кучи, кроме последнего, содержит ровно 2^k узлов, последний может содержать меньше, заполняется он слева направо, и до тех пор, пока он неполон, уровень k + 1 не появляется. Heap-shape property Each level k must be filled with 2k entries (from left to right) before any entry appears on level k + 1.

Если в двоичной куче только один элемент, в ней только один уровень — нулевой; 2⁰=1, пирамидальность соблюдена. Сколько уровней понадобится, чтобы хранить N > 0 элементов? Нужна математическая формула, которая по заданному N позволит вычислить необходимое количество уровней в куче. С помощью иллюстрации 4-6 можно попробовать догадаться, что это за формула. Расположим в виде пирамиды 16 узлов и пронумеруем их согласно принципу пирамидальности: на вершине — e₁, затем последовательно по каждому уровню с увеличением индекса на 1. Получится четыре полных уровня и единственный узел на пятом. When a binary heap only contains a single entry, there is just a single level, 0, because 20 = 1. How many levels are needed for a binary heap to store N > 0 entries? Mathe‐ matically, I need to define a formula, L(N), that returns the number of necessary lev‐ els for N entries. Figure 4-6 contains a visualization to help determine L(N). It contains 16 entries, each labeled using a subscript that starts at e1 at the top and increases from left to right until there are no more entries on that level, before start‐ ing again at the leftmost entry on the next level.

Иллюстрация 4-6. Сколько уровней в куче из N узлов?

Пока в куче только 7 узлов e₁ - e₇, они помещаются на трёх уровнях. Начиная с восьми узлов уже нужно четыре уровня. Если идти по стрелкам сверху налево, нам встретятся узлы e₁, e₂, e₄, e₈ и e₁₆ — очевидно, степень двойки влияет не только на размер уровня, но и на размер всей кучи. В формуле оценки количества слоёв логично ожидать двоичный логарифм от N — если быть более точным, количество слоёв L для хранения N элементов в двоичной куче равно L(N) = 1 + ⌊log₂N⌋ (неполные квадратные скобки здесь означают округление до целого числа вниз, аналогичная функция Python — math.floor()). If there were only 7 entries in a heap, there would be 3 levels containing entries e1 through e7. Four levels would be needed for 8 entries. If you follow the left arrows from the top, you can see that the subscripts follow a specific pattern: e1, e2, e4, e8, and e16, suggesting that powers of 2 will play a role. It turns out that L(N) = 1 + floor(log(N)).

В каждом следующем уровне двоичной кучи помещается больше узлов, чем во всех предыдущих вместе взятых! В двоичной куче из L полных уровней содержится 2L-1 элемент. В самом деле, в куче из одного уровня 21-1=1 узел, в куче из двух уровней — 22-1=3 узла; предположим, что в куче из L-1 уровней 2L-1-1 узел — тогда в куче из L уровней с добавлением ещё 2L-1 элемента из очередного слоя окажется 2L-1-1 + 2L-1 = 2(2L-1)-1 = 2L-1 узел, и формула индуктивно доказана. Как следствие, если к куче добавить всего один слой, она вместо N элементов будет способна хранить 2N+1 элемент.

Что же касается двоичных логарифмов, то мы помним правило: при удвоении N логарифм увеличивается на 1; или в виде формулы: log₂ 2N = 1 + log₂ N. You should recall with logarithms that when you double N, the value of log(N) increases by 1. This is represented mathematically as follows: log(2N) = 1 + log(N).

Какие из вариантов на иллюстрации 4-7 соответствую двоичной куче с порядком убывания? Which of the four options in Figure 4-7 are valid max binary heaps?

Иллюстрация 4-7. Что из этого можно назвать двоичной кучей с убыванием?

Сначала давайте проверим свойство пирамидальности. Варианты №1 и №2 подходят, потому что в них заполнены все уровни. Вариант №3 тоже подходит, потому что в нём неполон только последний уровень, и заполнен он правильно: содержит три узла из допустимых четырёх, и это три самых левых узла. А вот в варианте №4 пирамидальность не соблюдается: последний уровень содержит три узла, при этом самый левый узел пуст. First review the heap-shape property for each of these options. Options #1 and #2 are acceptable, since each level is completely full. Option #3 is acceptable because only its last level is partial and it contains three (out of possible four) entries from left to right. Option #4 violates the heap-shape property because its last level contains three entries, but the leftmost possible entry is missing.

Теперь проверим частичный порядок. В случае убывания приоритет каждого родителя должен быть не меньше приоритетов его потомков. Это верно для варианта №1,в чём можно убедиться, сравнив все начала и концы стрелок. Вариант №3 не годится, потому что у узла с приоритетом 8 есть потомок с приоритетом 9. Вариант №2 не годится, потому что уже на уровне 0 приоритет узла равен 4, а у обоих его потомков он выше. Now consider the heap-ordered property for max binary heaps, which ensures that each parent’s priority is greater than or equal to the priorities of its children. Option #1 is valid, as you can confirm by checking each possible arrow. Option #3 is invalid because the entry with priority 8 has a right child whose priority of 9 is greater. Option #2 is invalid because the entry with priority 4 on level 0 has smaller priority than both of its children entries.

В действительности вариант №2 — это пример двоичной кучи с убыванием, в которой приоритет родительского узла не превосходит приоритеты потомков. Этот вариант двоичной кучи мы рассмотрим в главе 7.

Операции добавления элемента в кучу enqueue() и снятия с кучи элемента с наивысшим приоритетом dequeue() должны сохранять оба её свойства. Если удастся их реализовать так, чтобы производительность обеих операций оценивалась как O(log N), мы получим значительное улучшение быстродействия по сравнению с медленными моделями из таблицы 4-1, в которых либо enqueue(), либо dequeue() в наихудшем случае показывали быстродействие O(N). I need to make sure that both heap properties hold after enqueue() or dequeue() (which removes the value with highest priority in the max heap). This is important because then I can demonstrate that both of these operations will perform in O(log N), a significant improvement to the approaches documented earlier in Table 4-1, which were limited since either enqueue() or dequeue() had worst case behavior of O(N).

Добавление пары в кучу

Inserting a (value, priority)

Если задаться целью добавить пару (значение, приоритет) в двоичную кучу, соблюдая только свойство пирамидальности, то в каком конкретно месте функции enqueue() придётся заводить узел? Ответ всегда одинаков: After enqueue(value, priority) is invoked on a max binary heap, where should the new entry be placed? Here’s a strategy that always works:

• Если последний уровень неполон, заполняется самый левый пустой узел этого уровня. • Place the new entry into the first available empty location on the last level.

• Если последний уровень полон, заводится новый уровень, и заполняется самый левый его узел • If that level is full, then extend the heap to add a new level, and place the new entry in the leftmost location in the new level.

На иллюстрации 4-8 показан свежедобавленный в кучу узел с приоритетом 12: он занял третье место на уровне 4. Свойство пирамидальности соблюдено — все уровни, кроме последнего, полны, а последний заполнен слева. Однако во многих случаях частичный порядок от такого добавления нарушается. In Figure 4-8, a new entry with priority 12 is inserted in the third location on level 4. You can confirm that the heap-shape property is valid (because the entries on the par‐ tial level 4 start from the left with no gaps). It might be the case, however, that the heap-ordered property has now been violated.

К счастью это дело поправимое, причём достаточно переставить местами только узлы «по дороге» от вершины кучи к только что добавленному элементу. На иллюстрации 4-10 показана куча с восстановленным частичным порядком; можно заметить, что для этого пришлось переставить в порядке невозрастания узлы отмеченной серым пути от вершины до крайнего левого узла на последнем уровне. The good news is that I only need to possibly rearrange entries that lie in the path from the newly placed entry all the way back to the topmost entry on level 0. Figure 4-10 shows the end result after restoring the heap-ordered property; as you can see, the entries in the shaded path have been reordered appropriately, in decreas‐ ing (or equal) order from the top downward.

Иллюстрация 4-8. Добавление элемента. Начальный шаг — заполняется первый свободный узел

Путь до заданного узла двоичной кучи — это последовательность узлов и стрелок вправо или влево между ними от единственного узла на уровне 0 до заданного.

Теперь надо позаботиться о восстановлении частичного порядка. Добавленный элемент начинает «всплывать» вдоль пути — если порядок нарушен, он и его родитель меняются местами. В примере на иллюстрации 4-8 свежедобавленный узел с приоритетом 12 нарушает порядок, потому что его приоритет выше, чем 2, приоритет родителя. Два узла меняются местами; результат показан на иллюстрации 4-9. Между тем всплытие продолжается. To remake the max heap to satisfy the heap-ordered property, the newly added entry “swims up” along this path to its proper location, using pairwise swaps. Based on this example, Figure 4-8 shows that the newly added entry with priority 12 invalidates the heap-ordered priority since its priority is larger than its parent whose priority is 2. Swap these two entries to produce the max heap in Figure 4-9 and continue upward.

Иллюстрация 4-9. Добавление элемента. Второй шаг — если нужно, узел всплывает на уровень выше

После первого «всплытия» структура с вершиной в узле 12 будет полноценной двоичной кучей из двух элементов. Но 12 всё ещё нарушает частичный порядок, потому что приоритет родителя этого узла — 9, а это меньше 12. Надо всплывать ещё выше, как показано на иллюстрации 4-10. You can confirm that from 12 downward, the structure is a valid max binary heap with two entries. However the entry with 12 still invalidates the heap-ordered prop‐ erty since its parent entry has a priority of 9, which is smaller, so swap with its parent, as shown in Figure 4-10.

После очередного всплытия структура с вершиной в узле 12 будет полноценной двоичной кучей. Меняя местами 9 и 12 (по правой стрелке), мы можем не проверить, соблюдаются ли свойства кучи в структуре с вершиной 8 (по левой стрелке). Поскольку раньше все элементы этой структуры были не больше 9, они и подавно будут меньше 12. После третьего шага приоритет родительского узла, 13, оказывается больше 12 — частичный порядок восстановлен. From highlighted entry 12 downward in Figure 4-10, the structure is a valid max binary heap. When you swapped the 9 and 12 entries, you didn’t have to worry about the structure from 8 and below since all of those values are known to be smaller than or equal to 8, which means they will all be smaller than or equal to 12. Since 12 is smaller than its parent entry with priority of 13, the heap-ordered property is satisfied.

Иллюстрация 4-10. Добавление элемента. Третий шаг — если нужно, узел всплывает на уровень выше

Попробуем вручную отработать вызов enqueue(значение, 16) на куче из иллюстрации 4-10. Сначала узел добавляется в четвёртую ячейку уровня 4 в качестве правого потомка узла с приоритетом 9. Затем узел всплывает всё выше и выше вплоть до уровня 0. В результате должна получается двоичная куча как на иллюстрации 4-11. Try on your own to enqueue(value, 16) into the heap depicted in Figure 4-10, which initially places the new entry in the fourth location on level 4, as the right child of the entry with priority 9. This new entry will swim up all the way to level 0, result‐ ing in the max binary heap shown in Figure 4-11.

Иллюстрация 4-11. Элемент с приоритетом 16 после добавления всплывает на вершину кучи

Наихудший случай для операции добавления — когда добавляется элемент с приоритетом, превышающим все имеющиеся приоритеты в куче. Длина пути при добавлении равна количеству уровней в куче, 1+ ⌊log₂N⌋, а это значит, что наибольшее возможное количество операций обмена будет на одну меньше — ⌊log₂N⌋. Теперь уже можно уверенно оценивать и процедуру восстановления пирамидальности, и всю операцию enqueue() как O(log N). Большое дело — но это только половина решения всей задачи: теперь надо убедиться в том, что операцию снятия с кучи элемента с наивысшим приоритетом можно реализовать так же эффективно. The worst case is when you enqueue a new entry whose priority is higher than any entry in the max binary heap. The number of entries in the path is 1 + floor(log(N)), which means the most number of swaps is one smaller, or floor(log(N)). Now I can state clearly that the time to remake the max binary heap after an enqueue() opera‐ tion is O(log N). This great result only addresses half of the problem, since I must also ensure that I can efficiently remove the entry with highest priority in the max binary heap.

Снятие элемента с кучи

Removing the Value with Highest Priority

Искать в куче элемент с наивысшим приоритетом не надо — он всегда находится на её вершине, в единственном узле уровня 0. Но если просто удалить его, нарушится свойство пирамидальности — уровень 0, не последний в структуре, будет содержать пустой узел. К счастью, для dequeue() тоже есть способ эффективной перестройки кучи, как мы это увидим в последующих иллюстрациях. Если сохранять только свойство пирамидальности, удаление выглядит довольно просто: Finding the entry with highest priority in a max binary heap is simple—it will always be the single entry on level 0 at the top. But you just can’t remove that entry, since then the heap-shape property would be violated by having a gap at level 0. Fortu‐ nately, there is a dequeue() strategy that can remove the topmost entry and efficiently remake the max binary heap, as I show in the next sequence of figures:

1. Запомним самый последний (самый правый в последнем уровне) элемент кучи и удалим его. Получившаяся структура сохранит все свойства двоичной кучи. 1. Remove the rightmost entry on the bottommost level and remember it. The resulting structure will satisfy both the heap-ordered and heap-shape properties.

2. Запомним значение элемента с наивысшим приоритетом (с уровня 0) — это значение должна вернуть функция dequeue(). Save the value for the highest priority entry on level 0 so it can be returned.

3. Заменим верхний элемент кучи с уровня 0 на элемент, который мы удалили из нижнего уровня и запомнили на первом шаге. Это сохранит пирамидальность, но, скорее всего, нарушит частичный порядок. Replace the entry on level 0 with the entry you removed from the bottommost level of the heap. This might break the heap-ordered property.

На примере иллюстрации 4-12: сначала мы запоминаем и удаляем из кучи элемент 9; куча при этом остаётся кучей. Затем запоминаем возвращаемое значение, приоритет которого наивысший, 16; на иллюстрации это действие не показано. To achieve this goal, first remove and remember entry 9, as shown in Figure 4-12; the resulting structure remains a heap. Next, record the value associated with the highest priority on level 0 so it can be returned (not shown here).

Иллюстрация 4-12. Снятие элемента. Удаляем последний узел

На втором шаге мы подменяем узел на уровне 0 только что удалённым нами узлом. Как это понятно из иллюстрации 4-13, частичный порядок в куче нарушится. Мы видим, что приоритет единственного узла на уровне 0 меньше и приоритета его левого потомка, 15, и приоритета его правого потомка, 14. Чтобы порядок восстановился, узел должен начать «тонуть», погружаясь вглубь кучи вплоть до отведёного ему места. Finally, replace the single entry on level 0 with the entry that was removed, resulting in the broken max heap shown in Figure 4-13. As you can see, the priority of the sin‐ gle entry on level 0 is not greater than its left child (with priority 15) and right child (with priority 14). To remake the max heap, you need to “sink down” this entry to a location further down inside the heap to re-establish the heap-ordered property.

Иллюстрация 4-13. Снятие элемента. Подставляем последний элемент вместо верхнего, порядок при этом нарушается

Поскольку наш узел нарушает порядок (сейчас на уровне 0 оказалась пара с приоритетом 9), надо решить, какой из узлов кучи необходимо поставить на его место. Очевидно, это должен быть узел с наивысшим приоритетом среди тех, что доступны по стрелкам на уровнях ниже нашего. Выбор придётся делать среди всего двух узлов — правого и левого потомков (приоритеты остальных заведомо не выше). Если правого потомка нет, то остаётся только левый. В нашем примере мы выбираем левого потомка, чей приоритет равен 15, и это больше, чем 14, приоритет правого потомка. Меняем местами наш узел и выбранного потомка с наивысшим приолритетом, получаем состояние, показанное на иллюстрации 4-14. Starting from the entry that is invalid (i.e., the level 0 entry with priority 9), deter‐ mine which of its children (i.e., left or right) has the higher priority—if only the left child exists, then use that one. In this running example, the left child with priority 15 has higher priority than the right child with priority 14, and Figure 4-14 shows the result of swapping the topmost entry with the higher selected child entry.

Иллюстрация 4-14. Снятие элемента. Меняем местами верхний узел и его левого потомка, приоритет которого выше

Можно заметить, что вся структура, начинающаяся с узла с приоритетом 14 на уровне 1, — это полноценная двоичная куча; мы её не трогали, и менять там ничего не надо. А вот в структуре под узлом с приоритетом 9, который оказался на уровне 1 после обмена, порядок нарушен — оба его потомка имеют более высокий приоритет. Значит, наш узел будет продолжать «тонуть», меняясь с левым потомком (как это показано на иллюстрации 4-15), потому что приоритет левого потомка 13 выше, чем приоритет правого. As you can see, the entire substructure based on the entry with priority 14 on level 1 is a valid max binary heap, and so it doesn’t need to change. However, the newly swapped entry (with priority 9) violates the heap-ordered property (it is smaller than the priority of both of its children), so this entry must continue to “sink down” to the left, as shown in Figure 4-15, since the entry with priority 13 is the larger of its two children entries.

Иллюстрация 4-15. Снятие элемента. Узел продолжает тонуть

Осталось немного! На иллюстрации 4-15 видно, что в новом положении у нашего узла с приоритетом 9 есть правый потомок, чей приоритет оставшихся — 12, так что мы меняем эти два узла, после чего частичный порядок в нашей куче восстанавливается, как это видно на иллюстрации 4-16. Almost there! Figure 4-15 shows that the entry with priority 9 has a right child whose priority of 12 is higher, so we swap these entries, which finally restores the heap- ordered property for this heap, as shown in Figure 4-16.

Иллюстрация 4-16. Снятие элемента. Куча после того, как узел погрузился на нужный уровень

В отличие от операции добавления элемента в приоритезированную очередь, в операции снятия нельзя спроста предсказать путь до будущего положения «тонущего» узла. Однако узел «тонет» с уровня на уровень, так что наибольшее возможное количество «погружений» не больше, чем переходов между уровнями в двоичной куче. Это число на единицу меньше, чем самих уровней, иными словами, ⌊log₂N⌋. There is no simple path of adjusted entries, as we saw when enqueuing a new entry to the priority queue, but it is still possible to determine the maximum number of times the “sink down” step was repeated, namely, one value smaller than the number of lev‐ els in the max binary heap, or floor(log(N)).

Ещё можно посчитать, сколько раз сравниваются приоритеты двух узлов за одну операцию снятия. Каждое «погружение» требует максимум двух сравнений: выбора наибольшего приоритета среди двух потомков и сравнения этого приоритета с приоритетом родителя. Таким образом можно ожидать, что сравнений будет не больше 2·⌊log₂N⌋. You can also count the number of times the priorities of two entries were compared with each other. For each “sink down” step, there are at most two comparisons—one comparison to find the larger of the two sibling entries, and then one comparison to determine if the parent is bigger than the larger of these two siblings. In total, this means the number of comparisons is no greater than 2 × floor(log(N)).

Мы сделали очень важное предположение: и добавление элемента в двоичную кучу, и снятие элемента с её вершины занимают время, в наихудшем случае прямо пропорциональное log N. Пора переходить от теории к практике, а заодно посмотреть, как можно хранить двоичную кучу в обычном массиве. It is incredibly important that the max binary heap can both add an entry and remove the entry with highest priority in time that is directly proportional to log(N) in the worst case. Now it is time to put this theory into practice by showing how to imple‐ ment a binary heap using an ordinary array.

Можно заметить, что пирамидальность кучи позволяет перечислить все элементы, если начать перебор с уровня 0 вниз, а по уровню двигаться слева направо. Этой особенностью можно воспользоваться: оказывается, элементы двоичной кучи вполне удобно хранить в обычном массиве подряд по уровням. Have you noticed that the heap-shape property ensures that you can read all entries in sequence from left to right, from level 0 down through each subsequent level? I can take advantage of this insight by storing a binary heap in an ordinary array.

Хранение двоичной кучи в массиве

Representing a Binary Heap in an Array

На иллюстрации 4-17 показан один из способов записать двоичную кучу размером N = 18 в массив фиксированного размера M > N. В такой куче будет пять уровней, каждый из которых которые будет соответствовать определённому диапазону индексов массива, содержащего хранимые пары. Пунктирные квадраты в правой стороне иллюстрации отмечают индекс, по которому хранится соответствующий узел двоичной кучи. Как обычно, при изображении кучи мы показываем только приоритеты, а значения опускаем. Figure 4-17 shows how to store a max binary heap of N = 18 entries within a fixed array of size M > N. This max binary heap of five levels can be stored in an ordinary array by mapping each location in the binary heap to a unique index location. Each dashed box contains an integer that corresponds to the index position in the array that stores the entry from the binary heap. Once again, when depicting a binary heap, I only show the priorities of the entries.

Иллюстрация 4-17. Запись двоичной кучи в массив

Итак, каждой хранимой паре сопоставляется индекс в массиве storage[]. Чтобы не упражняться лишний раз с вычитанием и добавлением единицы к этому индексу, оставим storage[0] пустым, и ничего там хранить не будем. Элемент с наивысшим приоритетом, 15, хранится в storage[1]. Согласно иллюстрации, его левый потомок, с приоритетом 13, хранится в storage[2]. В общем случае, если у элемента storage[k] есть левый потомок, он будет храниться в storage[2*k] (в этом легко убедиться, проследив стрелочки между пунктирными квадратами на иллюстрации 4-17). Если у элемента storage[k] есть правый потомок, он будет храниться, соответственно, в storage[2*k+1]. Each entry has a corresponding location in the storage[] array. To simplify all com‐ putations, location storage[0] is unused and never stores an entry. The topmost entry with priority 15 is placed in storage[1]. You can see that its left child, with pri‐ ority 13, is placed in storage[2]. If the entry in storage[k] has a left child, that entry is storage[2*k]; Figure 4-17 confirms this observation (just inspect the dashed boxes). Similarly, if the entry in storage[k] has a right child, that entry is in stor age[2*k+1].

Если k > 1, родительский узел для storage[k] всегда находится в storage[k//2] (в Python k//2 — это целая часть от деления k на 2). Если располагать вершину кучи в storage[1], то чтобы вычислить индекс родителя любого узла, надо просто целочисленно поделить на 2 индекс узла-потомка. В примере родительский узел для storage[5] (с приоритетом 11) окажется в storage[2], потому что 5//2 = 2.

For k > 1, the parent of the entry in storage[k] can be found in storage[k//2], where k//2 is the integer value resulting by truncating the result of k divided by 2. By placing the topmost entry of the heap in storage[1], you just perform integer divi‐ sion by two to compute the parent location of an entry. The parent of the entry in storage[5] (with a priority of 11) is found in storage[2] because 5//2 = 2.

Если в куче содержится N элементов, storage[k] для любого 0 < k ⩽ N содержит узел из двоичной кучи. Как следствие, если 2·k > N, то у k-го узла нет потомков; например, у узла storage[10] (с приоритетом 1) потомков нет, потому что 2 · 10 = 20 > 18 = N. А у узла storage[9] (с приоритетом, так случайно вышло, тоже 9) нет только правого потомка, потому что 2 · 9 = 18 = N, а вот 2 · 9 + 1 = 19 > N. The entry in storage[k] is a valid entry when 0 < k ≤ N, where N represents the number of entries in the max binary heap. This means that the entry at storage[k] has no children if 2 × k > N; for example, the entry at storage[10] (which has prior‐ ity of 1) has no left child, because 2 × 10 = 20 > 18. You also know that the entry at storage[9] (which coincidentally has a priority of 9) has no right child, because 2 × 9 + 1 = 19 > 18.

Как погружаться и всплывать

Implementation of Swim and Sink

Начнём программировать нашу двоичную кучу с частичным убыванием с задания класса для пары (значение, приоритет): To store a max binary heap, start with an Entry that has a value with its associated priority:

   1       class Entry:
   2         def __init__(self, v, p):
   3           self.value = v
   4           self.priority = p

В примере 4-2 для хранения узлов кучи применяется массив storage. При создании экземпляра класса PQ размер storage на единицу превосходит максимальный размер кучи — параметр size конструктора — потому что, напомним, мы храним элементы кучи в массиве начиная с storage[1]. Listing 4-2 stores a max binary heap in an array, storage. When instantiated, the length of storage is one greater than the size parameter, to conform to the computa‐ tions described earlier where the first entry is stored in storage[1].

Чтобы можно было лучше изучить работу нашего класса, мы написали два вспомогательных метода. Метод .less(i, j) проверяет, что приоритет i-го узла меньше приоритета j-го, и возвращает True или False. Когда нам понадобится оценить, сколько раз мы сравниваем приоритеты двух узлов, достаточно будет просто посчитать количество вызовов .less(). Метод swap(i, j) меняет местами i-й и j-й узлы в массиве, он нам понадобится для подсчёта количества обменов при перестройке кучи, когда узел «всплывает» или «тонет». There are two helper methods that simplify the presentation of the code. You have seen how many times I checked whether one entry has a smaller priority than another entry. The less(i,j) function returns True when the priority of the entry in storage[i] is smaller than the priority of the entry in storage[j]. When swimming up or sinking down, I need to swap two entries. The swap(i,j) function swaps the locations of the entries in storage[i] and storage[j].

   1 class PQ:
   2   def less(self, i, j):                                 # 1
   3     return self.storage[i].priority < self.storage[j].priority
   4 
   5   def swap(self, i, j):                                 # 2
   6     self.storage[i], self.storage[j] = self.storage[j], self.storage[i]
   7 
   8   def __init__(self, size):                             # 3
   9     self.size = size
  10     self.storage = [None] * (size+1)
  11     self.N = 0
  12 
  13   def enqueue(self, v, p):                              # 4
  14     if self.N == self.size:
  15       raise RuntimeError('Priority Queue is Full!')
  16     self.N += 1
  17     self.storage[self.N] = Entry(v, p)
  18     self.swim(self.N)
  19 
  20   def swim(self, child):                                # 5
  21     while child > 1 and self.less(child//2, child):     # 6
  22       self.swap(child, child//2)                        # 7
  23       child = child // 2                                # 8

• Пример 4-2. Реализация кучи с методами .enqueue() и .swim() Listing 4-2. Heap implementation showing enqueue() and swim() methods

1. Метод .less(i, j) проверяет, что storage[i] имеет меньший приоритет, чем storage[j]. less() determines if storage[i] has lower priority than storage[j].

2. Метод swap(i, j) меняет местами i-й и j-й узел. swap() switches the locations of entries i and j.

3. Узлы хранятся в ячейках от storage[1] до storage[size], а storage[0] не испльзуется. storage[1] through storage[size] will store the entries; storage[0] is unused.

4. Чтобы добавить элемент в кучу, надо расположить его в первой свободной ячейке массива, а затем позволить ему «всплыть». To enqueue a (v, p) entry, place it in the next empty location and swim it upward.

5. Метод .swim() перестраивает массив storage, возвращая куче пирамидальность. swim() remakes the storage array to conform to the heap-ordered property.

6. Родительский узел для storage[child] находится в storage[child//2] (child//2 — это целочисленное деление child на 2). The parent of the entry in storage[child] is found in storage[child//2], where child//2 is the integer result of dividing child by 2.

7. Меняем местами storage[child] и его родителя storage[child//2]. Swap entries at storage[child] and its parent storage[child//2].

8. Если надо, узел продолжит всплывать, и теперь child равен индексу родителя. Continue upward by setting child to its parent location as needed.

Метод .swim() оказался весьма лаконичен! Индекс свежедобавленного узла — child, индекс его родителя, если таковой имеется, — child//2. Если приоритет родителя меньше приоритета child, они меняются местами, и всплытие продолжается. The swim() method is truly brief! The entry identified by child is the newly enqueued entry, while child//2 is its parent entry, should it exist. If the parent entry has lower priority than the child, they are swapped, and the process continues upward.

На иллюстрации 4-18 представлено, как меняется массив storage после вызова enqueue(значение, 12) из состояния, которое было показано на иллюстрации 4-8. В каждом следующем ряду ячейки storage меняется, как это ранее отображалось на очередной иллюстрации. В последнем ряду — состояние массива, соответствующее двоичной куче с пирамидальностью и частичным порядком. Figure 4-18 shows the changes to storage initiated by enqueue(value, 12) in Figure 4-8. Each subsequent row corresponds to an earlier identified figure and shows the entries that change in storage. The final row represents a max binary heap that conforms to the heap-ordered and heap-shape properties.

Иллюстрация 4-18. Как меняется storage после вызова enqueue() на иллюстрации 4-08

Путь от вершины кучи до только что добавленного элемента с приоритетом 12 состоит из пяти узлов — они помечены серым на иллюстрации 4-18. После двух итераций цикла whlle в методе .swim(), в которых узел «всплывает», меняясь местами со своим родителем, он попадает в ячейку storage[4], и свойство пирамидальности кучи восстанавливается. Количество обменов не может превышать log₂N, где N — общее число ячеек в двоичной куче. The path from the topmost entry to the newly inserted entry with priority 12 consists of five entries, as shaded in Figure 4-18. After two times through the while loop in swim(), the entry with priority 12 is swapped with its parent, eventually swimming up to storage[4], where it satisfies the heap-ordered property. The number of swaps will never be more than log(N), where N is the number of entries in the binary heap.

В примере 4-3 мы реализовали метод .sink(), который который используется для восстановления свойств двойчной кучи при снятии элемента с её вершины при помощи .dequeue(). The implementation in Listing 4-3 contains the sink() method to reestablish the structure of the max binary heap after dequeue() is invoked.

   1     def dequeue(self):
   2       if self.N == 0:
   3         raise RuntimeError ('PriorityQueue is empty!')
   4       max_entry = self.storage[1]                               # 1
   5       self.storage[1] = self.storage[self.N]                    # 2
   6       self.storage[self.N] = None
   7       self.N -= 1                                               # 3
   8       self.sink(1)
   9       return max_entry.value                                    # 4
  10 
  11     def sink(self, parent):
  12       while 2*parent <= self.N:                                 # 5
  13         child = 2*parent
  14         if child < self.N and self.less(child, child+1):        # 6
  15           child += 1
  16         if not self.less(parent, child):                        # 7
  17           break
  18         self.swap(child, parent)                                # 8
  19         parent = child

• Пример 4-3. После добавления методов .dequeue() и .sink() мы получаем полноценно работающую кучу Listing 4-3. Heap implementation completed with dequeue() and sink() methods

1. Запомним ячейку на вершине кучи. Save entry of highest priority on level 0.

2. Переставим на вершину последний (самый правый в самом нижнем уровне) элемент, а его место освободим. Replace entry in storage[1] with entry from bottommost level of heap and clear from storage.

3. Уменьшим количество узлов и запустим sink() для storage[1]. Reduce number of entries before invoking sink on storage[1].

4. Вернём значение элемента, снятого с вершины кучи. Return the value associated with entry of highest priority.

5. Проверка продолжается, пока у узла есть хотя бы левый потомок. Continue checking as long as parent has a child.

6. Если правый потомок существует и приоритет левого потомка меньше, нам нужен правый потомок. Select right child if it exists and is larger than left child.

7. Если приоритет родителя не меньше максимального приоритета потомков, пирамидальность восстановлена. If parent is not smaller than child, heap-ordered property is met.

8. Если нет, поменяем местами родителя и потомка и продолжим «топить» наш узел уже с нового места. Swap if needed, and continue sinking down, using child as new parent.

На иллюстрации 4-19 изображено, как меняется storage в процессе работы dequeue() — начиная с двоичной кучи с иллюстрации 4-11. Первая строка на иллюстрации 4-19 — это массив из 19 элементов. Во второй строке самый последний элемент с приоритетом 9 перемещается в самое начало (что соотвествует вершине двоичной кучи и нарушает пирамидальность); коме того, теперь в куче 18 узлов, так как последний мы удалили. Figure 4-19 shows the changes to storage initiated by dequeue() based on the initial max binary heap shown in Figure 4-11. The first row of Figure 4-19 shows the array with 19 entries. In the second row, the final entry in the heap with priority 9 is swapped to become the topmost entry in the max binary heap, which breaks the heap-ordered property; also, the heap now only contains 18 entries, since one was deleted.

Иллюстрация 4-19. Изменения массива storage в процессе снятия элемента с вершины кучи, приведённой на иллюстрации 4-11

После трёх последовательных итераций цикла while в методе .sink() узел с приоритетом 9 «погружается» на позицию, в которой достигается пирамидальность кучи, серым всюду обозначены потомки этого узла (ном лежат в массиве правее). Всякий раз, когда выясняется, что приоритет родителя меньше приоритета потомка, родитель и потомок и более высоким приоритетом меняются местами. Количество таких обменов не может превысить log₂N. After three successive passes through the while loop in sink(), the entry with prior‐ ity 9 has dropped down to a location that ensures the heap-ordered property. In each row, the leftmost highlighted entry is the entry with priority 9, and the shaded entries to the right are its children entries. Whenever the parent entry of 9 is smaller than one of its children, it must sink down to be swapped with the larger of its children. The number of swaps will never be more than log(N).

Метод .sink() наглядно показать сложнее, потому что нет однозначного «маршрута», по которому «тонет» переставленный на вершину кучи узел, — в отличие от .swim(). В окончательном состоянии storage из примера 4-19 погрузившийся на своё место узел с приоритетом 9 имеет ещё одного потомка (с приоритетом 2). После отрабатывания .sink() мы можем быть уверены, что приоритет узла не меньше (т. е. больше либо равен) приоритетов всех имеющихся у него потомков. Как частный случай, индекс ячейки p может превышать N // 2, тогда у узла потомков нет, т. к. элементов с индексами 2p и 2p + 1 нет в storage. The sink() method is the hardest to visualize because there is no straight path to fol‐ low, as with swim(). In the final representation of storage in Figure 4-19, you can see that the highlighted entry with priority 9 only has one shaded child (with priority 2). When sink() terminates, you know that the entry that was sinking has either reached an index location, p, where it has no children (i.e., because 2 × p is an invalid storage index location greater than N), or it is greater than or equal (i.e., not lesser than) the larger of its children entries.

В методе .dequeue() важно сначала уменьшить N на 1, а только потом вызвать .sink(1), иначе sink() примет элемент, лежащий за пределами кучи, за принадлежащий ей. На всякий случай, если кто-то всё-таки решит туда заглянуть, мы предварительно записываем None в storage[N] — тогда уж точно её не перепутать с узлом. В программировании такой приём — защита от ошибки, которой вроде бы и так не должно случиться — называется «hardening», усиление надёжности исходного текста.

Я выбросил глубокомысленное замечание о том, что «порядок операторов имеет значение», это какая-то уж совсем стыдоба -- FrBrGeorge 2022-09-01 19:08:39

Чтобы убедиться в правильности такой логики метода .dequeue(), посмотрим, что случиться, если куча содержит единственный элемент, а мы его снимаем. Узел max_entry мы запомнили, N уменьшили до 0, затем вызывали sink(), а он, как и ожидается, ничего не делает, потому что 2 · 1 > 0. If you want to convince yourself that the dequeue() logic is correct, consider how it operates with a heap that contains just a single entry. It will retrieve max_entry and set N to 0 before calling sink(), which will do nothing since 2 × 1 > 0.

Заключение

Summary

С помощью двоичной кучи можно эффективно реализовать абстрактный тип данных — приоритезированную очередь. Довольно много алгоритмов, например те, что мы обсудим в главе 7, пользуются этим типам данных. The binary heap structure offers an efficient implementation of the priority queue abstract data type. Numerous algorithms, such as those discussed in Chapter 7, depend on priority queues.

• Добавление в очередь пары (значение, приоритет) имеет логарифмическую вычислительную сложность O(log N). • You can enqueue() a (value, priority) entry in O(log N) performance.

• Снятие из начала очереди элемента с наивысшим приоритетом тоже имеет сложность O(log N). • You can dequeue() the entry with highest priority in O(log N) performance.

• Подсчёт количества элементов в очереди имеет константную сложность O(1). • You can report the number of entries in a heap in O(1) performance.

В этой главе мы занимались только двоичной кучей с частичным порядком убывания. Если требуется частичный порядок возрастания, когда на вершине содержится наименьший элемент, достаточно изменить совсем немного (это нам понадобится в главе 7). В примере 4-2 надо взять метод .less() и поменять в нём операцию больше на меньше («>» на «<»), не трогая сверх того ничего. In this chapter I focused exclusively on max binary heaps. You only need to make one small change to realize a min binary heap, where higher priority entries have smaller numeric priority values. This will become relevant in Chapter 7. In Listing 4-2, just rewrite the less() method to use greater-than (>) instead of less-than (<). All other code remains the same.

   1         def less(self, i, j):
   2           return self.storage[i].priority > self.storage[j].priority

Приоритезированная очередь может быть любого размера, но в нашей реализации использовалась куча фиксированного размера M, в которой можно было хранить только N < M элементов. Если куча полна, больше элементов в очередь не добавить. Мы выбрали эту реализацию, чтобы аккуратнее оценить быстродействие: посчитать количество операций сравнения и обмена, не опасаясь, что какие-то другие действия с данными не попадут в оценку. Из главы 4 мы знаем, что массив фиксированного размера всегда можно заменить на динамический массив с геометрическим масштабированием (удвоением при заполнении), это не изменит оценку сложности в среднем, так что сложность enqueue() останется O(log N). While a priority queue can grow or shrink over time, the heap-based implementation predetermines an initial size, M, to store the N < M entries. Once the heap is full, no more additional entries can be enqueued to the priority queue. It is possible to auto‐ matically grow (and shrink) the storage array, similar to what I showed in Chapter 3. As long as you use geometric resizing, which doubles the size of storage when it is full, then the overall amortized performance for enqueue() remains O(log N).

Тренировочные задания

Challenge Exercises

1. В действительности для реализации двоичной кучи произвольного размера почти ничего дополнительно делать не надо: всё равно мы используем не массив, а Python-овский list, динамические свойства которого как раз и обеспечиваются геометрическим масштабированием. Перепишите класс PQ, чтобы в приоритезированной очереди можно было хранить произвольное число элементов. Сравните быстродействие полученной структуры данных с PQ, для чего создайте достаточной длины последовательность со случайными приоритетами, добавьте их по одному в каждую из структур, а потом по одному снимите. Какая структура работает быстрее? Почему? Значимо ли это различие, т. е. есть ли основание считать, что какие-то операции над этими структурами имеют различный класс сложности?

   • Отдельно хранить .size и .N нет необходимости: они всегда равны len(storage)

   • Для работы с последней ячейкой массива используйте .append() и .pop()

   • Другие методы, такие как .insert() или .pop() с параметром, использовать нельзя: их сложность в среднем линейна, в то время как сложность .append() и .pop() константна

     • Эту задачу я добавил, чтобы у читателя не было ощущения бессмысленной работы с заведомо не нужной в жизни структурой данных; по этой же причине переформулировал предпоследнюю задачу -- FrBrGeorge 2022-09-08 11:49:26

2. Обычную очередь фиксированного размера можно весьма эффективно реализовать с помощью массива storage фиксированного размера, причём быстродействие операций enqueue() и dequeue() будет константным, O(1). Один из способов — это так называемый «кольцевой буфер», использующий простую, но остроумную идею: начальный элемент очереди не обязательно лежит в storage[0]. Достаточно просто хранить два индекса — forst, позицию того, кто стоит в очереди дольше всех, и last, позицию, куда мы поместим очередной добавляемый элемент, когда он появится. Посмотрим на иллюстрацию 4-20:

   • 1. It is possible to use a fixed array, storage, as the data structure to efficiently implement a queue, such that the enqueue() and dequeue() operations have O(1) performance. This approach is known as a circular queue, which makes the novel suggestion that the first value in the array isn’t always storage[0]. Instead, keep track of first, the index position for the oldest value in the queue, and last, the index position where the next enqueued value will be placed, as shown in Figure 4-20.

     Иллюстрация 4-20. Массив в качестве кольцевого буфера

     Figure 4-20. Using an array as a circular queue

     При каждом добавлении элемента в конец очереди и снятии элемента из её начала надо аккуратно обновлять first и last. Скорее всего, будет удобно хранить N — количество элементов в очереди, и придётся использовать остаток от деления 9операцию «%»). Изучите пример 4-4, допишите соответствующие методы и проверьте, что они действительно работают за константное время.

     • As you enqueue and dequeue values, you need to carefully manipulate these val‐ ues. You will find it useful to keep track of N, the number of values already in the queue. Can you complete the implementation in Listing 4-4 and validate that these operations complete in constant time? You should expect to use the modulo operator in your code.

        1      class Queue:
        2        def __init__(self, size):
        3          self.size = size
        4          self.storage = [None] * size
        5          self.first = 0
        6          self.last = 0
        7          self.N = 0
        8 
        9        def is_empty(self):
       10          return self.N == 0
       11 
       12        def is_full(self):
       13          return self.N == self.size
       14 
       15        def enqueue(self, item):
       16          """If not full, enqueue item in O(1) performance."""
       17 
       18        def dequeue(self):
       19          """If not empty, dequeue head in O(1) performance."""
     

     • Пример 4-4. Допишите реализацию очереди в виде кольцевого буфера Listing 4-4. Complete this Queue implementation of a circular queue

3. Добавьте в порядке возрастания N = 2^k - 1 элемент в пустую двоичную кучу размера N. Изучите получившийся массив, который хранит узлы кучи (напомним, позиция 0 в нём не используется). Можно ли предсказать, какие места в массиве будут занимать k наибольших элементов? А если в пустую двоичную кучу добавить N элементов в порядке убывания — нельзя ли предсказать место каждого элемента в массиве ячеек? Insert N = 2k – 1 elements in ascending order into an empty max binary heap of size N. When you inspect the underlying array that results (aside from the index location 0, which is unused), can you predict the index locations for the largest k values in the storage array? If you insert N elements in descending order into an empty max heap, can you predict the index locations for all N values?

4. Допустим, у нас есть две кучи размером M и N. Придумайте алгоритм, который заполняет массив размером M + N всеми элементами обеих куч в порядке возрастания за O(M log M + N log N) операций. Для подтверждения правильности алгоритма подготовьте таблицу с результатами экспериментов. Given two max heaps of size M and N, devise an algorithm that returns an array of size M + N containing the combined items from M and N in ascending order in O(M log M + N log N) performance. Generate a table of runtime perfor‐ mance to provide empirical evidence that your algorithm is working.

5. Придумайте метод получения k наименьших элементов среди произвольного набора из N элементов за время O(N log k). Для подтверждения правильности алгоритма подготовьте таблицу с результатами экспериментов. Use a max binary heap to find the k smallest values from a collection of N ele‐ ments in O(N log k). Generate a table of runtime performance to provide empirical evidence that your algorithm is working.

6. В двоичной куче у каждого узла бывает не больше двух потомков. Рассмотрим другой вариант, в котором узел на вершине кучи имеет двух потомков, каждый из них имеет трёх потомков (назовём их внуками), каждый из внуков — четырёх потомков и так далее, как показано на иллюстрации 4-21. Назовём эту структуру факториальной кучей: в ней с каждым уровнем у узлов прибавляется по дополнительному потомку. Куча должна обладать Свойствами пирамидальности и частичного порядка. Реализуйте факториальную кучу, используя хранение ячеек в массиве, проэкспериментируйте с ней, и убедитесь, что она работает медленнее двоичной. Попробуйте оценить вычислительную сложность; это задача похитрее, но в конце концов у вас должно получиться O((log N)/(log(log N))). 1. In a max binary heap, each parent entry has up to two children. Consider an alternative strategy, which I call a factorial heap, where the top entry has two chil‐ dren; each of these children has three children (which I’ll call grandchildren). Each of these grandchildren has four children, and so on, as shown in Figure 4-21. In each successive level, entries have one additional child. The heap- shape and heap-ordered property remain in effect. Complete the implementation by storing the factorial heap in an array, and perform empirical evaluation to confirm that the results are slower than max binary heap. Classifying the runtime performance is more complicated, but you should be able to determine that it is O(log N/log(log N)).

   • Иллюстрация 2-21. Инновационная факториальная куча

7. Используя геометрическое масштабирование, описанное в главе 3, доработайте кольцевой буфер из упражнения 2 так, чтобы он мог работать с произвольным количеством элементов. Переносить ячейки из старого массива в новый удобнее не по одной, а сегментами (таких сегментов будет один или два). Реализуйте уменьшение размера массива, если показатель заполнения опустился ниже ¼. 1. Using the geometric resizing strategy from Chapter 3, extend the PQ implementa‐ tion in this chapter to automatically resize the storage array by doubling in size when full and shrinking in half when ¼ full.

8. Допустим, мы хотим сделать итератор по всей куче, который возвращает по одному значения в том порядке, в котором мы снимали бы их с кучи. С одной стороны, такой итератор не должен модифицировать саму структуру, с другой — при снятии элемента с кучи нужно переструктурировать массив ячеек. Как совместить оба требования? Одно из решений — написать генератор-функцию iterator(pq), которая получает на вход приоритезированную очередь pq и создаёт её копию, pqit, откуда потом и снимает по одному все элементы. Начнём с более «надёжного» варианта, в котором pqit хранит не сами элементы pq, а их индексы в массиве pq.storage; приоритеты при этом остаются такими же, как и у соответствующих значений. По этим индексам мы и будем обращаться к pq.storage, до самого последнего момента не трогая его содержимого, и вообще не меняя его структуры. An iterator for an array-based heap data structure should produce the values in the order they would be dequeued without modifying the underlying array (since an iterator should have no side effect). However, this cannot be accomplished easily, since dequeuing values would actually modify the structure of the heap. One solution is to create an iterator(pq) generator function that takes in a pri‐ ority queue, pq, and creates a separate pqit priority queue whose values are index locations in the storage array for pq, and whose priorities are equal to the corre‐ sponding priorities for these values. pqit directly accesses the array storage for pq to keep track of the entries to be returned without disturbing the contents of storage.

   • Допишите следующий пример, в начале которого в pqit добавляется индекс 1, который соответствует элементу pq с наивысшим приоритетом. Продолжите заполнение pqit и допишите цикл while из примера: Complete the following implementation, which starts by inserting into pqit the index position, 1, which refers to the pair in pq with highest priority. Complete the rest of the while loop:

     •    1       def iterator(pq):
          2         pqit = PQ(len(pq))
          3         pqit.enqueue(1, pq.storage[1].priority)
          4         ...
          5         while pqit:
          6           idx = pqit.dequeue()
          7           yield (pq.storage[idx].value, pq.storage[idx].priority)
          8           ...
       

     Такой итератор должен возвращать все элементы pq в порядке приоритетов, не изменяя сам pq. As long as the original pq remains unchanged, this iterator will yield each of the values in priority order.

     Стоит заметить, что особой надёжности использование в куче-копии индексов вместо самих элементов, по-видимому, не добавляет. Напишите вариант нашей функции, iteratorc(pq), в которой задаётся новая куча pqit минимального размера, а затем все поля pq просто копируются туда (включая storage, который можно получить с помощью pq.storage.copy()). Будет ли такая структура надёжной: нет ли случаев, в которых что-то в pq модифицируется? Какая из функций работает быстрее и почему?