Куча

Куча — структура данных в которой значение в родителе меньше чем значение в каждом из её детей.

Добавление значения в кучу

При добавлении нового элемента в кучу он добавляется в конец. Далее нужно проверить не нарушено ли свойство кучи т.е. значение родителя должно быть меньше значения добавленного элемента, если это не так то необходимо просеить добавленный элемент вверх.

Процедура просеивания элемента вверх заключается в том, что если значение элемента меньше значения его родителя, то мы меняем родителя и элемент местами.

# т.е. нумерация элементов в списке(массиве) начинается не с 1, а с 0 то формула нахождения предка изменится с i//2 на (i-1)//2
def parent(i):
    return (i-1)//2

def sift_up(heap, i):
    while i > 1 and heap[parent(i)] < heap[i]:
        heap[parent(i)], heap[i] = heap[i], heap[parent(i)]
        i = parent(i)
    return heap

Пояснения по коду:

1. Пока i > 1 т.е. до тех пор пока мы не пришли в корень и значение в родителе меньше значения в сыне
2. Меняем местами значения родителя и сына
3. i присваиваем индекс родителя
4. Выполняем цикл еще раз, если подходят условия

После выполнения полного цикла просеивания вверх, куча будет выглядеть так:

После этого операция добавления элемента в кучу будет выглядеть так (предполагается, что мы храним кучу в обычном списке — list)

def insert_heap(heap, value):
	heap.append(value)
	sift_up(heap, heap[-1])

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

Очевидно, что минимальный элемент в куче будет в её корне, т.е. в самом начале если представлять кучу в виде списка(массива).

Алгоритм извлечения минимального элемента

Забираем элемент из начала кучи, на его место ставим последний элемент из кучи, после чего просеиваем этот элемент вниз.

Утапливание винз

1. Начинаем из корня кучи (первый элемент)

2. Далее смотрим выполняется ли условия кучи, т.е. дети больше родителя, если нет меняем родителя с меньшим из детей.

# т.к. индексации в массиве начинается не с 1 а с 0, индекс левого соседа будет не [2*i], а [2*i+1] 
# и индекс правого соседа будет не [2*i+1], а [2*i+2]
sift_down(heap, i):
	while (2*i <= len(heap)):
		j = i
		# Если значение в левом соседе меньше, то j равен индексу левого соседа
		if heap[2*i+1] < len(heap) and heap[2*i+1] < heap[j]:
			j = 2*i+1
			
		# Если значение в правом соседе меньше, то j равен индексу правого соседа 
		if heap[2*i+2] < len(heap) and heap[2*i+2] < heap[j]:
			j = 2*i+2
			
		# Если условия выше не выполнелись, то значит в детях равные элементы с родителем
		# ничего менять не нужно, выходим из цикла 
		if j = i:
			break
			
		# Меняем значения родителя на значение меньшего из детей. 
		# крутим цикл дальше
		heap[i] = heap[j]
		i = j

Извлечение минимума

def extract_min(heap):
	heap_min = heap[0]
	heap[0] = heap.pop()
	sift_down(0)
	return heap_min