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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
{{В разработке}}
+
==Определение==
  
 
{{Определение
 
{{Определение
Строка 7: Строка 7:
 
* Значение (ключ) в любой вершине не больше, чем значения её потомков.
 
* Значение (ключ) в любой вершине не больше, чем значения её потомков.
  
* Каждый лист имеет глубину (расстояние до корня) либо <tex>d</tex> либо <tex>d-1</tex>. Иными словами, если назвать слоем совокупность вершин, находящихся на определённой глубине, то все слои, кроме, быть может, последнего, заполнены полностью.
+
* Каждый лист имеет глубину (расстояние до корня) либо <tex>d</tex> либо <tex>d-1</tex>. Иными словами, если назвать слоем совокупность вершин, находящихся на определённой глубине, то все слои, кроме последнего заполнены полностью.
  
 
* Последний слой заполняется слева направо.
 
* Последний слой заполняется слева направо.
 
}}
 
}}
 
  
 
Удобная структура данных для сортирующего дерева — массив <tex>A</tex>, у которого первый элемент, <tex>A[1]</tex> — элемент в корне, а потомками элемента <tex>A[i]</tex> являются <tex>A[2i]</tex> и <tex>A[2i+1]</tex>. Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть <tex>O(logN)</tex>, где <tex>N</tex> — количество узлов дерева.
 
Удобная структура данных для сортирующего дерева — массив <tex>A</tex>, у которого первый элемент, <tex>A[1]</tex> — элемент в корне, а потомками элемента <tex>A[i]</tex> являются <tex>A[2i]</tex> и <tex>A[2i+1]</tex>. Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть <tex>O(logN)</tex>, где <tex>N</tex> — количество узлов дерева.
Строка 20: Строка 19:
  
 
Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры '''Shift_Down'''(просеивание вниз) и '''Shift_Up'''(просеивание вверх). Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией '''Shift_Down(i)'''.
 
Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служат процедуры '''Shift_Down'''(просеивание вниз) и '''Shift_Up'''(просеивание вверх). Если значение измененного элемента увеличивается, то свойства кучи восстанавливаются функцией '''Shift_Down(i)'''.
Работа процедуры : если <tex>i</tex>-й элемент больше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наибольшим из его сыновей, после чего выполняем '''Shift_Down''' для этого сына.
+
Работа процедуры : если <tex>i</tex>-й элемент больше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами <tex>i</tex>-й элемент с наибольшим из его сыновей, после чего выполняем '''Shift_Down(i)''' для этого сына.
 
Процедура выполняется за время <tex>O(logN)</tex>.
 
Процедура выполняется за время <tex>O(logN)</tex>.
  
Строка 58: Строка 57:
 
# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
 
# Значение корневого элемента (он и является минимальным) сохраняется для последующего возврата.
 
# Последний элемент копируется в корень, после чего удаляется из кучи.
 
# Последний элемент копируется в корень, после чего удаляется из кучи.
# Вызывается '''Shift_Down''' для корня.
+
# Вызывается '''Shift_Down(i)''' для корня.
 
# Сохранённый элемент возвращается.
 
# Сохранённый элемент возвращается.
 
<code>
 
<code>

Версия 00:01, 23 марта 2011

Определение

Определение:
Двоичная куча или пирамида — такое двоичное дерево, для которого выполнены три условия:
  • Значение (ключ) в любой вершине не больше, чем значения её потомков.
  • Каждый лист имеет глубину (расстояние до корня) либо [math]d[/math] либо [math]d-1[/math]. Иными словами, если назвать слоем совокупность вершин, находящихся на определённой глубине, то все слои, кроме последнего заполнены полностью.
  • Последний слой заполняется слева направо.


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

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

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

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

Shift_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[largest]
   Shift_Down(A, min)

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

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

Shift_Up(i)

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

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

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

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

extract_min()

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

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

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

Insert(key)

 A.heap_size = A.heap_size + 1
 A[A.heap_size] = key;
 Shift_Up(A.heap_size)

Источники