Primena efikasnih struktura podataka

3.8 Primena efikasnih struktura podataka

Izbor strukture podataka može u velikoj meri uticati na efikasnost. U nastavku ćemo prikazati nekoliko primera koji ovo ilustruju.

3.8.1 Primena skupova i mapa

Većina savremenih programskih jezika nudi gotove tipove podataka koji implementiraju skupove i mape. U jeziku C++ su to set i map koji omogućavaju osnovne operacije (umetanje, pretraga, brisanje) u složenosti \(O(\log{n})\), gde je \(n\) broj elemenata skupa tj. ključeva u mapi i unordered_set i unordered_map čija je amortizovana složenost osnovnih operacija \(O(1)\), ali je složenost najgoreg slučaja \(O(n)\). Iako imaju malo lošiju prosečnu složenost operacija, uređeni skupovi nude neke dodatne operacije – pronalaženje najmanjeg ili najvećeg elemenata (pomoću begin i end), obilazak elemenata u uređenom redosledu i pronalaženje najmanjeg elementa koji je veći ili jednak datoj vrednosti (metodom lower_bound) ili najmanjeg elementa koji je strogo veći od date vrednosti (metodom upper_bound). Pošto ove metode vrše binarnu pretragu, njihova složenost je takođe \(O(\log{n})\).

Ako dopuštamo da skup sadrži duplikate, možemo koristiti multiset i unordered_multiset, koji su iste efikasnosti kao set i unordered_set.

Ilustrujmo na primeru sortiranja niza kako izbor pogodne strukture podataka čini algoritam efikasnijim. Algoritam sortiranja umetanjem (engl. insertion sort) radi tako što se jedan po jedan element ubacuje na svoje mesto u sortiranom nizu. Kada se koristi niz, umetanje elementa je linearne složenosti (jer se svi elementi iza njega moraju pomeriti za jedno mesto udesno). Ako se umesto niza elementi ubacuju u uređeni skup, isti algoritam radi mnogo efikasnije. Naime, umetanje svakog elementa je složenosti \(O(\log{k})\) (gde je \(k\) broj elemenata uređenog skupa), pa je ukupna složenost umetanja svih \(n\) elemenata složenosti \(O(n\log{n})\). Nakon toga se ispis svih elemenata uređenog multiskupa vrši u linearnom vremenu \(O(n)\).

int n;
cin >> n;
multiset<int> a;
for (int i = 0; i < n; i++) {
   int x;
   cin >> x;
   a.insert(x);
}
for (int x : a)
   cout << x << endl;

Dakle, uz korišćenje pogodne strukture podataka isti algoritam može biti mnogo efikasniji. Ilustrujmo ovo još jednim primerom.

Zadatak: Kupovina računara

U prodavnicu laptop računara često stižu novi modeli i informacija o njihovoj ceni se odmah objavljuje. Skuplji računari uvek imaju bolje performanse. Svaki kupac dolazi čim dođe u prodavnicu, saopštava visinu svog budžeta. Za svakog kupca prodabnica objavljuje koji najbolji računar može da kupi u okviru raspoloživog budžeta i objavljuje da je taj računar prodat.

Opis ulaza

Svaka linija standardnog ulaza počinje karakterom i, e ili f.

Linije koje počinju sa i označavaju da je novi računar stigao u prodavnicu i nakon slova i navedena je njegova cena (prirodan broj manji od \(10^9\)).
Linije koje počinju sa e označavaju da je neki računar prodat i nakon slova e navedena je cena tog računara.
Linije koje počinju sa f označavaju da kupac želi da kupi najskuplji računar trenutno u prodavnici čija je cena manja ili jednaka od iznosa budžeta navedenog nakon slova f.

Opis izlaza

Na standardni izlaz ispisati redom rezultate svih upita koje su organizatori postavili (ako nijedan računr ne može da se kupi za navedeni iznos, ispisati -).

Primer

Ulaz

Izlaz

Rešenje

Gruba sila

