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 tietorakenne, 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)\).

Pakka on toteutettu Pythonissa linkitettynä listana, minkä ansiosta on mahdollista lisätä ja poistaa alkioita tehokkaasti sekä listan alussa että lopussa.

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. Kekoon voi lisätä alkioita rajoituksetta, mutta siitä voi hakea ja poistaa vain pienimmän tai suurimman alkion, riippuen keon toteutuksesta.

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

• 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ä keosta 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]

Moduulin heapq funktiot pitävät listan alkioita sopivassa järjestyksessä niin, että keon operaatiot pystytään toteuttamaan tehokkaasti.

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