4. Prioritné fronty

Dátová štruktúra front (rad) umožňuje uchovávať ľubovoľné dáta a poskytuje ich presne v tom poradí, ako sem boli vkladané. Pripomeňme si túto štruktúru z 1. ročníka, ktorá bola realizovaná typom list:

class EmptyError(Exception): pass

class Queue:

    def __init__(self):
        '''inicializuje zoznam'''
        self._prvky = []

    def enqueue(self, data):
        '''na koniec radu vlozi novu hodnotu'''
        self._prvky.append(data)

    def dequeue(self):
        '''zo zaciatku radu vyberie prvu hodnotu, alebo vyvola EmptyError'''
        if self.is_empty():
            raise EmptyError('prazdny rad')
        return self._prvky.pop(0)

    def front(self):
        '''zo zaciatku radu vrati prvu hodnotu, alebo vyvola EmptyError'''
        if self.is_empty():
            raise EmptyError('prazdny rad')
        return self._prvky[0]

    def is_empty(self):
        '''zisti, ci je rad prazdny'''
        return self._prvky == []

Niekedy môžeme potrebovať trochu zmenené správanie frontu:

  • už pri vkladaní dát do frontu zadávame aj ešte jednu špeciálnu hodnotu, tzv. kľúč, ktorý označuje prioritu tohto prvku: čím menšia hodnota kľúča, tým vyššia priorita, teda dôležitosť vloženého prvku
  • pri vyberaní z frontu dostávame nie ten prvok, ktorý bol vložený ako prvý, ale ten, ktorý má najmenší kľúč
  • okrem vkladania a vyberania z takéhoto frontu sa vieme pozrieť aj na prvok, ktorý má najnižší kľúč (najlepšiu prioritu), teda ten, ktorý sa bude najbližšie z frontu vyberať

Abstraktný dátový typ

Budeme sa zaoberať tým, ako čo najefektívnejšie realizovať takýto front. Budú nás zaujímať práve operácie s takouto štruktúrou. Najprv sa teda dohodneme, aké operácie budeme očakávať pre všetky možné realizácie:

  • p.is_empty() - zistí, či je front prázdny
  • len(p) - vráti počet prvkov vo fronte
  • p.add(key, value) - pridá nový prvok s kľúčom key a ľubovoľnou hodnotou value
    • všetky kľúče by sa mali dať navzájom porovnávať operáciou „menší“ (zabezpečí metóda __lt__())
  • p.min() - vráti dvojicu (key, value) (typ tuple) prvku s najmenším kľúčom
    • bude hlásiť chybu, ak je front prázdny
    • ak je vo fronte viac prvkov s minimálnym kľúčom, vráti jeden z nich
  • p.remove_min() - vráti dvojicu (key, value) (typ tuple) prvku s najmenším kľúčom a zároveň ho z frontu odstráni

Aby sme zabezpečili, že niektorá konkrétna realizácia prioritného frontu naozaj zrealizuje všetky požadované operácie, zadefinujeme príslušnú abstraktnú triedu. Zrejme všetky ďalšie triedy budú od tejto abstraktnej odvodené.

from abc import ABC, abstractmethod

class Empty(Exception): pass

class PriorityQueue(ABC):

    class _Item:
        def __init__(self, key, value):
            self.key, self.value = key, value

        def __lt__(self, other):
            return self.key < other.key

        def __repr__(self):
            return str((self.key, self.value))

    @abstractmethod
    def __len__(self):
        '''vráti počet prvkov'''
        pass

    @abstractmethod
    def add(self, key, value):
        '''pridá dvojicu (key, value)'''
        pass

    @abstractmethod
    def min(self):
        '''vráti dvojicu (key, value) s najmenším kľúčom'''
        pass

    @abstractmethod
    def remove_min(self):
        '''vráti a odstráni dvojicu (key, value) s najmenším kľúčom'''
        pass

    def is_empty(self):
        return len(self) == 0

Všimnite si, že na uchovávanie dvojíc použijeme pomocnú triedu _Item a nie pythonovskú dvojicu (typ tuple). Dôvod je taký, aby sme lepšie vyjadrili, že pri vzájomnom porovnávaní dvoch dvojíc (key1, value1) a (key2, value2) musíme porovnávať len hodnoty kľúčov key1 a key2 a nemali by sme nikdy navzájom porovnávať hodnoty value1 a value2 (o týchto dvoch nemáme žiadne predpoklady, že sú to porovnávateľné dáta). Ak by sme totiž urobili if (key1, value1) < (key2, value2) a kľúče by sa rovnali, Python by porovnával ďalšie prvky dvojice a tu by to mohlo spadnúť.

Pomocou neutriedenej postupnosti

Začneme realizáciou pomocou neutriedenej postupnosti, t. j. dvojice (key, value) budeme ukladať do pythonovského zoznamu (typ list). Novú dvojicu budeme pridávať na momentálny koniec zoznamu (operácia list.append() je rýchla) a na vyhľadanie minimálneho kľúča budeme musieť prejsť a porovnať všetky prvky zoznamu. Ak by sme na realizáciu namiesto zoznamu použili dvojsmerný spájaný zoznam, vkladanie aj vyhľadanie by bolo rovnako rýchle (pomalé), ale vyberanie prvku z frontu je rýchlejšie pri spájanom zozname ako pri liste.

