Yığın və heapq

Sıralı siyahı minimumu O(1)-də verir, amma əlavə O(n)-dir. Sıralanmamış siyahıda əlavə O(1), minimumun tapılması O(n)-dir. Yığın (heap) orta yoldur: əlavə və minimumun çıxarılması O(log n), minimuma baxış O(1). Prioritetli növbə və yığın sıralaması bunun üzərində qurulur.

Yığın nədir

• Min-yığın: hər düyün uşaqlarından kiçik və ya bərabərdir, ona görə kök minimumdur. Max-yığında əksinədir.
• Bu tam ikili ağacdır: son səviyyə istisna olmaqla bütün səviyyələr doludur, sonuncu isə soldan sağa dolur.
• Yığın tam sıralanmış deyil: yalnız valideyn-uşaq münasibəti saxlanır, qardaşlar arasında sıra yoxdur.

Tamlıq ağacı göstəricisiz massivdə saxlamağa imkan verir. 0-dan başlayan i indeksi üçün: valideyn (i - 1) // 2, uşaqlar 2i + 1 və 2i + 2.

heap = [1, 3, 2, 7, 4, 5, 6]

def is_min_heap(a):
    return all(a[(i - 1) // 2] <= a[i] for i in range(1, len(a)))

i = 1
print("node", heap[i], "parent", heap[(i - 1) // 2])
print("children", heap[2 * i + 1], heap[2 * i + 2])
print(is_min_heap(heap), is_min_heap([3, 1, 2]))

node 3 parent 1
children 7 4
True False

push və pop

push elementi sona yazır və yuxarı süzür: valideynindən kiçikdirsə, yerlərini dəyişir. pop kökü götürür, yerinə sonuncu elementi qoyur və onu aşağı süzür: sıra bərpa olunana qədər kiçik uşaqla yer dəyişir. Hər ikisi bir budaq boyunca gedir, ona görə O(log n) başa gəlir.

class MinHeap:
    def __init__(self):
        self.a = []