Yığınla çeşidləmə massivi ikili max-yığına çevirir və sonra maksimumu dəfələrlə massivin sonuna köçürür. Bu, O(n log n) pis hal zəmanəti, O(1) əlavə yaddaşı və rekursiyasızlığı olan nadir çeşidləmədir. Burada yığın yalnız çeşidləmə vasitəsidir; strukturun özü və heapq modulu yığınlar və heapq dərsində izah olunur.
Massivdə yığın
Max-yığın hər valideynin övladlarından kiçik olmadığı ikili ağacdır; kök maksimumdur. O, göstəricilər olmadan massivdə saxlanır: i-nin övladları 2i + 1 və 2i + 2, valideyni (i - 1) // 2-dir. Ağacın səviyyələri massivdə ardıcıl düzülür.
a = [10, 5, 7, 4, 1, 3, 2]
for i in range(len(a)):
left, right = 2 * i + 1, 2 * i + 2
parent = (i - 1) // 2
kids = [a[k] for k in (left, right) if k < len(a)]
print(i, a[i], "parent", a[parent] if i else None, "children", kids)
def is_max_heap(a):
return all(a[(i - 1) // 2] >= a[i] for i in range(1, len(a)))
print(is_max_heap(a), is_max_heap([1, 5, 3]))0 10 parent None children [5, 7]
1 5 parent 10 children [4, 1]
2 7 parent 10 children [3, 2]
3 4 parent 5 children []
4 1 parent 5 children []
5 3 parent 7 children []
6 2 parent 7 children []
True Falsesift_down
sift_down(a, i, n) a[:n] yığınında i düyününü aşağı endirir: düyün övladlarından kiçik olmayana qədər onu böyük övladı ilə dəyişir. Vaxt yığının hündürlüyü qədərdir, O(log n).
