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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
(Восстановление свойств кучи)
Строка 24: Строка 24:
 
===Восстановление свойств кучи===
 
===Восстановление свойств кучи===
  
Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры '''Sift_Down''' (просеивание вниз) и '''Sift_Up''' (просеивание вверх). Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией '''Sift_Down(i)'''.
+
Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры '''sift_down''' (просеивание вниз) и '''sift_up''' (просеивание вверх). Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией ''sift_down(i)'''.
Работа процедуры: если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем '''Sift_Down()''' для этого сына.
+
Работа процедуры: если <tex>i</tex>-й элемент меньше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наименьшим из его сыновей, после чего выполняем '''sift_down()''' для этого сына.
 
Процедура выполняется за время <tex>O(\log{N})</tex>.
 
Процедура выполняется за время <tex>O(\log{N})</tex>.
  
Строка 43: Строка 43:
 
   If (min <> i)  
 
   If (min <> i)  
 
     Поменять A[i] и A[minimum]
 
     Поменять A[i] и A[minimum]
     Sift_Down(min)
+
     sift_down(min)
 
</code>
 
</code>
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией '''Sift_Up(i)'''.
+
Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией '''sift_up(i)'''.
  
Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем '''Sift_Up''' для этого отца. Иными словами, слишком большой элемент всплывает наверх.
+
Работа процедуры: если элемент больше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Иначе, мы меняем местами его с отцом. После чего выполняем '''sift_up''' для этого отца. Иными словами, слишком большой элемент всплывает наверх.
 
Процедура выполняется за время <tex>O(\log{N})</tex>.  
 
Процедура выполняется за время <tex>O(\log{N})</tex>.  
  
Строка 54: Строка 54:
 
   If (A[i] < A[i / 2])
 
   If (A[i] < A[i / 2])
 
     Поменять A[i] и A[i / 2]
 
     Поменять A[i] и A[i / 2]
     Sift_Up(i / 2)
+
     sift_up(i / 2)
 
</code>
 
</code>
  

Версия 22:25, 18 марта 2012

Определение

Определение:
Двоичная куча или пирамида — такое двоичное дерево, для которого выполнены три условия:
  • Значение (ключ) в любой вершине не больше (если куча для минимума), чем значения её потомков.
  • Полное двоичное дерево, у которого могут отсутствовать некоторые листья последнего слоя.
  • Последний слой заполняется слева направо.


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

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

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

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

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

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

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

sift_down(i)
 left = 2 * i // левый сын
 right = 2 * i + 1 // правый сын
 // heap_size - количество элементов в куче
 If (left <= A.heap_size) and (A[left] < A[i])  
   min = left
 else
   min = i
 If (right <= A.heap_size) and (A[right] < A[i])  
   min = right
 else
   min = i
 If (min <> i) 
   Поменять A[i] и A[minimum]
   sift_down(min)

Если значение измененного элемента уменьшается, то свойства кучи восстанавливаются функцией sift_up(i).

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

sift_up(i)
 If (A[i] < A[i / 2])
   Поменять A[i] и A[i / 2]
   sift_up(i / 2)

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

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

  1. Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
  2. Последний элемент копируется в корень, после чего удаляется из кучи.
  3. Вызывается Sift_Down(i) для корня.
  4. Сохранённый элемент возвращается.

extract_min()
 min = A[1]
 A[1] = A[A.heap_size]
 A.heap_size = A.heap_size - 1
 Sift_Down(1)
 return min

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

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

insert(key)
 A.heap_size = A.heap_size + 1
 A[A.heap_size] = key
 Sift_Up(A.heap_size)

Источники