Zapíšme túto implementáciu:

class UnsortedPriorityQueue(PriorityQueue):

    def __init__(self):
        self._data = []

    def __len__(self):
        '''vráti počet prvkov'''
        return len(self._data)

    def add(self, key, value):
        '''pridá dvojicu (key, value)'''
        self._data.append(self._Item(key, value))

    def _find_min(self):
        '''pomocná funkcia:
             vráti index dvojice (key, value) s najmenším kľúčom
        '''
        if self.is_empty():
            raise Empty('priority queue is empty')
        index = 0
        for i in range(1, len(self._data)):
            if self._data[i] < self._data[index]:
                index = i
        return index

    def min(self):
        '''vráti dvojicu (key, value) s najmenším kľúčom'''
        index = self._find_min()
        item = self._data[index]
        return item.key, item.value

    def remove_min(self):
        '''vráti a odstráni dvojicu (key, value) s najmenším kľúčom'''
        index = self._find_min()
        item = self._data.pop(index)
        return item.key, item.value
  • keďže min() hľadá minimálny prvok v neutriedenom zozname, musí ho vždy prejsť celý, táto operácia teda stojí O(n)
  • podobne aj remove_min() najprv hľadá minimálny prvok (teda O(n)) a potom tento prvok vyhodí zo zoznamu metódou pop(), t. j. ďalších O(n)
    • ak by sme toto realizovali spájaným zoznamom, vyhodenie nájdeného prvku by stálo iba O(1), ale aj tak má táto operácia s hľadaním minima zložitosť O(n)
Zložitosť operácií
operácia zložitosť  
len() O(1)  
is_empty() O(1)  
add() O(1)*  
min() O(n)  
remove_min() O(n)  

* označuje amortizovanú zložitosť, lebo sa využíva metóda list.append()

Môžeme otestovať:

p = UnsortedPriorityQueue()
p.add(5,'A')
p.add(9,'B')
p.add(3,'C')
p.add(7,'D')
p.add(4,'E')
p.add(6,'F')
print('data=', p._data)
print('min=', p.min(), 'data=', p._data)
print('remove_min=', p.remove_min(), 'data=', p._data)
print('remove_min=', p.remove_min(), 'data=', p._data)
print('len=', len(p))
while not p.is_empty():
    print('remove_min=', p.remove_min(), 'data=', p._data)
print('is_empty=', p.is_empty())
print('remove_min=', p.remove_min(), 'data=', p._data)

dostávame:

data= [(5,'A'), (9,'B'), (3,'C'), (7,'D'), (4,'E'), (6,'F')]
min= (3, 'C') data= [(5,'A'), (9,'B'), (3,'C'), (7,'D'), (4,'E'), (6,'F')]
remove_min= (3, 'C') data= [(5,'A'), (9,'B'), (7,'D'), (4,'E'), (6,'F')]
remove_min= (4, 'E') data= [(5,'A'), (9,'B'), (7,'D'), (6,'F')]
len= 4
remove_min= (5, 'A') data= [(9,'B'), (7,'D'), (6,'F')]
remove_min= (6, 'F') data= [(9,'B'), (7,'D')]
remove_min= (7, 'D') data= [(9,'B')]
remove_min= (9, 'B') data= []
is_empty= True

Empty: priority queue is empty

Realizácia pomocou funkcií bez tried

Pre názornosť, zjednodušenie pochopenia a aj jednoduchšie testovanie prepíšeme toto riešenie len pomocou niekoľkých globálnych funkcií. Samotný zoznam bude v globálnej premennej data a pracovať budeme iba s kľúčmi:

class EmptyError(Exception): pass

data = []

def add(key):
    data.append(key)

def _find_min():
    if len(data) == 0:
        raise EmptyError
    index = 0
    for i in range(1, len(data)):
        if data[i] < data[index]:
            index = i
    return index

def min():
    return data[_find_min()]

def remove_min():
    return data.pop(_find_min())

Teraz aj testovanie bude prehľadnejšie:

for i in 5, 9, 3, 7, 4, 6:
    add(i)
print('data =', data)
while data:
    print('remove_min =', remove_min(), 'data =', data)
print('remove_min =', remove_min(), 'data =', data)
data = [5, 9, 3, 7, 4, 6]
remove_min = 3 data = [5, 9, 7, 4, 6]
remove_min = 4 data = [5, 9, 7, 6]
remove_min = 5 data = [9, 7, 6]
remove_min = 6 data = [9, 7]
remove_min = 7 data = [9]
remove_min = 9 data = []

EmptyError

Pomocou utriedenej postupnosti

Pokúsme sa zefektívniť operácie prioritného frontu tak, že pythonovský zoznam (typ list) budeme udržiavať utriedený. Zrejme budeme musieť prvky vkladať do zoznamu na správne miesto, teda pred všetky s väčšou hodnotou kľúča. Hľadanie a vyberanie minimálnej hodnoty bude teraz veľmi jednoduché.