Rešenje grubom silom podrazumeva da se cene svih računara u prodavnici čuvaju u nizu. Dodavanje je moguće vršiti na kraj niza, brisanje elementa sa prve pozicije na kojoj se nalazi, dok se pronalazak najboljeg računara koji kupac može da priušti može vršiti jednim prolaskom kroz niz i analizom svih elemenata.

Dodavanje elementa na kraj niza je složenosti \(O(1)\), ali su brisanje i prebrojavanje složensti \(O(n)\), tako da je ukupna složenost \(O(q^2)\), gde je \(q\) broj linija (najgori slučaj može biti kada se prvo učita \(q/2\) linija kojima se elementi unose u niz, a zatim \(q/2\) linija kojima se pretražuju elementi niza).

Uređen skup

Da se vrši samo umetanje i jedno prebrojavanje na kraju, niz bi mogao da se sortira i da se binarnom pretragom pronađe traženi računar. Pošto se u ovom zadatku vrši više prebrojavanja a elementi mogu i da se brišu, u efikasnom rešenju nije moguće koristiti običan niz. Umesto toga, brojave ćemo čuvati u uređenom (multi)skupu koji omogućava efikasno dodavanje, brisanje i binarnu pretragu.

Uređen multiskup je implementiran kroz bibliotečku kolekciju multiset a za njegovu binarnu pretragu koristimo metodu upper_bound (ona vraća iterator na poziciju prve vrednosti koja je strogo veća od date, pa se tražena vrednost nalazi na prethodnoj poziciji). Za brisanje koristimo metodu erase, kojoj moramo da predamo iterator koji ukazuje na element koji želimo da obrišemo (ako navedemo vrednost, biće obrisana sva pojavljivanja te vrednosti). Pretragu vršimo metodom find (koja takođe binarno pretražuje drvo).

Svaka od navedenih operacija sa uređenim multiskupom se vrši u vremenu \(O(\log{n})\), gde je \(n\) trenutni broj elemenata u multiskupu. Ukupno izvršavanje \(q\) upita je \(O(q \log{q})\).

multiset<int> cene;
char c;
while (cin >> c) {
  if (c == 'i') {
    int cena;
    cin >> cena >> ws;
    cene.insert(cena);
  } else if (c == 'e') {
    int cena;
    cin >> cena >> ws;
    auto it = cene.find(cena);
    if (it != a.end())
      cene.erase(it);
  } else if (c == 'f') {
    int budzet;
    cin >> budzet >> ws;
    // pozicija najmanje cene strogo vece od budzeta
    auto it = cene.upper_bound(budzet);
    if (it != cene.begin()) {
      // trazimo prethodnu cenu
      --it;
      cout << *it << '\n';
    } else
      cout << "-" << '\n';
  }
}

#include <iostream>
#include <set>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  multiset<int> cene;
  char c;
  while (cin >> c) {
    if (c == 'i') {
      int cena;
      cin >> cena >> ws;
      cene.insert(cena);
    } else if (c == 'e') {
      int cena;
      cin >> cena >> ws;
      auto it = cene.find(cena);
      if (it != a.end())
        cene.erase(it);
    } else if (c == 'f') {
      int budzet;
      cin >> budzet >> ws;
      // pozicija najmanje cene strogo vece od budzeta
      auto it = cene.upper_bound(budzet);
      if (it != cene.begin()) {
        // trazimo prethodnu cenu
        --it;
        cout << *it << '\n';
      } else
        cout << "-" << '\n';
    }
  }
  return 0;
}

3.8.2 Primena stekova i redova

Stek i red su strukture podataka koje se prirodno javljaju i koriste u mnogim primenama. U ovom poglavlju ćemo prikazati kako se mogu upotrebiti i da se snizi složenost nekih algoritama.

Zadatak: Brisanje parova uzastopnih jednakih karaktera

Niska se skraćuje dokle god je to moguće tako što joj se briše prvi par jednakih uzastopnih karaktera. Napiši program koji određuje skraćenu nisku.

