Часть VII : Heap

1. Значение в любой вершине не меньше, чем значения её потомков.

2. Глубина листьев (расстояние до корня) отличается не более чем на 1 слой.

3. Последний слой заполняется слева направо.

length(A) – количество элементов массива

heap_size(A) – количество элементов пирамиды, содержащихся в массиве

heap_size(A)  length(A)

• Если A_i – промежуточный узел дерева, то для него:

  1. индекс родительского узла parent(i) = i / 2

  2. индекс левого дочернего узла left(i) = 2i

  3. индекс правого дочернего узла right(i) = 2i + 1

• невозрастающие – max-heap property: A_parent(i)  A_i пирамидальные сортировки

• неубывающие – min-heap property: A_parent(i)  A_i очереди с приоритетами

4. Heapify(A, i)

5. left = 2i

6. right = 2i+1

7. heap_size - количество элементов в куче

8. if left ≤ A.heap_size и A[left] > A[i]

9. then largest = left

10. else largest = i

11. if right ≤ A.heap_size и A[right] > A[largest]

12. then largest = right

13. if largest ≠ i

14. then Обменять A[i] ↔ A[largest]

15. Heapify(A, largest)

16. Build-Heap(A)

17. A.heap_size ← A.length

18. for i ← ⌊A.length/2⌋ downto 1

19. do Heapify(A, i)

sort

Heapsort(A)

Build_Max_Heap(A)

for i ← A.length downto 1

do Обменять A[1] ↔ A[i]

A.heap_size ← A.heap_size-1

Heapify(A,1)

Edit

Heap_Increase_Key(A, i, key)

if key < A[i]

then error "Новый ключ меньше предыдущего"

A[i] ← key

while i > 1 и A[⌊i/2⌋] < A[i]

do Обменять A[i] ↔ A[⌊i/2⌋]

i ← ⌊i/2⌋

insert

Heap_Insert(A, key)

A.heap_size ← A.heap_size+1

A[A.heap_size] ← -∞

Heap_Increase_Key(A, A.heap_size, key)

Max

Heap_Extract_Max(A)

if A.heap_size[A] < 1

then error "Куча пуста"

max ← A[1]

A[1] ← A[A.heap_size]

A.heap_size ← A.heap_size-1

Heapify(A, 1)

return max

Часть VIII : Skip-List

списки с пропусками: вероятностная структура данных; альтернатива сбалансированным деревьям

p = ½ Уровень элемента списка ограничен некоторым значением MaxLevel

Заголовок Skip Lists – содержит уровень списка и массив из MaxLevel указателей

Указатели заголовка списка для уровней, превышающих текущий уровень списка, указывают на специальный элемент EList

Уровень элемента генерируется случайным образом независимо от количества элементов в Skip List

struct Item { … }; – элемент списка в Skip Lists

struct SkipLists {

int level; – текущий уровень списка

struct Item *header; – указатель на головной элемент

};

Level()

level = 1

while random() < p и level < MaxLevel

level = level + 1

search

x = list->header – указатель на первый элемент верхнего уровня

цикл по i от list->level – 1 до 0 {

while x->forward[i]->key < k

x = x->forward[i]

}

x = x->forward[0]

if x->key = k успех: x else отказ

insert

цикл по i от list->level – 1 до 0 {

while x->forward[i]->key < k

x = x->forward[i]

update[i] = x – позиция предшествующего элемента i-го уровня

}

x = x->forward[0] – элемент, перед которым нужно вставить новый

if x->key = k

отказ

level = Level()

if list->level < level {

добавить в элементы update[i] значения list->header

list->level = level

}

для всех i от 0 до level – 1 {

x->forward[i] = update[i]->forward[i]

update[i]->forward[i] = x

}

DELETE

Как в insert только update[i]->forward[i] = x->forward[i]