Opäť použijeme pythonovský zoznam - hoci vhodnejší by bol asi dvojsmerný spájaný zoznam. Pracuje s ním tak, aby bol stále utriedený:

class EmptyError(Exception): pass

data = []

def add(key):
    i = len(data)
    while i > 0 and key < data[i - 1]:
        i -= 1
    data.insert(i, key)

def min():
    if len(data) == 0:
        raise EmptyError
    return data[0]

def remove_min():
    if len(data) == 0:
        raise EmptyError
    return data.pop(0)

Naša verzia pre remove_min() požíva metódu pop(0), ktorej zložitosť je O(n)

Zložitosť operácií
operácia unsorted sorted  
len() O(1) O(1)  
is_empty() O(1) O(1)  
add() O(1)* O(n)  
min() O(n) O(1)  
remove_min() O(n) O(n)  

Funkčnosť môžete otestovať rovnakým spôsobom, ako pre prvú verziu:

data = [3, 4, 5, 6, 7, 9]
remove_min = 3 data = [4, 5, 6, 7, 9]
remove_min = 4 data = [5, 6, 7, 9]
remove_min = 5 data = [6, 7, 9]
remove_min = 6 data = [7, 9]
remove_min = 7 data = [9]
remove_min = 9 data = []

EmptyError

Uvažujte:

  • Ako by sa zmenila implementácia tohto prioritného frontu, keby sme zoznam udržiavali utriedený zostupne, teda minimálny prvok by bol posledný? Zmenila by sa zložitosť operácií?
  • Ako by sa zmenila implementácia tejto triedy, keby sme namiesto zoznamu využili spájaný zoznam? Zmenila by sa zložitosť operácií?

Pomocou haldy

Tretia verzia implementácie prioritného frontu využíva dátovú štruktúru halda, ktorá má veľmi užitočné vlastnosti:

halda = heap

je binárny strom, ktorý musí spĺňať tieto dve podmienky:

  • vzťah medzi vrcholmi: každý vrchol (okrem koreňa) má hodnotu kľúča väčšiu alebo rovnú ako hodnota kľúča v jeho predkovi
    • vďaka tejto vlastnosti je v koreni minimálna hodnota kľúča z celého stromu
  • tvar stromu: chceme, aby strom mal minimálnu hĺbku, preto budeme požadovať takúto vlastnosť (skoro) úplného binárneho stromu:
    • okrem najnižšej úrovne sú všetky úrovne úplné
    • v najnižšej úrovni sú všetky vrcholy umiestňované len zľava
  • výška takéhoto binárneho stromu je log n

Halda implementovaná v zozname/poli

Keďže halda je „skoro“ úplný binárny strom, nemusíme ju realizovať pomocou spájanej štruktúry, ale použijeme pythonovský zoznam (typ list):

  • do zoznamu budeme prvky stromu ukladať po úrovniach:
    • najprv koreň (do 0. prvku)
    • potom dva vrcholy z ďalšej úrovne (obaja potomkovia koreňa)
    • za tým 4 vrcholy z 2. úrovne (najprv obaja potomkovia ľavého syna koreňa, potom obaja potomkovia pravého syna koreňa),
    • … atď.
    • na koniec všetky zvyšné vrcholy z poslednej (možno neúplnej) úrovne
  • hĺbka tohto stromu je log n
  • pre potomkov a predka vrcholu s indexom i platí:
    • predok má index (i-1) // 2
    • ľavý syn má index 2 * i + 1
    • pravý syn má index 2 * i + 2