Opis ulaza

Sa standardnog ulaza se učitava niska sastavljena od malih slova engleske abecede, dužine \(n\) (\(1 \leq n \leq 10^6\)).

Opis izlaza

Na standardni izlaz ispisati skraćenu nisku.

Primer

Ulaz

babccbddabbcaa

Izlaz

bc

Objašnjenje

Skraćivanje teče sledećim redosledom babccbddabbcaa, babbddabbcaa, baddabbcaa, baabbcaa, bbbcaa, bcaa, bc.

Rešenje

Brisanje karaktera sa početka ili iz sredine niske zahteva pomeranje ostalih karaktera, što dovodi do neefikasnog programa. Umesto toga, moguće je kreirati novu nisku obrađujući jedan po jedan karakter polazne niske (primetimo da ulazna niska ne mora da se čuva - mogu se u hodu obrađivati njeni elementi, redom kako se čitaju sa ulaza). Pretpostavićemo da smo obradili prvih \(k\) karaktera niske i da smo brisanjem svih pojavljivanja uzastopnih jednakih karaktera dobili nisku \(t\).

Ako je niska \(t\) prazna ili ako je poslednji karakter niske \(t\) različit od tekućeg karaktera \(s_k\) niske \(s\) (onog na poziciji \(k\)), karakter \(s_k\) treba dodati na \(t\),
U suprotnom (ako je poslednji karakter niske \(t\) jednak karakteru \(s_k\)) treba ukloniti poslednji karakter niske \(t\) i time (u oba slučaja) dobijamo rezultat obrade prvih \(k+1\) karaktera niske \(s\).

Primetimo da se niska \(t\) ponaša kao stek (karakteri joj se dodaju i uklanjaju sa desnog kraja). Tip string u jeziku C++ podržava metode empty, back, push_back i pop_back koji se izvršavaju u složenosti \(O(1)\), pa se taj tip može koristiti kao stek karaktera.

Pošto su sve operacije za rad sa stekom složenosti \(O(1)\) i svaki karakter se najviše jednom može dodati i jednom može ukloniti sa steka, složenost ovog algoritma je \(O(n)\). I memorijska složenost je takođe \(O(n)\).

char c;
string t;
while (cin >> c && c != '\n')
  if (t.empty() || c != t.back())
    t.push_back(c);
  else
    t.pop_back();
cout << t << endl;

#include <iostream>
#include <stack>

using namespace std;

int main() {
  char c;
  string t;
  while (cin >> c && c != '\n')
    if (t.empty() || c != t.back())
      t.push_back(c);
    else
      t.pop_back();
  cout << t << endl;
  return 0;
}

Zadatak: Maksimalna bijekcija

Filmski producent organizuje večeru na koju želi da pozove glumce. Da bi se glumci osećali prijatno na večeri, producent želi da obezbedi da je svaki glumac prisutan na večeri omiljen glumac nekog drugog glumca prisutnog na večeri. Svaki od \(n\) glumaca, potencijalnih gostiju, odabrao je svog omiljenog glumca iz tog skupa glumaca (pri čemu nije isključeno i da je neki glumac odabrao sam sebe). Napiši program koji određuje najveći podskup tog skupa glumaca koji sadrži glumce koje producent može pozvati na večeru.

Opis ulaza

Sa standardnog ulaza unosi se broj \(n\) (\(1 \leq n \leq 50000\)) koji predstavlja broj glumaca koji su glasali, a zatim i redom redni brojevi omiljenog glumca svakog glumca (svi brojevi su između \(0\) i \(n-1\)).

Opis izlaza

Na standardni izlaz ispiši najveći broj glumaca koji mogu prisustvovati večeri.

Primer

Ulaz

7
2 0 0 4 4 3 5

Izlaz

Objašnjenje

Na večeru mogu biti pozvani glumci sa brojevima \(0, 2, 4\). Glumac \(0\) je omiljeni glumac glumca \(2\), glumac \(2\) je omiljeni glumac glumca \(0\), dok je glumac \(4\) sam sebi omiljen.

Rešenje

Glasovi glumaca određuju funkciju \(f\) definisanu na skupu \(\{0, 1, \ldots, n-1\}\). Neka je skup \(S\) skup glumaca koji su pozvani na večeru. Da bi svaki glumac bio omiljen glumac nekom drugom glumcu iz skupa \(S\), potrebno je da restrikcija funkcije \(f\) na skup \(S\) bude “na” (tj. da za svaku sliku postoji original koji se slika u tu sliku). Pošto je skup \(S\) konačan, na osnovu Dirihleovog principa, ona će ujedno biti i “1-1” tj. bijekcija (za svaku sliku će postojati tačno jedan original koji se u nju slika). Zaista, ako bi neki glumac na večeri bio omiljen za dva različita glumca, nekom glumcu na večeri bi nedostajao glumac kome bi on bio omiljen.

Direktan, ali veoma neefikasan način da se ovaj zadatak reši je da se nabroje svi mogući podskupovi i da se za svaki od njih proveri da li je restrikcija \(f\) na taj podskup bijekcija.

Eliminacija elemenata

Efikasan algoritam možemo napraviti ako pronađemo potreban uslov da element bude deo skupa \(S\). Naime, svaki element skupa \(S\) mora biti slika tačno jednog elementa skupa \(S\). Ako je svaki element skupa \(X\) (domena funkcije \(f\)) slika tačno jednog elementa skupa \(X\), tada je \(f\) bijekcija na skupu \(X\). U suprotnom mora da postoji element koji nije slika ni jednog elementa skupa \(X\) i taj element ne može biti deo skupa \(S\). Kada taj element uklonimo (zajedno sa njegovom slikom), dobijamo skup koji je za jedan element manji i na koji možemo primeniti isti postupak (suštinski, imamo opisan induktivni tj. rekurzivni postupak).

Ovaj pristup se može jednostavno implementirati tako što za svaki element skupa \(X\) izračunamo broj elemenata koji se slikaju u njega. To možemo uraditi korišćenjem jednostavnog, asocijativnog niza.

Možemo održavati radnu listu (red) elemenata u koje se ne slika ni jedan element (nakon izračunavanja broja elemenata koji se slikaju u svaki od elemenata skupa \(X\), sve brojeve za koje je vrednost u asocijativnom nizu nula, ubacujemo u radnu listu). Nakon toga, sve dok se radna lista ne isprazni, uzimamo jedan po jedan element iz radne liste, izbacujemo ga iz skupa \(X\) i zato smanjujemo broj elemenata koji se slikaju u sliku tog izbačenog elementa (umanjujemo vrednost u asocijativnom nizu). Ako se ustanovi da se nakon toga vrednost slike u asocijativnom nizu smanjila na nulu, tada se slika ubacuje u radnu listu. Iako redosled uzimanja elemenata iz radne liste može biti potpuno proizvoljan, za implementaciju se najčešće koristi red (jer daje nekakav osećaj pravičnosti). Rešenje u kom bi se umesto reda koristio stek bilo bi takođe ispravno.

// izračunavamo ulazni stepen svakog elementa
vector<int> ulazniStepen(n, 0);
for (int i = 0; i < n; i++)
  ulazniStepen[f[i]]++;
// red u kom se čuvaju elementi ulaznog stepena 0
// oni ne mogu biti deo domena bijekcije
queue<int> q;
for (int i = 0; i < n; i++)
  if (ulazniStepen[i] == 0)
    q.push(i);
// izbacujemo jedan po jedan element iz reda
int broj_elemenata = n;
while (!q.empty()) {
  int i = q.front(); q.pop();
  broj_elemenata--;
  // uklanjamo sliku tog elementa i ako nakon toga
  // slika dobije ulazni stepen nula ubacujemo je u red
  if (--ulazniStepen[f[i]] == 0)
    q.push(f[i]);
}
cout << broj_elemenata << endl;

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> f(n);
  for (int i = 0; i < n; i++)
    cin >> f[i];
  // izračunavamo ulazni stepen svakog elementa
  vector<int> ulazniStepen(n, 0);
  for (int i = 0; i < n; i++)
    ulazniStepen[f[i]]++;
  // red u kom se čuvaju elementi ulaznog stepena 0
  // oni ne mogu biti deo domena bijekcije
  queue<int> q;
  for (int i = 0; i < n; i++)
    if (ulazniStepen[i] == 0)
      q.push(i);
  // izbacujemo jedan po jedan element iz reda
  int broj_elemenata = n;
  while (!q.empty()) {
    int i = q.front(); q.pop();
    broj_elemenata--;
    // uklanjamo sliku tog elementa i ako nakon toga
    // slika dobije ulazni stepen nula ubacujemo je u red
    if (--ulazniStepen[f[i]] == 0)
      q.push(f[i]);
  }
  cout << broj_elemenata << endl;
  return 0;
}

3.8.3 Primena redova sa prioritetom

Red sa prioritetom je vrsta reda u kome elementi imaju na neki način pridružen prioritet, dodaju se u red jedan po jedan, a uvek se iz reda uklanja onaj element koji ima najveći prioritet od svih elemenata u redu. Podsetimo se, u jeziku C++ red sa prioritetom se realizuje klasom priority_queue<T>, gde je T tip elemenata u redu. Red sa prioritetom podržava sledeće metode:

push - dodaje dati element u red
pop - uklanja element sa najvećim prioritetom iz reda (pod pretpostavkom da red nije prazan). Naglasimo da je ova metoda tipa void i da ne vraća uklonjeni element.
top - očitava element sa najvećim prioritetom (pod pretpostavkom da red nije prazan)
empty - proverava da li je red prazan
size - vraća broj elemenata u redu

Operacije push i pop su složenosti \(O(\log{k})\), gde je \(k\) broj elemenata u redu, dok su ostale operacije složenosti \(O(1)\).

Ilustrujmo kako se korišćenjem redova sa prioritetom može poboljšati složenost algoritama sortiranja. Koristi se algoritam sortiranja uz pomoć hipa (engl. heap sort) koji je varijacija algoritma sortiranja selekcijom (engl. selection sort) u kojem se, podsetimo se, u svakom koraku najmanji element dovodi na početak niza. Hip je struktura podataka koja se najčešće koristi za implementaciju reda sa prioritetom. Algoritam hip sort koristi činjenicu da je određivanje i uklanjanje najmanjeg elementa iz reda sa prioritetom prilično efikasna operacija. Stoga se sortiranje može realizovati tako što se svi elementi umetnu u red sa prioritetom (implementiran pomoću strukture hip), iz koga se zatim pronalazi i uklanja jedan po jedan najmanji element.

I ubacivanje elemenata u red sa prioritetom i izbacivanje elemenata iz reda sa prioritetom obično je složenosti \(O(\log{k})\), gde je \(k\) broj elemenata u redu sa prioritetom. Stoga je ukupna složenost ovog algoritma sortiranja \(O(n \log{n})\).

// ovo je način da se u C++-u definiše red sa prioritetom u 
// kome su elementi poređani u opadajućem redosledu prioriteta
// (ovde, vrednosti)
priority_queue<int, vector<int>, greater<int>> Q;

// učitavamo sve elemente niza i ubacujemo ih u red
int n;
cin >> n;
for (int i = 0; i < n; i++) {
  int ai;
  cin >> ai;
  Q.push(ai);
}
// vadimo jedan po jedan element iz reda i ispisujemo ga
while (!Q.empty()) {
  cout << Q.top() << endl;
  Q.pop();
}

Zadatak: Zbir k najboljih

Student je radio \(n\) zadataka i za svaki zadatak je dobio određeni broj poena. Odrediti zbir poena na \(k\) zadataka koje je najbolje uradio.

Opis ulaza

U prvoj liniji standardnog ulaza dat je prirodan broj \(n\) (\(1\le n \le 10^6\)) – broj zadataka koje je učenik radio, u drugoj prirodan broj \(k\) (\(1\le k \le n\)) – broj zadataka koje je najbolje uradio, a u trećoj \(n\) brojeva broj poena koje je dobio na zadacima.

Opis izlaza

Ukupan broj poena koje je osvojio na \(k\) najbolje ocenjenih zadataka.

Primer

Ulaz

10
3 
15 80 25 60 10 20 50 45 40 30

Izlaz

Rešenje

Red sa prioritetom

Najvećih \(k\) do sada viđenih elemenata niza možemo čuvati u strukturi podataka koja nam omogućava da pronađemo najmanji element u njoj i da ga eventualno zamenimo onim koji je trenutno učitan (ako je trenutno učitani element veći od njega). Idealna struktura za to je hip tj. red sa prioritetom.

Red sa prioritetom u jeziku C++ možemo dobiti pomoću priority_queue. Elemente u red možemo ubaciti metodom push. Element koji je najmanji možemo očitati metodom top i izbaciti metodom pop.

Na početku red popunjavamo sa \(k\) prvih učitanih elemenata, a zatim svaki naredni učitani element poredimo sa najmanjim u redu i ako je veći od njega, najmanji izbacujemo, a učitani element ubacujemo.

Pošto je složenost metoda za ubacivanje i izbacivanje iz reda sa prioritetom logaritamska, a metode za očitavanje najmanjeg elementa konstantna, vremenska složenost ovog algoritma je \(O(n \cdot \log(k))\), dok je prostorna složenost \(O(k)\).

Primetimo da je ovaj algoritam donekle sličan algoritmu sortiranja uz pomoć hipa tj. algoritma Hip-sort (HeapSort).

int n, k;
cin >> n >> k;

// red sa prioritetom koji cuva k najvecih elemenata koristi
// se min-hip, koji omogucava brzo uklanjanje najmanjeg
// elementa
priority_queue<int, vector<int>, greater<int>> pq;

// ucitavamo prvih k elemenata i ubacujemo ih u red
for (int i = 0; i < k; i++) {
  int x;
  cin >> x;
  pq.push(x);
}

// ucitavamo preostale elemente
for (int i = k; i < n; i++) {
  int x;
  cin >> x;
  // ako je ucitani element veci od najmanjeg trenutno u
  // redu izbacujemo taj najmanji i menjamo ga ucitanim
  if (x > pq.top()) {
    pq.pop();
    pq.push(x);
  }
}

// izbacujemo elemente iz reda racunajuci njihov zbir i
// ispisujemo ga
int s = 0;
while (!pq.empty()) {
  s += pq.top();
  pq.pop();
}
cout << s << endl;

#include <iostream>
#include <queue>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  
  int n, k;
  cin >> n >> k;

  // red sa prioritetom koji cuva k najvecih elemenata koristi
  // se min-hip, koji omogucava brzo uklanjanje najmanjeg
  // elementa
  priority_queue<int, vector<int>, greater<int>> pq;

  // ucitavamo prvih k elemenata i ubacujemo ih u red
  for (int i = 0; i < k; i++) {
    int x;
    cin >> x;
    pq.push(x);
  }

  // ucitavamo preostale elemente
  for (int i = k; i < n; i++) {
    int x;
    cin >> x;
    // ako je ucitani element veci od najmanjeg trenutno u
    // redu izbacujemo taj najmanji i menjamo ga ucitanim
    if (x > pq.top()) {
      pq.pop();
      pq.push(x);
    }
  }

  // izbacujemo elemente iz reda racunajuci njihov zbir i
  // ispisujemo ga
  int s = 0;
  while (!pq.empty()) {
    s += pq.top();
    pq.pop();
  }
  cout << s << endl;

  return 0;
}