Heap-ul (coada cu priorități) cu heapq
La camera de gardă nu intră primul venit, ci pacientul cu urgența cea mai mare. Ai nevoie de o structură care îți dă mereu cel mai important element, chiar dacă elementele noi vin pe rând. Aceasta este coada cu priorități, implementată cu un heap. În Python o ai gata în modulul heapq.
Ce este un heap
Un min-heap este un arbore binar complet în care fiecare părinte este mai mic sau egal decât copiii lui. Consecința: minimul este mereu în rădăcină. Arborele nu este ținut cu noduri, ci într-o simplă listă: copiii elementului de la indicele i sunt la 2*i + 1 și 2*i + 2.
import heapq
heap = []
for x in [7, 2, 9, 4, 1]:
heapq.heappush(heap, x)
print(f'push {x}: {heap} -> minimul: {heap[0]}') Scrie k_cele_mai_mici(lista, k) care returnează cele mai mici k valori în ordine crescătoare (dacă lista are mai puțin de k elemente, le returnează pe toate), folosind heapify și heappop. Apoi scrie ordine_tratare(pacienti), care primește t…
- k_cele_mai_mici: copiezi lista, heapq.heapify(...), apoi scoți de min(k, len(heap)) ori cu heappop.
- ordine_tratare: pui tuplurile în heap cu heappush, apoi le scoți pe rând și păstrezi numele.
- Trebuie să apară: [1, 2, 3], [4], [6, 8], [], ['Ion', 'Maria', 'Ana'], ['Dan', 'Elena', 'Bogdan', 'Radu'].
Restul explicațiilor, editorul și verificarea automată se deblochează cu Arbori, grafuri și heap.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan