333
правки
Изменения
Нет описания правки
'''function''' siftDown(i : '''int'''):
'''while''' 2 * i + 1 < A.heapSize <font color = "green">// heapSize {{---}} количество элементов в куче</font>
left <tex>= </tex> 2 * i + 1 <font color = "green">// left {{---}} левый сын</font> right <tex>= </tex> 2 * i + 2 <font color = "green">// right {{---}} правый сын</font> j <tex>= </tex> left '''if''' right < tex><</tex> A.heapSize '''and''' A[right] <= tex>\leqslant</tex> A[left] j <tex>= </tex> right '''else if''' A[i] <= tex>\leqslant</tex> A[j]
'''break'''
swap(A[i], A[j])
i <tex>= </tex> j
</code>
<code>
'''function''' siftUp(i : '''int'''):
'''while''' A[i] < A[(i - 1) / 2] <font color = "green">// i <tex>== </tex> 0 {{---}} мы в корне</font>
swap(A[i], A[(i - 1) / 2])
i <tex>= </tex> (i - 1) / 2
</code>
<code>
'''int''' extractMin():
'''int''' min <tex>= </tex> A[0] A[0] <tex>= </tex> A[A.heap_size - 1] A.heap_size <tex>= </tex> A.heap_size - 1
siftDown(0)
'''return''' min
<code>
'''function''' insert(key : '''int'''):
A.heap_size <tex>= </tex> A.heap_size + 1 A[A.heap_size - 1] <tex>= </tex> key
siftUp(A.heap_size - 1)
</code>
