Minimum Stack
A gyakorlaton láttuk, hogyan lehet egy minimum lekérdezését támogató vermet megalkotni. Ez egy olyan megoldás volt, ahol plusz $O(n)$ tárat használtunk fel. A továbbiakban megnézzük, hogyan lehet egy teljes plusz verem helyett egyetlen változóval, azaz plusz konstans tárral ugyanezt a logikát megvalósítani.
Egyetlen változóban fogjuk feljegyezni az aktuális minimumot, legyen ez $MinE$. Ez egy stack elem esetén ugyanaz, viszont nem csak push() műveletek után kell tudnunk megmondani a minimumot, hanem minden részveremre, így az az érdekes eset, hogy egyetlen változóval hogyan kezeljük azt, ha kivesszük az aktuális minimumot a veremből. Hogyan jegyezzük tehát meg, hogy ki volt a törölt elem alatt a minimum? A koncepció az, hogy ha egy új $x$ minimumot érkezik, helyette a $2x-MinE$ értéket rakjuk a verembe, így amikor törlünk, vissza tudjuk állítani az információt a maradék tömbre is. A műveletek a következőképpen működnek:
Push(x) : Az $x$ elemet a verem tetejére teszi.
- Ha a verem üres, szúrjuk be $x$-et a verembe és legyen $MinE=x$.
- Ha a verem nem üres hasonlítsuk össze $x$-et és $MinE$-t. Ekkor két eset lehetséges:
- Ha $x\geq MinE$, csak szúrjuk be $x$-et a verembe és kész.
- Ha $x<MinE$, szúrjuk be a $(2*x – MinE)$ értéket a verembe és legyen $MinE=x$. (Note: Vegyük észre, ilyenkor az aktális elemnél mindenképp egy kisebbet fogunk kapni!)
Pop() : Törli a verem tetején lévő értéket
- Vegyük ki a legfelső elemet. Legyen ez $y$. Két eset lehetséges:
- Ha $y\geq MinE$, nincs dolgunk, továbbra is $MinE$ a minimum az érték pedig a tényleges kivett érték.
- Ha $y < MinE$, akkor az aktuális minimumot töröljük és az alattalévők minimumát a $(2*MinE – y)$ értékből kapjuk vissza. Tehát jegyezzük fel az aktuális minimumot, mivel a jelenlegi érték helyett azt kell visszaadjuk, majd legyen $MinE = 2*MinE – y$.
Technikai részletek:
- A részminimumok sosem az eredeti értékükkel tárolódnak a veremben
- Viszont az aktuális minimumot mindig számon tartjuk a $MinE$ változóban, így $O(1)$ idő alatt vissza tudjuk adni.
- A Pop(), Push(x) és Min() műveletek továbbra is konstans időben elvégezhetőek
- A felhasznált plusz tár csupán egyetlen változó, ami $O(1)$
Példa:
| Beszúrt szám | Aktuálus veremtartalom | $MinE$ |
|---|---|---|
| 3 | 3 | 3 |
| 5 | 5 3 | 3 |
| 2 | 1 5 3 | 2 |
| 1 | 0 1 5 3 | 1 |
| 1 | 1 0 1 5 3 | 1 |
| -1 | -3 1 0 1 5 3 | -1 |
| Működése: |
| A verem üres, beszúrjuk a verembe és felveszi az értékét $MinE$ is |
| Az $5$ nagyobb, mint $3$, így nincs extra művelet. |
| A $2 < 3$: szúrjuk be a $2*2-3 = 1$ elemet, és $MinE$ értékét állítsuk az aktuális minimumra |
| Az $1< 2$: szúrjuk be a $2*1 - 2 = 0$ elemet, és $MinE=1$ |
| $1=1$, nincs más dolgunk, mint beszúrni |
| $-1<1$, beszúrjuk a $2*-1-1=-3$ elemet és $MinE=-1$ |
| Kivett érték | Eredeti érték | Aktuálus veremtartalom | $MinE$ |
|---|---|---|---|
| - | - | -3 1 0 1 5 3 | -1 |
| -3 | -1 | 1 0 1 5 3 | 1 |
| 1 | 1 | 0 1 5 3 | 1 |
| 0 | 1 | 1 5 3 | 2 |
| 1 | 2 | 5 3 | 3 |
| 5 | 5 | 3 | 3 |
| Működése: |
| Az aktiális minimum -1 |
| A kivett elem $-3<-1$. Visszaadni a $MinE$-t fogjuk, és $MinE$ új értéke $2*-1-(-3)=1$ |
| A kivett elem $1=1$. Nincs dolgunk. |
| A kivett elem $0<1$. Visszaadni a $MinE$-t fogjuk, és $MinE$ új értéke $2*1-0=2$ |
| A kivett elem $1<2$. Visszaadni a $MinE$-t fogjuk, és $MinE$ új értéke $2*2-1=3$ |
| A kivett elem $5>3$, nincs dolgunk |
(Forrás)
tipus: