11. Lisää tietorakenteita

Tässä luvussa tutustumme kahteen tietorakenteeseen:

• Pakka (deque): Pakka on listarakenne, jossa alkioiden lisäykset ja poistot ovat tehokkaita sekä listan alussa että lopussa.
• Keko (heap): Keko on puurakenne, jossa pystyy lisäämään tehokkaasti alkioita sekä etsimään ja poistamaan pienimmän tai suurimman alkion.

Molemmat tietorakenteet ovat saatavilla Pythonin standardikirjastossa, minkä ansiosta niitä voi käyttää kätevästi Python-ohjelmoinnissa.

Pakka

Pythonin tavallisessa listassa on tehokasta lisätä alkio listan loppuun metodilla append sekä poistaa alkio listan lopusta metodilla pop. Kuitenkaan ei ole tehokasta tapaa lisätä tai poistaa alkiota listan alussa.

Pakka (deque) on listarakenne, jossa lisäykset ja poistot ovat tehokkaita sekä listan alussa että lopussa. Pythonissa pakka on saatavilla moduulissa collections tietorakenteena deque, joka tarjoaa seuraavat metodit:

• append: lisää alkio listan loppuun
• pop: poista alkio listan lopusta
• appendleft: lisää alkio listan alkuun
• popleft: poista alkio listan alusta

Tuttujen metodien append ja pop lisäksi pakassa on siis myös metodit appendleft ja popleft, joilla voi lisätä ja poistaa alkion listan alussa. Kaikkien näiden metodien aikavaativuus on \(O(1)\).

Seuraava koodi esittelee pakan käyttämistä:

import collections

items = collections.deque()

items.append(1)
items.append(2)
items.appendleft(3)
items.append(4)
items.appendleft(5)

print(items) # deque([5, 3, 1, 2, 4])

print(items[0]) # 5
print(items[1]) # 3
print(items[-1]) # 4

Pakkaa voi indeksoida samaan tapaan kuin tavallista listaa. Pakan heikkoutena on kuitenkin, että alkion käsittely indeksin perusteella on hidasta. Tavallisessa listassa missä tahansa indeksissä olevaan alkioon pääsee käsiksi ajassa \(O(1)\), mutta pakassa listan keskellä olevan alkion käsittely vie aikaa \(O(n)\).

Pakan toteutus

Pakka on toteutettu Pythonissa linkitettynä listana (linked list), mikä tarkoittaa, että pakassa olevissa alkioissa on muistissa viittaus listan edelliseen ja seuraavaan alkioon. Toisin kuin tavallisessa listassa, alkioiden ei tarvitse olla peräkkäin muistissa.

Tarkastellaan esimerkkinä listan \([1,2,3]\) tallentamista tavallisena listana ja linkitettynä listana. Tavallisena listana tilanne voi näyttää tältä:

Tässä listan alkiot on tallennettu muistiin alkaen kohdasta 100. Alkiot ovat peräkkäin muistissa ja lisäykset ja poistot ovat tehokkaita vain listan lopussa.

Linkitettynä listanne tilanne voi puolestaan näyttää seuraavalta:

Tässä listan alkiot ovat kohdissa 100, 106 ja 103. Jokaisessa kohdassa on kolme tietoa: alkion sisältö, viittaus edelliseen alkioon ja viittaus seuraavaan alkioon. Esimerkiksi kohdassa 106 on arvot 2, 100, 103, koska alkion sisältö on 2, edellinen alkio on kohdassa 100 ja seuraava alkio on kohdassa 103. Viittaus 0 tarkoittaa, että alkiolla ei ole edellistä tai seuraavaa alkiota.

Linkitetyn listan etuna on, että alkioita voi lisätä ja poistaa joustavasti, koska alkiot voivat olla missä tahansa kohdissa muistissa. Esimerkiksi jos yllä olevassa tilanteessa listan alkuun halutaan lisätä uusi alkio, se voidaan lisätä muistiin kohtaan 109:

Tämä vastaa listaa \([4,1,3,2]\), jonka aloituskohta muistissa on 109.

Linkitetyn listan heikkoutena on, että ei ole tehokasta tapaa laskea, missä kohdassa muistia mikäkin alkio sijaitsee. Jos halutaan päästä käsiksi tietyssä kohdassa olevaan alkioon, täytyy seurata viittauksia listan alusta tai lopusta. Tämän vuoksi indeksointi vie aikaa \(O(n)\), jos alkio sijaitsee listan keskellä.

Pino ja jono

Pino (stack) on tietorakenne, jossa pystyy lisäämään alkion listan loppuun sekä hakemaan tai poistamaan alkion listan lopusta. Jono (queue) on puolestaan tietorakenne, jossa pystyy lisäämään alkion listan loppuun sekä hakemaan tai poistamaan alkion listan alusta.

Pakan avulla pystyy toteuttamaan tehokkaasti sekä pinon että jonon, koska alkioita voi käsitellä tehokkaasti sekä listan alussa että lopussa. Seuraavat luokat Stack ja Queue toteuttavat pinon ja jonon:

import collections

class Stack:
    def __init__(self):
        self.stack = collections.deque()

    def push(self, x):
        self.stack.append(x)

    def top(self):
        return self.stack[-1]

    def pop(self):
        self.stack.pop()

class Queue:
    def __init__(self):
        self.queue = collections.deque()

    def push(self, x):
        self.queue.append(x)

    def top(self):
        return self.queue[0]

    def pop(self):
        self.queue.popleft()

Huomaa, että pinon voi toteuttaa helposti myös Pythonin tavallisen listan avulla, kuten teimme luvussa 6. Sen sijaan jonon toteutuksessa on aitoa hyötyä siitä, että pakkaa pystyy käsittelemään tehokkaasti sekä alussa että lopussa.

Keko

Keko (heap) on tietorakenne, jossa voi lisätä, hakea ja poistaa alkioita. Keko on toteutuksesta riippuen joko minimikeko (min heap) tai maksimikeko (max heap). Minimikeossa voi hakea ja poistaa pienimmän alkion, kun taas maksimikeossa voi hakea ja poistaa suurimman alkion.

Pythonissa moduuli heapq sisältää funktioita, joiden avulla listaa voi käsitellä minimikekona:

• heappush: lisää kekoon uusi alkio
• heappop: poista ja palauta keon pienin alkio

Molemmat funktiot toimivat ajassa \(O(\log n)\). Lisäksi listan ensimmäinen alkio on aina keon pienin alkio, joten sen pystyy hakemaan ajassa \(O(1)\).

Seuraava koodi esittelee keon käyttämistä Pythonissa:

import heapq

items = []

heapq.heappush(items, 4)
heapq.heappush(items, 2)
heapq.heappush(items, 3)
heapq.heappush(items, 1)
heapq.heappush(items, 5)

print(items[0]) # 1
heapq.heappop(items)
print(items[0]) # 2

Verrattuna hajautukseen keon etuna on, että siitä pystyy hakemaan ja poistamaan pienimmän tai suurimman alkion tehokkaasti. Hajautuksessa tämä ei ole mahdollista, koska alkioita ei ole järjestetty. Toisaalta keon heikkoutena on, että ei ole mahdollista etsiä kehosta tehokkaasti muita kuin pienin tai suurin alkio.

Huomaa, että sama alkio voi esiintyä keossa monta kertaa. Esimerkiksi seuraava koodi lisää kekoon kolmesti luvun \(1\):

import heapq

items = []
heapq.heappush(items, 1)
heapq.heappush(items, 1)
heapq.heappush(items, 1)

print(items) # [1, 1, 1]

Keon toteutus

Keko perustuu binääripuuhun (binary tree), jossa jokaisella solmulla voi olla vasen ja oikea lapsi. Keko on täytetty niin, että alkiot ovat mahdollisimman ylhäällä puussa ja viimeisellä tasolla mahdollisimman vasemmalla.

Minimikeossa jokaisen solmun alkio on yhtä suuri tai suurempi kuin solmun vanhemman alkio. Maksimikeossa puolestaan jokaisen solmun alkio on yhtä suuri tai pienempi kuin solmun vanhemman alkio. Tämän ansiosta minimikeon juurena on pienin alkio ja maksimikeon juurena on suurin alkio.

Esimerkiksi seuraava minimikeko sisältää alkiot \([1,3,4,5,5,5,7,8,8,9]\):

Keon sisältö voidaan esittää listana, joka sisältää keon alkiot taso kerrallaan ylhäältä alas. Esimerkiksi yllä olevaa kekoa vastaa lista \([1,3,5,4,5,8,9,7,8,5]\). Kun alkio on listassa kohdassa \(k\), sen vasen lapsi on kohdassa \(2k+1\), oikea lapsi on kohdassa \(2k+2\) ja vanhempi on kohdassa \(\lfloor (k-1)/2 \rfloor\). Esimerkiksi alkio \(3\) on kohdassa \(1\), sen lapset ovat kohdissa \(3\) ja \(4\) ja sen vanhempi on kohdassa \(0\).

Alkion lisääminen kekoon

Uusi alkio lisätään uudeksi solmuksi keon pohjalle listan loppuun. Tämän jälkeen alkiota nostetaan ylöspäin taso kerrallaan, kunnes se on oikealla paikalla keossa. Joka vaiheessa vaihdetaan keskenään solmun ja sen vanhemman sisältö.

Seuraava kuva näyttää, miten alkio \(2\) voidaan lisätä kekoon. Alkio lisätään aluksi keon pohjalle, minkä jälkeen se nostetaan kaksi tasoa ylöspäin.

Alkion poistaminen keosta

Keon juuressa oleva alkio voidaan poistaa siirtämällä sen tilalle keon viimeinen alkio. Tämän jälkeen juuressa olevaa alkiota lasketaan alaspäin taso kerrallaan, kunnes se on oikealla paikalla keossa.

Seuraava kuva näyttää, miten pienin alkio \(1\) voidaan poistaa keosta. Sen tilalle siirretään keon pohjalta alkio \(5\), joka lasketaan sitten alaspäin.

Keon käsittely listana

Pythonin keon toimintaa on helppoa tutkia, koska keon sisältö on aina saatavilla listana. Esimerkiksi seuraava koodi näyttää, miten lista muuttuu, kun lisätään ja poistetaan alkio äskeisten esimerkkien mukaisesti.

import heapq

heap = [1, 3, 5, 4, 5, 8, 9, 7, 8, 5]

heapq.heappush(heap, 2)
print(heap) # [1, 2, 5, 4, 3, 8, 9, 7, 8, 5, 5]

heap = [1, 3, 5, 4, 5, 8, 9, 7, 8, 5]

heapq.heappop(heap)
print(heap) # [3, 4, 5, 5, 5, 8, 9, 7, 8]

Moduulissa heapq on saatavilla myös funktio heapify, joka muuttaa olemassa olevan listan keoksi:

import heapq

items = [8, 7, 6, 5, 4, 3, 2, 1]

heapq.heapify(items)
print(items) # [1, 4, 2, 5, 8, 3, 6, 7]

Funktion heapify aikavaativuus on \(O(n)\), eli sen käyttäminen on tehokkaampaa kuin suorittaa \(n\) kertaa funktio heappush tyhjään kekoon. Tässä kuluisi aikaa \(O(n \log n)\), koska funktio heappush vie aikaa \(O(\log n)\).

Esimerkki: Liukuva ikkuna

Tehtävä

Voimme ratkaista tehtävän tehokkaasti keon avulla seuraavasti:

import heapq

def find_minima(items, k):
    n = len(items)
    heap = []
    result = []
    
    for i in range(n):
        heapq.heappush(heap, (items[i], i))
        while heap[0][1] <= i - k:
            heapq.heappop(heap)
        if i >= k - 1:
            result.append(heap[0][0])
            
    return result

Tämä algoritmi käy läpi listan ja lisää kekoon alkioita muotoa \((x,i)\): alkio \(x\) on kohdassa \(i\). Keosta voidaan hakea tehokkaasti pienin alkio, joka on kohdassa \(0\). Lisäksi jos havaitaan, että keon pienin alkio on jäänyt listan ulkopuolelle, se poistetaan keosta.

Tuloksena olevan algoritmin aikavaativuus on \(O(n \log n)\), koska jokainen alkio lisätään kekoon ja poistetaan keosta enintään kerran.

Muiden kielten toteutukset

Pakan toteuttamiseen on useita tapoja, ja C++:n ja Javan toteutuksissa myös alkioiden indeksointi on tehokasta. C++:ssa luokka std::deque toteuttaa pakan:

std::deque<int> items;

items.push_back(1);
items.push_back(2);
items.push_front(3);
items.push_back(4);
items.push_front(5);

Javassa on taulukkoon perustuva luokka ArrayDeque:

ArrayDeque<Integer> items = new ArrayDeque<>();

items.addLast(1);
items.addLast(2);
items.addFirst(3);
items.addLast(4);
items.addFirst(5);

Monissa kielissä kekoa käyttävän tietorakenteen nimi on prioriteettijono (priority queue). C++:ssa luokka std::priority_queue, toteuttaa maksimikeon:

std::priority_queue<int> items;

items.push(1);
items.push(2);
items.push(3);

cout << items.top() << "\n"; // 3
items.pop();
cout << items.top() << "\n"; // 2

Javassa luokka PriorityQueue toteuttaa minimikeon:

PriorityQueue<Integer> items = new PriorityQueue<>();

items.add(1);
items.add(2);
items.add(3);

System.out.println(items.peek()); // 1
items.poll();
System.out.println(items.peek()); // 2