Mål

Läs i kursboken

Prioritetskö

Heap

7.8 - 7.10. Priority Queues with Binary Heaps

Idag

Prioritetskö
Heap
Heapsort
Bästaförstsökning

Dagens problem: hitta minsta/största värdet.

Prioritetskö

När man poppar en stack får man ut det senast inpushade. När man tar ut något ur en vanlig kö får man tvärtom ut det som legat längst tid i kön. Man skulle kunna se det som att det som stoppas in tidsstämplas och att det påstämplade talet ger prioriteten för uthämtning.

I en prioritetskö stämplas en prioritet på varje objekt som stoppas in och vid uthämtning får man objektet med högst prioritet.

En abstrakt prioritetskö kan ha föjande anrop:

insert(p,x) Stoppa in x med påstämplad prioritet p (oftast ett heltal).
x = delMax() Hämta det som har högst prioritet.
isEmpty() Undersök om prioritetskön är tom.

Om det man vill stoppa in i prioritetskön är ett tal kan man använda talet självt som prioritet och bara skriva insert(x). Hur den då skiljer sej från en stack och från en vanlig kö ser man av följande exempel.

      pq.insert(1)
      pq.insert(3)
      pq.insert(2)
      x = pq.delMax() # x blir 3

En kö hade skickat tillbaka det först instoppade talet 1; en stack hade skickat tillbaka det senast instoppade talet, 2; prioritetskön skickar tillbaka det bästa talet, 3. I denna prioritetskö betraktar vi största talet som bäst - vi har en så kallad maxprioritetskö. Det finns förstås också minprioritetsköer, där det minsta talet betraktas som bäst.

Prioritetsköer har många användningar. Man kan tänka sej en auktion där budgivarna stoppar in sina bud i en maxprioritetskö och auktionsförrättaren efter "första, andra, tredje" gör pq.delMax() för att få reda på det vinnande budet. För att hen ska veta vem som lagt detta bud behövs förstås båda parametrarna ipq.insert(p,x).

      pq.insert(bud,person)   #person är ett objekt med budgivarens namn och bud
      winner = pq.delMax()    #budgivaren  med högst bud

Heap

Den bästa implementationen av en prioritetskö är en heap, (på svenska: trappa), som är en lista tolkad som binärträd (OBS! Inte ett binärt sökträd).

Roten är tab[1], dess båda barn är tab[2] och tab[3] osv. Vi använder inte tab[0]. Allmänt gäller att tab[i] har barnen tab[2*i] och tab[2*i+1].

Heapvillkoret

Heapvillkoret är att föräldern är bäst, dvs varje värde ligger på två sämre värden.

insert()

Ett nytt värde läggs alltid in sist i heapen. Om heapvillkoret inte blir uppfyllt, dvs om det är större än sin förälder, byter förälder och barn plats och så fortgår det tills villkoret uppfyllts. Det här kallas upheap (upptrappning) och kan i värsta fall föra det nya värdet hela vägen upp till toppen, alltså tab[1].

delMax()

Man plockar alltid ut det översta talet ur heapen och fyller igen tomrummet med det sista talet i heapen. Då är inte heapvillkoret uppfyllt, så man får byta talet och dess största barn. Denna downheap (nedtrappning) upprepas tills villkoret åter gäller.

Både insert och delMax har komplexitet O(log n) om heapen har n element.

Här följer en rudimentär implementation av en max-heap:

class HeapNode:

    def __init__(self, data, priority):
        """data är det objekt vi vill lagra
           priority är nyckelvärdet som används för att jämföra objekten"""
        self.data = data
        self.priority = priority

class Heap:
    # En max-heap

    def __init__(self):
        """Skapar en lista där vi använder element 1..maxsize"""
        self.maxsize = 32
        self.tab = (self.maxsize+1)*[None]
        self.size = 0

    def isEmpty(self):
        """Returnerar True om heapen är tom, False annars"""
        return self.size  == 0

    def isFull(self):
        """Returnerar True om heapen är full, False annars"""        
        return self.size == self.maxsize

    def insert(self, data, priority):
        """Lägger in nya data med nyckeln priority i heapen"""
        if not self.isFull():
            self.size += 1
            self.tab[self.size] = HeapNode(data, priority)
            i = self.size
            while i > 1 and self.tab[i//2].priority < self.tab[i].priority:
                self.tab[i//2], self.tab[i] = self.tab[i], self.tab[i//2]
                i = i//2

    def delMax(self):
        """Hämtar det största (översta) objektet ur heapen"""
        if not self.isEmpty():
            utnod = self.tab[1]
            self.tab[1] = self.tab[self.size]
            self.size -= 1
            i = 1
            while i <= self.size//2:
                maxi = self.maxindex(i)
                if self.tab[i].priority < self.tab[maxi].priority:
                    self.tab[i],self.tab[maxi] = self.tab[maxi], self.tab[i]
                i = maxi
            return utnod.data
        else:
            return None

    def maxindex(self, i):
        """Returnerar index för det största barnet"""
        if 2*i+1 > self.size:
            return 2*i
        if self.tab[2*i].priority > self.tab[2*i+1].priority:
            return 2*i
        else:
            return 2*i+1

Heapsort

Om man stoppar in n tal i en heap och sedan hämtar ut dom ett efter ett får man dom sorterade.

from heap import Heap

heap = Heap()
with open("folksagor.txt", encoding = "utf8") as stories:
    for title in stories:
        title = title.strip()
        heap.insert(title, len(title))
    while not heap.isEmpty():
        print(heap.delMax())

Komplexiteten för denna heapsort blir O(n log n):

Vi stoppar först in n element (insert() n gånger) => n*log n
Sen plockar vi ut n element (delMax() n gånger) => n*log n

Bästaförstsökning

Labb 4 behandlar problemet att finna kortaste vägen från söt till sur. Man har då ett problemträd med söt som stamfar/urmoder, på nivån därunder barnen nöt , set , söl osv, på nästa nivå fans barnbarn osv. Om man lägger barnen i en kö kommer man att gå igenom problemträdet nivå för nivå, alltså breddenförst. Om man byter kön mot en stack blir sökningen djupetförst. Med en prioritetskö får man bästaförstsökning, dvs det mest lovande barnet prioriteras och får föda barn.

Exempel 1: Sök billigaste transport från Teknis till Honolulu. All världens resprislistor finns tillgängliga.

Problemträdets objekt innehåller en plats, ett pris och en förälderpekare. Överst i trädet står Teknis med priset noll. Barnen är alla platser man kan komma till med en transport och priset, till exempelT-centralen, 20.00. Man söker en Honolulu-objekt i problemträdet. Med breddenförstsökning får man den resa som har så få transportsteg som möjligt.

Men med bästaförstsökning, där LinkedQ byts ut mot Heap, får man den billigaste resan.

Exempel 2: Sök effektivaste processen för att framställa en önskad substans från en given substans. All världens kemiska reaktioner finns tillgängliga med uppgift om utbytet i procent.

Problemträdets objekt innehåller substansnamn och procenttal. Överst i trädet står utgångssubstansen med procenttalet 100. Barnen är alla substanser man kan framställa med en reaktion och utbytet, till exempel C2H5OH, 96%.

Med en max-prioritetskö får man fram den effektivaste process som leder till målet.

https://xkcd.com/835/