Примена ефикасних структура података

3.8 Примена ефикасних структура података

Избор структуре података може у великој мери утицати на ефикасност. У наставку ћемо приказати неколико примера који ово илуструју.

3.8.1 Примена скупова и мапа

Већина савремених програмских језика нуди готове типове података који имплементирају скупове и мапе. У језику C++ су то set и map који омогућавају основне операције (уметање, претрага, брисање) у сложености \(O(\log{n})\), где је \(n\) број елемената скупа тј. кључева у мапи и unordered_set и unordered_map чија је амортизована сложенот основних операција \(O(1)\), али је слoженост најгорег случаја \(O(n)\). Иако имају мало лошију просечну сложеност операција, уређени скупови нуде неке додатне операције – проналажење најмањег или највећег елемената (помоћу begin и end), обилазак елемената у уређеном редоследу и проналажење најмањег елемента који је већи или једнак датој вредности (методом lower_bound) или најмањег елемента који је строго већи од дате вредности (методом upper_bound). Пошто ове методе врше бинарну претрагу, њихова сложеност је такође \(O(\log{n})\).

Ако допуштамо да скуп садржи дупликате, можемо користити multiset и unordered_multiset, који су исте ефикасности као set и unordered_set.

Илуструјмо на примеру сортирања низа како избор погодне структуре података чини алгоритам ефикаснијим. Алгоритам сортирања уметањем (енгл. insertion sort) ради тако што се један по један елемент убацује на своје место у сортираном низу. Када се користи низ, уметање елемента је линеарне сложености (јер се сви елементи иза њега морају померити за једно место удесно). Ако се уместо низа елементи убацују у уређени скуп, исти алгоритам ради много ефикасније. Наиме, уметање сваког елемента је сложеност \(О(\log{k})\), па је укупна сложеност уметања свих \(n\) елемената сложености \(О(n\log{n})\). Након тога се испис свих елемената уређеног мултискупа врши у линеарном времену \(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;

Дакле, уз коришћење погодне структуре података исти алгоритам може бити много ефикаснији. Илуструјмо ово још једним примером.

Задатак: Куповина рачунара

У продавници лаптоп рачунара се често појављују нови модели, док се стари модели распродају. Позната је цена сваког рачунара. Купци долазе са жељом да купе рачунаре који су у оквиру њиховог буџета. Продавница ради веома поштено, тако да скупљи рачунари увек имају и боље перформансе. Зато сваки корисник жели да купи што скупљи рачунар који може да приушти.

Опис улаза

Свака линија стандардног улаза почиње карактером i, e или f.

Линије које почињу са i означавају да је нови рачунар стигао у продавницу и након слова i наведена је његова цена (природан број мањи од \(10^9\)).
Линије које почињу са e означавају да је неки рачунар продат и након слова e наведена је цена тог рачунара.
Линије које почињу са f означавају да купац жели да купи најскупљи рачунар тренутно у продавници чија је цена мања или једнака од износа буџета наведеног након слова f.

Опис излаза

На стандардни излаз исписати редом резултате свих упита које су организатори поставили (ако ниједан рачунр не може да се купи за наведени износ, исписати -).

Пример

Улаз

Излаз

Решење

Груба сила

Решење грубом силом подразумева да се цене свих рачунара у продавници чувају у низу. Додавање је могуће вршити на крај низа, брисање елемента са прве позиције на којој се налази, док се проналазак најбољег рачунара који купац може да приушти може вршити једним проласком кроз низ и анализом свих елемената.

Додавање елемента на крај низа је сложености \(O(1)\), али су брисање и пребројавање сложенсти \(O(n)\), тако да је укупна сложеност \(O(q^2)\), где је \(q\) број линија (најгори случај може бити када се прво учита \(q/2\) линија којима се елементи уносе у низ, а затим \(q/2\) линија којима се претражују елементи низа).

Уређен скуп

Да се врши само уметање и једно пребројавање на крају, низ би могао да се сортира и да се бинарном претрагом пронађе тражени рачунар. Пошто се у овом задатку врши више пребројавања а елементи могу и да се бришу, у ефикасном решењу није могуће користити обичан низ. Уместо тога, бројаве ћемо чувати у уређеном (мулти)скупу који омогућава ефикасно додавање, брисање и бинарну претрагу.

Уређен мултискуп је имплементиран кроз библиотечку колекцију multiset а за његову бинарну претрагу користимо методу upper_bound (она враћа итератор на позицију прве вредности која је строго већа од дате, па се тражена вредност налази на претходној позицији). За брисање користимо методу erase, којој морамо да предамо итератор који указује на елемент који желимо да обришемо (ако наведемо вредност, биће обрисана сва појављивања те вредности). Претрагу вршимо методом find (која такође бинарно претражује дрво).

Свака од наведених операција са уређеним мултискупом се врши у времену \(O(\log{n})\), где је \(n\) тренутни број елемената у мултискупу. Укупно извршавање \(q\) упита је \(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 Примена стекова и редова

Стек и ред су структуре података које се природно јављају и користе у многим применама. У овом поглављу ћемо приказати како се могу употребити и да се снизи сложеност неких алгоритама.

Задатак: Брисање парова узастопних једнаких карактера

Ниска се скраћује докле год је то могуће тако што јој се брише први пар једнаких узастопних карактера. Напиши програм који одређује скраћену ниску.

Опис улаза

Са стандардног улаза се учитава ниска састављена од малих слова енглеске абецеде, дужине \(n\) (\(1 \leq n \leq 10^6\)).

Опис излаза

На стандардни излаз исписати скраћену ниску.

Пример

Улаз

babccbddabbcaa

Излаз

bc

Објашњење

Скраћивање тече следећим редоследом babccbddabbcaa, babbddabbcaa, baddabbcaa, baabbcaa, bbbcaa, bcaa, bc.

Решење

Брисање карактера са почетка или из средине ниске захтева померање осталих карактера, што доводи до неефикасног програма. Уместо тога, могуће је креирати нову ниску обрађујући један по један карактер полазне ниске. Претпоставићемо да смо обрадили првих \(k\) карактера ниске и да смо брисањем свих појављивања узастопних једнаких карактера добили ниску \(t\).

Ако је ниска \(t\) празна или ако је последњи карактер ниске \(t\) различит од текућег карактера \(s_k\) ниске \(s\) (оног на позицији \(k\)), карактер \(s_k\) треба додати на \(t\),
У супротном (ако је последњи карактер ниске \(t\) једнак карактеру \(s_k\)) треба уклонити последњи карактер ниске \(t\) и тиме (у оба случаја) добијамо резултат обраде првих \(k+1\) карактера ниске \(s\).

Приметимо да се ниска \(t\) понаша као стек (карактери јој се додају и уклањају са десног краја). Тип string у језику C++ подржава методе empty, back, push_back и pop_back који се извршавају у сложености \(O(1)\), па се тај тип може користити као стек карактера.

Пошто су све операције за рад са стеком сложености \(O(1)\) и сваки карактер се највише једном може додати и једном може уклонити са стека, сложеност овог алгоритма је \(O(n)\). И меморијска сложеност је такође \(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;
}

Задатак: Максимална бијекција

Филмски продуцент организује вечеру на коју жели да позове глумце. Да би се глумци осећали пријатно на вечери, продуцент жели да обезбеди да је сваки глумац присутан на вечери омиљен глумац неког другог глумца присутног на вечери. Сваки од \(n\) глумаца, потенцијалних гостију, одабрао је свог омиљеног глумца из тог скупа глумаца (при чему није искључено и да је неки глумац одабрао сам себе). Напиши програм који одређује највећи подскуп тог скупа глумаца који садржи глумце које продуцент може позвати на вечеру.

Опис улаза

Са стандардног улаза уноси се број \(n\) (\(1 \leq n \leq 50000\)) који представља број глумаца који су гласали, а затим и редом редни бројеви омиљеног глумца сваког глумца (сви бројеви су између \(0\) и \(n-1\)).

Опис излаза

На стандардни излаз испиши највећи број глумаца који могу присуствовати вечери.

Пример

Улаз

7
2 0 0 4 4 3 5

Излаз

Објашњење

На вечеру могу бити позвани глумци са бројевима \(0, 2, 4\). Глумац \(0\) је омиљени глумац глумца \(2\), глумац \(2\) је омиљени глумац глумца \(0\), док је глумац \(4\) сам себи омиљен.

Решење

Гласови глумаца одређују функцију \(f\) дефинисану на скупу \(\{0, 1, \ldots, n-1\}\). Нека је скуп \(S\) скуп глумаца који су позвани на вечеру. Да би сваки глумац био омиљен глумац неком другом глумцу из скупа \(S\), потребно је да рестрикција функције \(f\) на скуп \(S\) буде “на” (тј. да за сваку слику постоји оригинал који се слика у ту слику). Пошто је скуп \(S\) коначан, на основу Дирихлеовог принципа, она ће уједно бити и “1-1” тј. бијекција (за сваку слику ће постојати тачно један оригинал који се у њу слика). Заиста, ако би неки глумац на вечери био омиљен за два различита глумца, неком глумцу на вечери би недостајао глумац коме би он био омиљен.

Директан, али веома неефикасан начин да се овај задатак реши је да се наброје сви могући подскупови и да се за сваки од њих провери да ли је рестрикција \(f\) на тај подскуп бијекција.

Елиминација елемената

Ефикасан алгоритам можемо направити ако пронађемо потребан услов да елемент буде део скупа \(S\). Наиме, сваки елемент скупа \(S\) мора бити слика тачно једног елемента скупа \(S\). Ако је сваки елемент скупа \(X\) (домена функције \(f\)) слика тачно једног елемента скупа \(X\), тада је \(f\) бијекција на скупу \(X\). У супротном мора да постоји елемент који није слика ни једног елемента скупа \(X\) и тај елемент не може бити део скупа \(S\). Када тај елемент уклонимо (заједно са његовом сликом), добијамо скуп који је за један елемент мањи и на који можемо применити исти поступак (суштински, имамо описан индуктивни тј. рекурзивни поступак).

Овај приступ се може једноставно имплементирати тако што за сваки елемент скупа \(X\) израчунамо број елемената који се сликају у њега. То можемо урадити коришћењем једноставног, асоцијативног низа.

Можемо одржавати радну листу (ред) елемената у које се не слика ни један елемент (након израчунавања броја елемената који се сликају у сваки од елемената скупа \(X\), све бројеве за које је вредност у асоцијативном низу нула, убацујемо у радну листу). Након тога, све док се радна листа не испразни, узимамо један по један елемент из радне листе, избацујемо га из скупа \(X\) и зато смањујемо број елемената који се сликају у слику тог избаченог елемента (умањујемо вредност у асоцијативном низу). Ако се установи да се након тога вредност слике у асоцијативном низу смањила на нулу, тада се слика убацује у радну листу. Иако редослед узимања елемената из радне листе може бити потпуно произвољан, за имплементацију се најчешће користи ред (јер даје некакав осећај правичности). Решење у ком би се уместо реда користио стек било би такође исправно.

// 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 Примена редова са приоритетом

Ред са приоритетом је врста реда у коме елементи имају на неки начин придружен приоритет, додају се у ред један по један, а увек се из реда уклања онај елемент који има највећи приоритет од свих елемената у реду. Подсетимо се, у језику C++ ред са приоритетом се реализује класом priority_queue<Т>, где је Т тип елемената у реду. Ред са приоритетом подржава следеће методе:

push - додаје дати елемент у ред
pop - уклања елемент са највећим приоритетом из реда (под претпоставком да ред није празан). Нагласимо да је ова метода типа void и да не враћа уклоњени елемент.
top - очитава елемент са највећим приоритетом (под претпоставком да ред није празан)
empty - проверава да ли је ред празан
size - враћа број елемената у реду

Операције push и pop су сложености \(O(\log{k})\), где је \(k\) број елемената у реду, док су остале операције сложености \(O(1)\).

Илуструјмо како се коришћењем редова са приоритетом може побољшати сложеност алгоритама сортирања. Користи се алгоритам сортирања уз помоћ хипа (енгл. heap sort) који је варијација алгоритма сортирања селекцијом (енгл. selection sort) у којем се, подсетимо се, у сваком кораку најмањи елемент доводи на почетак низа. Хип је структура података која се најчешће користи за имплементацију реда са приоритетом. Алгоритам хип сорт користи чињеницу да је одређивање и уклањање најмањег елемента из реда са приоритетом прилично ефикасна операција. Стога се сортирање може реализовати тако што се сви елементи уметну у ред са приоритетом (имплементиран помоћу структуре хип), из кога се затим проналази и уклања један по један најмањи елемент.

И убацивање елемената у ред са приоритетом и избацивање елемената из реда са приоритетом обично је сложености \(O(\log{k})\), где је \(k\) број елемената у реду са приоритетом. Стога је укупна сложеност овог алгоритма сортирања \(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();
}

Задатак: Збир k најбољих

Студент је радио \(n\) задатaкa и за сваки задатак je добио одређени број поена. Одредити збир поена на \(k\) задатака које је најбоље урадио.

Опис улаза

У првој линији стандардног улаза дат је природан број \(n\) (\(1\le n \le 10^6\)) – број задатака које је ученик радио, у другој природан број \(k\) (\(1\le k \le n\)) – број задатака које је најбоље урадио, а у трећој \(n\) бројева број поена које је добио на задацима.

Опис излаза

Укупан број поена које је освојио на \(k\) најбоље оцењених задатака.

Пример

Улаз

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

Излаз

Решење

Ред са приоритетом

Највећих \(k\) до сада виђених елемената низа можемо чувати у структури података која нам омогућава да пронађемо најмањи елемент у њој и да га евентуално заменимо оним који је тренутно учитан (ако је тренутно учитани елемент већи од њега). Идеална структура за то је хип тј. ред са приоритетом.

Ред са приоритетом у језику C++ можемо добити помоћу priority_queue. Елементе у ред можемо убацити методом push. Елемент који је најмањи можемо очитати методом top и избацити методом pop.

На почетку ред попуњавамо са \(k\) првих учитаних елемената, а затим сваки наредни учитани елемент поредимо са најмањим у реду и ако је већи од њега, најмањи избацујемо, а учитани елемент убацујемо.

Пошто је сложеност метода за убацивање и избацивање из реда са приоритетом логаритамска, а методе за очитавање најмањег елемента константна, временска сложеност овог алгоритма је \(O(n \cdot \log(k))\), док је просторна сложеност \(O(k)\).

Приметимо да је овај алгоритам донекле сличан алгоритму сортирања уз помоћ хипа тј. алгоритма Хип-сорт (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;
}