7. heti jegyzet (2014.11.20.)

Órai anyag:

Strázsa elemek.

Prioritási sorok. Kupac adatszerkezet.

Min-kupac strázsa elemek segítségével. (Bár ez nem a legjobb alkalmazási helyük, mert így csak a tömb felét tudjuk kihasználni.)
(A kupacba rekordokat pakolhatunk, melyek pr mezője jelöli a prioritást.)
init
| meret:=0
| for i:=1 to n //1-től indexelt tömbbel kicsivel szebb lesz a kód
| | t[i].pr:=inf //strázsa
berak(x)
| meret++
| t[meret]:=x
| i:=meret
| while i>1 && t[i/2].pr>t[i].pr
| | csere(t[i],t[i/2])
| | i:=i/2
kivesz
| r:=t[1]
| t[1]:=t[meret]
| t[meret].pr:=inf //strázsa
| meret--
| i:=1
| while t[i].pr>min(t[2*i].pr,t[2*i+1].pr)
| | j:=t[2*i].pr<t[2*i+1].pr?2*i:2*i+1
| | csere(t[i],t[j])
| | i:=j
| return r


Házi:

Egy kézműves n db munkát vállalt el. Mindegyik feladatról ismert, hogy hány napig tart az elkészítése, és hogy hanyadik nap végére kell elkészülnie.
A munkát az 1. napon kezdi, és egyszerre csak egy feladaton dolgozhat.
Van-e olyan ütemezése a feladatoknak, mely minden határidőt tiszteletben tart?
Bemenet: a munkák n száma, majd n db számpár: az egyes munkák elkészítési ideje és határideje.
Kimenet: "igen" vagy "nem"
Időkorlát: O(n * log n)