Двоичная куча — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Источники)
Строка 22: Строка 22:
 
===Восстановление свойств кучи===
 
===Восстановление свойств кучи===
  
Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры <math> \mathrm {siftDown} </math> (просеивание вниз)
+
Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры <tex> \mathrm {siftDown} </tex> (просеивание вниз)
и <math> \mathrm {siftUp} </math> (просеивание вверх).  
+
и <tex> \mathrm {siftUp} </tex> (просеивание вверх).  
Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией <math> \mathrm {siftDown} </math>.
+
Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftDown} </tex>.
Работа процедуры: если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем <math> \mathrm {siftDown} </math> для этого сына.
+
Работа процедуры: если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем <tex> \mathrm {siftDown} </tex> для этого сына.
 
Процедура выполняется за время <tex>O(\log{N})</tex>.
 
Процедура выполняется за время <tex>O(\log{N})</tex>.
  
Строка 46: Строка 46:
 
     siftDown(2 * i + 1)  
 
     siftDown(2 * i + 1)  
 
</code>
 
</code>
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией <math> \mathrm {siftUp} </math>.
+
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией <tex> \mathrm {siftUp} </tex>.
  
Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем <math> \mathrm {siftUp} </math>
+
Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем <tex> \mathrm {siftUp} </tex>
 
для этого отца. Иными словами, слишком большой элемент всплывает наверх.
 
для этого отца. Иными словами, слишком большой элемент всплывает наверх.
 
Процедура выполняется за время <tex>O(\log{N})</tex>.  
 
Процедура выполняется за время <tex>O(\log{N})</tex>.  
Строка 65: Строка 65:
 
# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
 
# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
 
# Последний элемент копируется в корень, после чего удаляется из кучи.
 
# Последний элемент копируется в корень, после чего удаляется из кучи.
# Вызывается <math> \mathrm {siftDown} </math> для корня.
+
# Вызывается <tex> \mathrm {siftDown} </tex> для корня.
 
# Сохранённый элемент возвращается.
 
# Сохранённый элемент возвращается.
  
Строка 78: Строка 78:
  
 
Выполняет добавление элемента в кучу за время <tex>O(\log{N})</tex>.
 
Выполняет добавление элемента в кучу за время <tex>O(\log{N})</tex>.
Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью процедуры <math> \mathrm {siftUp} </math>.
+
Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью процедуры <tex> \mathrm {siftUp} </tex>.
  
 
  '''function''' insert(key):
 
  '''function''' insert(key):
Строка 90: Строка 90:
 
}}
 
}}
  
Дан массив <tex>A[0.. N - 1].</tex> Требуется построить <tex>D</tex>-кучу с минимумом в корне. Наиболее очевидный способ построить такую кучу из неупорядоченного массива - по очереди добавить все его элементы (сделать <math> \mathrm {siftDown} </math> для каждого). Временная оценка такого алгоритма <tex> O(N\log{N})</tex>.  Однако можно построить кучу еще быстрее — за <tex> O(N) </tex>.  
+
Дан массив <tex>A[0.. N - 1].</tex> Требуется построить <tex>D</tex>-кучу с минимумом в корне. Наиболее очевидный способ построить такую кучу из неупорядоченного массива - по очереди добавить все его элементы (сделать <tex> \mathrm {siftDown} </tex> для каждого). Временная оценка такого алгоритма <tex> O(N\log{N})</tex>.  Однако можно построить кучу еще быстрее — за <tex> O(N) </tex>.  
Представим, что в массиве хранится дерево (<tex>A[0] - </tex>  корень, а потомками элемента <tex>A[i]</tex> являются <tex>A[2i+1]...A[2i+D]</tex>). Сделаем <math> \mathrm {siftDown} </math> для вершин, имеющих хотя бы одного потомка, начиная с конца(от <tex> n - 1</tex> до <tex>0</tex>) (так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены).  
+
Представим, что в массиве хранится дерево (<tex>A[0] - </tex>  корень, а потомками элемента <tex>A[i]</tex> являются <tex>A[2i+1]...A[2i+D]</tex>). Сделаем <tex> \mathrm {siftDown} </tex> для вершин, имеющих хотя бы одного потомка, начиная с конца(от <tex> n - 1</tex> до <tex>0</tex>) (так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены).  
 
{{Лемма
 
{{Лемма
 
|statement= На выходе получим искомую кучу.  
 
|statement= На выходе получим искомую кучу.  
|proof= При вызове <math> \mathrm {siftDown} </math> для вершины, ее поддерево является кучей, после выполнения <math> \mathrm {siftDown} </math> поддерево с этой вершиной будет являться кучей.  Значит после выполнения всех <math> \mathrm {siftDown} </math> получится куча.
+
|proof= При вызове <tex> \mathrm {siftDown} </tex> для вершины, ее поддерево является кучей, после выполнения <tex> \mathrm {siftDown} </tex> поддерево с этой вершиной будет являться кучей.  Значит после выполнения всех <tex> \mathrm {siftDown} </tex> получится куча.
 
}}
 
}}
 
{{Лемма
 
{{Лемма

Версия 15:33, 12 июня 2014

Определение

Определение:
Двоичная куча или пирамида — такое двоичное подвешенное дерево, для которого выполнены следующие три условия:
  • Значение в любой вершине не меньше, (если куча для максимума), чем значения её потомков.
  • На [math]i[/math]-ом слое [math]2^i[/math] вершин, кроме последнего. Слои нумеруются с нуля.
  • Последний слой заполнен слева направо (как показано на рисунке)


Пример кучи для максимума

Удобнее всего двоичную кучу хранить в виде массива [math]A[0..n-1][/math], у которого нулевой элемент, [math]A[0][/math] — элемент в корне, а потомками элемента [math]A[i][/math] являются [math]A[2i+1][/math] и [math]A[2i+2][/math]. Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть [math]O(\log{N})[/math], где [math]N[/math] — количество узлов дерева.

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

Двоичные кучи используют, например, для того, чтобы извлекать минимум из набора чисел за [math]O(\log{N})[/math]. Двоичные кучи — частный случай приоритетных очередей.

Базовые процедуры

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

Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры [math] \mathrm {siftDown} [/math] (просеивание вниз) и [math] \mathrm {siftUp} [/math] (просеивание вверх). Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией [math] \mathrm {siftDown} [/math]. Работа процедуры: если [math]i[/math]-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами [math]i[/math]-й элемент с наименьшим из его сыновей, после чего выполняем [math] \mathrm {siftDown} [/math] для этого сына. Процедура выполняется за время [math]O(\log{N})[/math].

function siftDown(i):
  // heap_size - количество элементов в куче
  if 2 * i + 1 <= A.heap_size 
    left = A[2 * i + 1] // левый сын
  else
    left = inf
  if (2 * i + 2 <= A.heap_size) 
    right = A[2 * i + 2] // правый сын
  else
    right = inf
  if (left == right == inf) return
  if (right <= left && right < A[i])
    swap(A[2 * i + 2], A[i])
    siftDown(2 * i + 2)  
  if (left < A[i]) 
    swap(A[2 * i + 1], A[i])
    siftDown(2 * i + 1) 

</code> Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией [math] \mathrm {siftUp} [/math].

Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем [math] \mathrm {siftUp} [/math] для этого отца. Иными словами, слишком большой элемент всплывает наверх. Процедура выполняется за время [math]O(\log{N})[/math].

function siftUp(i):
  if i == 0 
    return //Мы в корне
    if A[i] < A[i / 2]
      swap(A[i], A[i / 2])
      siftUp(i / 2)

Извлечение минимального элемента

Выполняет извлечение минимального элемента из кучи за время [math]O(\log{N})[/math]. Извлечение выполняется в четыре этапа:

  1. Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
  2. Последний элемент копируется в корень, после чего удаляется из кучи.
  3. Вызывается [math] \mathrm {siftDown} [/math] для корня.
  4. Сохранённый элемент возвращается.
function extractMin():
  min = A[0]
  A[0] = A[A.heap_size - 1]
  A.heap_size = A.heap_size - 1
  siftDown(0)
  return min

Добавление нового элемента

Выполняет добавление элемента в кучу за время [math]O(\log{N})[/math]. Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью процедуры [math] \mathrm {siftUp} [/math].

function insert(key):
  A.heap_size = A.heap_size + 1
  A[A.heap_size - 1] = key
  siftUp(A.heap_size - 1)

Построение кучи за O(N)

Определение:
[math]D[/math]-куча — это куча, в которой у каждого элемента, кроме, возможно, элементов на последнем уровне, ровно [math]D[/math] потомков.


Дан массив [math]A[0.. N - 1].[/math] Требуется построить [math]D[/math]-кучу с минимумом в корне. Наиболее очевидный способ построить такую кучу из неупорядоченного массива - по очереди добавить все его элементы (сделать [math] \mathrm {siftDown} [/math] для каждого). Временная оценка такого алгоритма [math] O(N\log{N})[/math]. Однако можно построить кучу еще быстрее — за [math] O(N) [/math]. Представим, что в массиве хранится дерево ([math]A[0] - [/math] корень, а потомками элемента [math]A[i][/math] являются [math]A[2i+1]...A[2i+D][/math]). Сделаем [math] \mathrm {siftDown} [/math] для вершин, имеющих хотя бы одного потомка, начиная с конца(от [math] n - 1[/math] до [math]0[/math]) (так как поддеревья, состоящие из одной вершины без потомков, уже упорядочены).

Лемма:
На выходе получим искомую кучу.
Доказательство:
[math]\triangleright[/math]
При вызове [math] \mathrm {siftDown} [/math] для вершины, ее поддерево является кучей, после выполнения [math] \mathrm {siftDown} [/math] поддерево с этой вершиной будет являться кучей. Значит после выполнения всех [math] \mathrm {siftDown} [/math] получится куча.
[math]\triangleleft[/math]
Лемма:
Время работы этого алгоритма [math] O(N) [/math].
Доказательство:
[math]\triangleright[/math]

Число вершин на высоте [math]h[/math] в куче из [math]N[/math] элементов не превосходит [math] \left \lceil \frac{N}{D^h} \right \rceil [/math]. Высота кучи не превосходит [math] \log_{D}N [/math]. Обозначим за [math] H [/math] высоту дерева, тогда время построения не превосходит

[math] \sum_{h = 1}^H \limits\frac{N}{D^h} \cdot D [/math] [math] \cdot h [/math] [math] = N \cdot D \cdot {\sum_{h = 1}^H \limits}\frac{h}{D^h}. [/math]

Докажем вспомогательную лемму о сумме ряда.

Лемма:
[math] {\sum_{h = 1}^\infty \limits}\frac{h}{D^h} = \frac{D}{(D - 1)^2} . [/math]
Доказательство:
[math]\triangleright[/math]

Обозначим за [math]S[/math] сумму ряда. Заметим, что [math] \frac{n}{D^n} = \frac{1}{D} \cdot \frac{n - 1}{D ^{n - 1}} + \frac{1}{D^n}. [/math]

[math]{\sum_{n = 1}^\infty \limits}\frac{1}{d^n}[/math] — это сумма бесконечной убывающей геометрической прогрессии, и она равна [math] \frac{\frac{1}{D}}{1 - \frac{1}{D}} = \frac{1}{D - 1}. [/math]

Получаем [math]S[/math] [math]=\frac{1}{D}[/math] [math]\cdot S +[/math] [math] \frac{1}{D - 1}. [/math] Откуда [math]S[/math] [math] = \frac{D}{(D - 1)^2}. [/math]
[math]\triangleleft[/math]
Подставляя в нашу формулу результат леммы, получаем [math]N[/math] [math]\cdot (\frac {D}{D - 1})^2 [/math] [math] \lt 5 \cdot N [/math] [math]=O(N).[/math]
[math]\triangleleft[/math]

Источники