Funkcia add() - vloženie nového prvku:

  • aby sme zachovali vlastnosť (skoro) úplného binárneho stromu, pridáme vrchol na úplný koniec (za posledný prvok v zozname), teda data.append()
  • asi sme tým pokazili pravidlo medzi vrcholom a jeho predkom: haldu treba upratať - budeme prebublávať v halde od tohto prvku nahor smerom ku koreňu:
    • ak je práve pridaný prvok menší ako jeho predok (s indexom (i - 1) // 2), vymení ho s predkom a znovu kontroluje už túto jeho novú pozíciu s novým predkom
    • toto sa opakuje, kým nenatrafí na menšieho predka (teda je to už OK) alebo sa dostane až do koreňa stromu
    • takto sa opraví celá halda

Funkcia remove_min() - vyhodenie minimálneho prvku, t.j. koreň haldy

  • nesmieme naozaj vyhodiť 0. prvok zoznamu (koreň stromu), lebo by sa halda pokazila tak, že jej oprava by bola príliš náročná, namiesto toho:
  • vyhodený koreň nahradíme posledným prvkom v halde (najpravejší v najnižšej úrovni) a haldu (zoznam) pritom o 1 skrátime
  • asi sme tým opäť haldu pokazili - budeme tento prvok kontrolovať s jeho synmi a vymieňať, t.j. budeme prebublávať smerom nadol:
    • práve presťahovaný 0. prvok zoznamu porovnáme s oboma jeho synmi (prvky s indexami 2 * i + 1 a 2 * i + 2)
    • ak je jeden z nich menší ako spracovávaný vrchol, tak menší z nich vymeníme so spracovávaným vrcholom a znovu túto novú pozíciu porovnávame s jeho synmi
    • toto sa opakuje, kým neprídeme do listu stromu (vrchol už nemá ani jedného syna), alebo obaja synovia už nemajú menšiu hodnotu
    • takto sa opraví celá halda

Realizácia

Pre lepšiu názornosť nedefinujeme triedu, ale len samostatné tri funkcie:

class EmptyError(Exception): pass

data = []

def add(key):
    # nový prvok pridáme na koniec
    data.append(key)
    # teraz to prebublá nahor
    vrchol = len(data) - 1
    while vrchol > 0:                # vrchol nie je koreň
        # ak je key < ako predok: vymeň ich
        predok = (vrchol - 1) // 2
        if data[vrchol] < data[predok]:
            data[vrchol], data[predok] = data[predok], data[vrchol]
            vrchol = predok
        else:
            break    # hotovo

def min():
    if len(data) == 0:
        raise EmptyError
    return data[0]

def remove_min():
    if len(data) == 0:
        raise EmptyError
    # vymeníme posledný s prvým a haldu o posledný skrátime
    data[0], data[-1] = data[-1], data[0]
    res = data.pop()
    # celé je to halda okrem data[0]
    vrchol = 0
    while True:
        # nájdem menšieho syna - ak nie je, break
        lavy = vrchol * 2 + 1
        if lavy >= len(data):
            break
        mensi = lavy
        pravy = vrchol * 2 + 2
        if pravy < len(data) and data[pravy] < data[lavy]:
            mensi = pravy
        # vrchol vymeníme s menším alebo skončím
        if data[mensi] < data[vrchol]:
            data[mensi], data[vrchol] = data[vrchol], data[mensi]
            vrchol = mensi
        else:
            break
    return res

Zložitosť operácií

  • min() - je bez cyklu, len vráti prvú hodnotu v zozname => O(1)
  • add() - algoritmus pri prebublávaní nahor urobí maximálne toľko porovnávaní, aká je hĺbka stromu, t.j. O(log n)
  • remove_min() - algoritmus pri prebublávaní nadol urobí maximálne toľko porovnávaní, aká je hĺbka stromu, t.j. O(log n)
    • uvedomte si, že ak by sme namiesto výmeny data[0], data[-1] = data[-1], data[0] a data.pop() robili najprv data.pop(0) a potom vložili posledný prvok na začiatok pomocou data.insert(0), tak zložitosť remove_min() by stúpla na O(n)

Zhrňme to do tabuľky:

Zložitosť operácií
operácia unsorted sorted heap  
len() O(1) O(1) O(1)  
is_empty() O(1) O(1) O(1)  
add() O(1)* O(n) O(log n)*  
min() O(n) O(1) O(1)  
remove_min() O(n) O(n) O(log n)*  

* označuje amortizovanú zložitosť, lebo sa využívajú metódy list.append() a list.pop()

Po otestovaní:

data = [3, 4, 5, 9, 7, 6]
remove_min = 3 data = [4, 6, 5, 9, 7]
remove_min = 4 data = [5, 6, 7, 9]
remove_min = 5 data = [6, 9, 7]
remove_min = 6 data = [7, 9]
remove_min = 7 data = [9]
remove_min = 9 data = []

EmptyError

Všimnite si, ako sa v zozname uchováva halda: po každom vyhodení prvého prvku sa zoznam preuprace

Využitie modulu heapq

Idea uchovávania prvkov v zozname tak, aby mali vlastnosť haldy, je pre programátorov tak užitočná, že v Pythone jeden zo štandardných modulov heapq pracuje s haldou, teda pracuje s obyčajným zoznamom (typ list), ale prvky udržiava v správnom poradí. Modul heapq ponúka tieto funkcie:

  • heappush(data, prvok) - vloží nový prvok do zoznamu data, tak aby to stále bola halda (predpokladáme, že v tomto zozname už predtým bolo správne haldové usporiadanie) - zložitosť tejto funkcie je O(log n)
  • heappop(data) - robí to isté ako naše remove_min(), teda vráti zo zoznamu 0. prvok, pritom ho zo zoznamu vyhodí a preusporiada ho, aby to bola opäť halda - zložitosť tejto funkcie je O(log n)
  • heapify(data) - preusporiada zoznam tak, aby spĺňal podmienky haldy - zložitosť tejto funkcie je O(n)

Zrejme prvky vkladané do zoznamu musia byť navzájom porovnávateľné, preto nemôžeme do haldy vkladať dvojice (key, value) (typ tuple), ak sú druhé zložky neporovnávateľné, napr. (15, 3.14) a (15, 'a') majú rovnaký kľúč a neporovnávateľné hodnoty.

Zapíšme definíciu funkcií pomocou modulu heapq:

import heapq

class EmptyError(Exception): pass

data = []

def add(key):
    heapq.heappush(data, key)

def min():
    if len(data) == 0:
        raise EmptyError
    return data[0]

def remove_min():
    if len(data) == 0:
        raise EmptyError
    return heapq.heappop(data)

Po otestovaní vidíme, že to funguje rovnako, ako naša vlastná realizácia haldy:

data = [3, 4, 5, 9, 7, 6]
remove_min = 3 data = [4, 6, 5, 9, 7]
remove_min = 4 data = [5, 6, 7, 9]
remove_min = 5 data = [6, 9, 7]
remove_min = 6 data = [7, 9]
remove_min = 7 data = [9]
remove_min = 9 data = []

EmptyError

Triedenie pomocou prioritného frontu

Dátovú štruktúru prioritný front môžeme použiť aj na utriedenie ľubovoľného zoznamu. Použijeme takýto algoritmus:

  • najprv sa zo všetkých prvkov zoznamu vytvorí prioritný front (n-krát sa zavolá operácia add())
    • ako kľúč použijeme samotnú hodnotu z triedeného zoznamu
  • potom opäť v cykle vyberáme stále najmenší prvok a vkladáme ho späť do zoznamu na správne miesto

Tento algoritmus nevracia žiadnu hodnotu, ale priamo triedi vstupný zoznam:

def sort(zoz):
    for prvok in zoz:
        add(prvok)
    for i in range(len(zoz)):
        zoz[i] = remove_min()

Ak zavoláme takéto triedenie pomocou funkcií s neutriedeným zoznamom (volali sme to unsorted), dostávame nám známy algoritmus triedenia min-sort (nazýva sa aj selection-sort). V tomto prípade sa stále vyberá minimálny prvok a vkladá sa za už utriedenú časť na začiatku zoznamu.

Ak zavoláme takéto triedenie pomocou utriedeného zoznamu (volali sme to sorted), dostávame opäť nám známy algoritmus triedenia insert-sort. V tomto prípade už vytvorenie prioritného frontu (n-krát vloženie pomocou operácie add()) vytvorí usporiadaný zoznam. Druhá časť algoritmu ho len prekopíruje do pôvodného zoznamu.

Vidíme, že oba sorty majú zložitosť O(n**2).

Triedenie pomocou prioritného frontu s haldou = heap sort

Použitie algoritmu sort() s využitím haldy bude mať inú zložitosť ako v dvoch predchádzajúcich prípadoch:

  • prvá časť algoritmu, ktorá pomocou operácie add() vytvára front (teda poskladá haldu zo všetkých prvkov zoznamu), má zložitosť O(n log n) (n-krát vloženie do haldy, ktorého zložitosť je O(log n))
  • druhá časť algoritmu, ktorá pomocou operácie remove_min() postupne vyberá minimálne prvky a vkladá ich na príslušné miesta v zozname, má tiež zložitosť O(n log n) (n-krát vyberanie z haldy, ktorého zložitosť je O(log n))
  • celková zložitosť je teda súčet zložitostí týchto dvoch častí, teda opäť je to O(n log n)

Otestujeme rýchlosť tohto triedenia s haldou pre rôzne veľké vstupné zoznamy:

import time
import random

for n in 1000, 10000, 100000, 1000000:
    zoz = [random.randrange(10000) for i in range(n)]
    zoz0 = zoz[:]      # kontrolná kópia pôvodného zoznamu

    start = time.time()
    # samotné triedenie
    for prvok in zoz:
        add(prvok)
    for i in range(len(zoz)):
        zoz[i] = remove_min()
    # koniec triedenia
    end = time.time()
    print('{:<8} {:<10.6f}'.format(n, end-start), zoz==sorted(zoz0))

Pri výpise vidíme, že porovnanie výsledného zoznamu s utriedeným pomocou štandardného pythonovského triedenia (sorted()) prebehlo v poriadku, teda vrátilo True:

1000     0.015999   True
10000    0.321295   True
100000   4.055583   True
1000000  47.430463  True

Všimnite si, ako sa postupne mení čas, keď program spúšťame s 10-krát väčším zoznamom: zrejme je to o trochu väčší prírastok, ako keby to bola zložitosť O(n), teda mohli by sme usudzovať, že zložitosť tohto algoritmu je naozaj O(n log n).

Triedenie pomocou haldy (tzv. heap-sort) je teda rýchle triedenie a je porovnateľné napr. s quick-sortom. Táto naša realizácia ale využíva na triedenie pomocný zoznam rádovo veľkosti n (zoznam s haldou sa vytvoril mimo samotného triedeného zoznamu). Ak by sme chceli zefektívniť takéto triedenie, asi by boli vhodné takéto vylepšenia:

  • pracovať budeme priamo so vstupným zoznamom bez ďalšieho pomocného zoznamu, teda haldu vytvoríme preusporiadaním prvkov zoznamu
  • aby sme v druhej fáze algoritmu nepotrebovali pomocný zoznam na postupné ukladanie minimálnych prvkov (remove_min()) do výsledného zoznamu, pravidlá pre haldu zmeníme tak, že v koreni bude maximálny prvok a všetky preusporiadania haldy (prebublávania nahor aj nadol) budú robiť opačné testy; potom stačí maximálny prvok vymieňať s posledným prvkom haldy a namiesto skracovania haldy, len zmenšíme premennú, ktorá bude označovať počet prvkov haldy (namiesto len(data) budeme vo všetkých metódach pracovať s touto premennou)

Aj vytváranie haldy (prvá fáza algoritmu heap-sort), ktorá má zložitosť O(n log n) sa dá ešte urýchliť tak, aby mala zložitosť O(n). Tomuto sa hovorí algoritmus heapify (vie to aj modul heapq) a pracuje takto:

  • postupne prechádza zoznam od konca
  • pre každý i-ty prvok zabezpečí, aby sa podstrom s koreňom i stal haldou (použijeme „prebublanie nadol“):
    • zrejme na začiatku to budú malé binárne stromy a čím ideme vyššie (blížime sa ku koreňu), budú aj tie binárne stromy - haldy väčšie a väčšie
    • na záver sa takto uhalduje celý strom
  • uvedomte si, že v tomto cykle nemusíme začínať od vrcholov stromu, ktoré sú listami, stačí začínať s vrcholmi, ktoré majú aspoň jedného syna: teda začneme až od vrcholu s indexom n // 2

Zamyslite sa, či by ste vedeli dokázať, že tento algoritmus má naozaj zložitosť O(n).

Z pohľadu zložitosti algoritmov takéto vylepšenia (bez pomocného zoznamu, otočená halda od maximálnej hodnoty, heapify, …) nemení celkovú zložitosť, stále je to O(n log n), ale v reálnych situáciách sa robia aj takéto vylepšenia, lebo výrazne pomôžu skutočnému času behu.



Cvičenia

L.I.S.T.

  1. Predpokladaj, že na vstupe máme tieto hodnoty:

    • vstupné pole:

      8, 13, 7, 10, 5, 15, 12, 17, 9, 14, 4, 11, 18, 16, 6
      
    • ručne vytvor z tohto poľa haldu (postupne pridávaj najprv do prázdneho stromu rovnako ako funkcia add())

    • ručne z haldy niekoľkokrát odstráň minimálny prvok (operácia remove_min())

    • priebeh ukladania do haldy (aj vyberania najmenšieho) si môžeš vizualizovať napr. aj na stránke Heap Visualization


  1. Spojazdni všetky funkcie pre prioritný front, ktoré fungujú pomocou haldy a prever, či je tvoja halda z úlohy (1) rovnaká ako v tomto programe. Tiež skontroluj, či aj tvoje ručné odstraňovanie minimálnych prvkov haldu upratalo úplne rovnako ako v programe.

    • haldou vytvor pomocou:

      data = []
      for i in pole:
          add(i)
      print(data)
      
    • postupné odstraňovanie najmenšieho prvku:

      for i in range(4):
          print(remove_min(), data)
      

  1. Napíš funkciu kontrola_na_haldu(zoz), ktorá skontroluje, či daný zoznam spĺňa podmienky haldy.

    • napr.

      >>> zoz = [8, 13, 7, 10, 5, 15, 12, 17, 9, 14, 4, 11, 18, 16, 6]
      >>> kontrola_na_haldu(zoz)
      False
      
      >>> data = []
      >>> for i in pole:
              add(i)
      >>> kontrola_na_haldu(data)
      True
      
    • zamysli sa, či ľubovoľný vzostupne usporiadaný zoznam je automaticky haldou? napr.

      >>> zoz = list(range(30))
      >>> kontrola_na_haldu(zoz)
      ???
      

  1. Jedna z úloh záverečného testu sa venovala haldám:

    Z rôznych čísel 1 až 10 vytvor haldu (v koreni s indexom 0. je minimum) v 10-prvkovom zozname tak, aby:

    1. v prvku zoznamu s indexom 4 bola maximálne možná hodnota
    2. v prvku zoznamu s indexom 4 bola minimálne možná hodnota

    Pre obe podúlohy zrealizuj aj operáciu remove_min().


  1. Zadefinuj triedu HeapPriorityQueue, ktorá bude odvodená od abstraktnej triedy PriorityQueue podobne, ako sa to urobilo pre UnsortedPriorityQueue. Pritom obidve prebublávania presuň do dvoch pomocných metód _heap_up pre prebublanie nahor z funkcie add() a _heap_down pre prebublanie nadol z remove_min. Uvedom si, že prioritný front musí ukladať dvojice (kľúč, hodnota) do pomocnej podtriedy _Item a až tieto pôjdu do zoznamu _data. Výsledkom oboch metód min aj remove_min budú dvojice (tuple) (kľúč, hodnota) rovnako, ako sa to robilo v UnsortedPriorityQueue.

    • dodefinuj:

      from priority_queue import PriorityQueue
      
      class HeapPriorityQueue(PriorityQueue):
      
          def __init__(self):
              self._data = []
      
          def __len__(self):
              return len(self._data)
      
          def add(self, key, value):
              ...
      
          def min(self):
              ...
      
          def remove_min(self):
              ...
      
          #---- pomocne metody ----
      
          def _heap_up(self, index):      # index vrchol odkial zacne
              ...
      
          def _heap_down(self, index):    # index vrchol odkial zacne
              ...
      
    • otestuj túto svoju implementáciu podobne ako pri UnsortedPriorityQueue:

      p = HeapPriorityQueue()
      p.add(5,'A')
      p.add(9,'B')
      p.add(3,'C')
      p.add(7,'D')
      p.add(4,'E')
      p.add(6,'F')
      print('data=', p._data)
      print('min=', p.min(), 'data=', p._data)
      print('remove_min=', p.remove_min(), 'data=', p._data)
      print('remove_min=', p.remove_min(), 'data=', p._data)
      print('len=', len(p))
      while not p.is_empty():
          print('remove_min=', p.remove_min(), 'data=', p._data)
      print('is_empty=', p.is_empty())
      print('remove_min=', p.remove_min(), 'data=', p._data)
      

  1. Algoritmus, ktorý zo zoznamu vytvára haldu (prvá fáza nášho triedenia heap_sort()) má zložitosť O(n log n) (n-krát sa urobí prebublanie nahor a ten má zložitosť O(log n)). Ak by sme ale haldu nevytvárali zhora postupným pridávaním prvku na koniec, ale naopak zdola, mohli by sme zabezpečiť zložitosť tejto fázy algoritmu O(n). Tento algoritmus sa nazýva heapify a pracuje na takomto princípe:

    • pre jednoduchosť predpokladajme, že strom je úplny (najnižšia úroveň je kompletná)
    • každý vrchol najnižšej úrovne stromu je malá halda
    • postupne prechádzame predposlednú úroveň vrcholov: vytvoríme malé haldy z tohto vrcholu a jeho dvoch synov (algoritmus prebublanie nadol), ktoré sú už teraz malé haldy
    • potom prejdeme o úroveň vyššie a vytvoríme haldy s koreňmi v týchto vrcholoch, keďže ich synovia sú už malé haldy (opäť prebublanie nadol)
    • takto postupne prejdeme všetky vrcholy stromu až po koreň - keď už sme v koreni, celý strom je haldou

    Dá sa ukázať, že tento algoritmus má naozaj zložitosť O(n). Na stránke Heap Visualization môžete vidieť aj algoritmus heapify, tu sa volá BuildHeap.

    • ručne vytvor haldu zo zoznamu z úlohy (1):

      >>> zoz = [8, 13, 7, 10, 5, 15, 12, 17, 9, 14, 4, 11, 18, 16, 6]
      

  1. Do triedy HeapPriorityQueue doprogramuj metódu heapify(zoznam), ktorá daný zoznam dvojíc (kľúč, hodnota) najprv zapíše do self._data (ako _Item) a potom ho podľa algoritmu z úlohy (6) uprace na haldu.

    • odkontroluj, či je takto vytvorený zoznam haldou, napr.

      >>> zoz = [8, 13, 7, 10, 5, 15, 12, 17, 9, 14, 4, 11, 18, 16, 6]
      >>> p = HeapPriorityQueue()
      >>> p.heapify(zoz)
      >>> kontrola_na_haldu(p._data)
      True
      

  1. V niektorých situáciách je vhodné, aby prioritný front nepracoval s minimálnymi kľúčmi, ale s maximálnymi. Vytvor verziu triedy MaxHeapPriorityQueue, ktorá implementuje metódy tejto triedy.

    • zrejme v koreni stromu je maximálny prvok a mnohé testy bude treba nejako otočiť:

      class MaxHeapPriorityQueue:
        class _Item:
            def __init__(self, key, value):
                self.key, self.value = key, value
      
            def __lt__(self, other):
                return self.key < other.key
      
            def __repr__(self):
                return str((self.key, self.value))
        #......................
        def __len__(self):
            '''vráti počet prvkov'''
            pass
      
        def add(self, key, value):
            '''pridá dvojicu (key, value)'''
            pass
      
        def max(self):
            '''vráti dvojicu (key, value) s najväčším kľúčom'''
            pass
      
        def remove_max(self):
            '''vráti a odstráni dvojicu (key, value) s najväčším kľúčom'''
            pass
      
        def is_empty(self):
            return len(self) == 0
      
    • túto triedu otestuj, napr. triedením pomocou tohto prioritného frontu


  1. Napíš funkciu heap_sort(zoz), ktorá utriedi daný zoznam priamo namieste algoritmom heap sort (bez pomocného poľa). Budeme pracovať bez dvojíc (kľúč, hodnota) len s kľúčmi:

    • najprv sa zoznam preusporiada tak, aby spĺňal kritérium haldy s maximálnym v koreni, t. j. zoz[i]>=zoz[2*i+1] a zároveň zoz[i]><=zoz[2*i+2] pre každé i - najvhodnejšie je tu použiť algoritmus heapify
    • keď je halda hotová, postupne sa odoberá 0. prvok (maximum) a odkladá sa na koniec zoznamu (vymení sa s posledným a samotný zoznam sa naozaj neskracuje pomocou pop() len sa zaeviduje, že už je o 1 kratší) - zakaždým sa obnoví halda (prebublanie nadol)
    • takto sa na koniec zoznamu postupne dostávajú maximálne prvky a tým dostávame utriedený celý zoznam

    • funkciu otestuj na správne usporiadanie prvkov aj na rýchlosť pre rôzne veľké náhodné zoznamy



2. Domáce zadanie

L.I.S.T.

Implementujte prioritný front pomocou haldy, ktorá ale nebude uložená v jednorozmernom poli, ale v dvojrozmernom poli data takto:

  • prvý riadok tohto dvojrozmerného poľa data[0] obsahuje jednoprvkové pole s koreňom haldy
  • druhý riadok data[1] obsahuje dvojprvkové pole s ľavým a pravým synom koreňa
  • tretí riadok data[2] obsahuje štvorprvkové pole so všetkými synmi predchádzajúceho riadku
  • každý ďalší riadok dvojrozmerného poľa data má dvojnásobnú dĺžku oproti predchádzajúcemu riadku
  • posledný riadok poľa data môže byť kratší ako táto dvojnásobná dĺžka (ale nie je prázdny)

Keby sme zlepili za seba všetky riadky dvojrozmerného poľa data, dostali by sme pôvodnú reprezentáciu haldy v jednorozmernom poli.

Uvedomte si, že prvkami dvojrozmerného poľa data sú jednorozmerné polia (data je typu list, ktorého každý prvok je typu list), ktorých prvky sú typu HeapPriorityQueue.Item. V dátovej štruktúre HeapPriorityQueue nepoužívajte žiadne ďalšie atribúty (stavové premenné) okrem data a reverse. Môžete si zadefinovať ľubovoľné pomocné metódy, napr. swap, has_left a pod. Je vhodné si pritom každý prvok haldy indexovať nie jedným indexom (ako to bolo v obyčajnej halde, kde pre index i bol jeho otcom i//2 a synovia mali indexy 2*i+1 a 2*i+2), ale dvomi pre index riadku dvojrozmerného poľa a index v príslušnom riadku. Nemeňte podtriedu Item ani inicializáciu __init__ v triede HeapPriorityQueue.

Na riešenie úlohy použite deklarácie v súbore riesenie2.py z úlohového servera L.I.S.T. kde

  • parameter reverse v inicializácii __init__ nastaví vytváranie haldy tak, že v koreni bude maximálny prvok a preto metódy min a remove_min budú namiesto minimálnej hodnoty vracať maximálnu
  • metóda heapify pôvodný obsah dvojrozmerného poľa data nahradí prvkami vstupnej postupnosti seq; predpokladajte, že prvkami seq sú dvojice (typu tuple) hodnôt (key, value) a metóda z nich vyrobí prvky Item; naprogramujte ju tak, aby využila metódu heap_down, t.j. aby mala zložitosť O(n)
  • dávajte pozor, aby ste kľúče navzájom porovnávali len pomocou relácie menší <, iné realačné operácie nemusia s kľúčmi fungovať
class EmptyError(Exception): pass

class HeapPriorityQueue:
    class Item:
        def __init__(self, key, value=None):
            self.key, self.value = key, value

        def __lt__(self, other):
            return self.key < other.key

        def __repr__(self):
            if self.value is None:
                return repr(self.key)
            return str((self.key, self.value))

    def __init__(self, reverse=False):
        self.data = []
        self.reverse = reverse

    def __len__(self):
        return ...

    def is_empty(self):
        return ...

    def add(self, key, value=None):
        ...

    def min(self):
        return ...    # vrati dvojicu alebo EmptyError

    def remove_min(self):
        return ...    # vrati dvojicu alebo EmptyError

    def heapify(self, seq):
        ...

    def heap_up(self, ...):
        ...

    def heap_down(self, ...):
        ...

Váš program môžete testovať napr. takto:

if __name__ == '__main__':
    h = HeapPriorityQueue()
    pp = (8, 13, 7, 10, 5, 15, 12, 17, 9, 14, 4, 11, 18, 16, 6)
    for i in pp:
        h.add(i)
    print(*h.data, sep='\n')
    print('==================================')
    p = []
    while not h.is_empty():
        p.append(h.remove_min())
    print(p == sorted(p, key=lambda x: x[0]))
    h = HeapPriorityQueue()
    h.heapify(zip(pp, 'programujeme v pythone'))
    print(*h.data, sep='\n')

Výpis potom bude takýto:

[4]
[5, 6]
[9, 7, 11, 8]
[17, 13, 14, 10, 15, 18, 16, 12]
==================================
True
[(4, 'm')]
[(5, 'r'), (6, ' ')]
[(9, 'j'), (8, 'p'), (11, 'e'), (7, 'o')]
[(17, 'u'), (10, 'g'), (14, 'e'), (13, 'r'), (15, 'a'), (18, ' '), (16, 'v'), (12, 'm')]

Definíciu triedy HeapPriorityQueue uložte do súboru riesenie2.py a na začiatok pridajte tieto tri komentárové riadky (s vašim menom a dátumom):

# 2. zadanie: heap
# autor: Alan Turing
# datum: 25.10.2018

Súbor riesenie2.py odovzdávajte na úlohový server L.I.S.T. najneskôr do 23:00 7. novembra. Môžete zaň získať 10 bodov.



© Copyright 2018-2019, Andrej Blaho.
Naposledy aktualizované 14. feb. 2019.
Vytvorené pomocou Sphinx 1.8.4.

Creative Commons License This work is licensed under a Creative Commons Attribution 4.0 International License.