View All Pages

F11 Prioritetskö, heap, bästaförstsökning, heapsort

 

  • Binära sökträd, repetition
  • Prioritetskö
  • Trappa (heap)
  • Trappsortering (Heapsort)
  • Bästaförstsökning

Binära sökträd - repetition

När man programmerar binärträd brukar man använda noder, som i en länkad lista, men med två pekare: en åt vänster och en åt höger:

    class Node:
       def __init__(self, value):
          self.value = value
          self.left = None
          self.right = None

Man når trädet genom variabeln root som pekar på den översta noden (datalogiska träd har roten uppåt). Rotnodens vänsterpekare pekar på ett mindre binärträd och högerpekaren på ett annat mindre binärträd.

Antalet nivåer i trädet avgör hur många noder det kan innehålla. Ett fullt träd med k nivåer innehåller 2k - 1 noder. Exempel: k=3 i vår bild ger högst 7 noder (det finns plats för två till under 9999). Man kan också säga att ett balanserat träd med n noder har cirka log n nivåer.

I vårt exempelträd ligger små tal till vänster och stora tal till höger. När det är på det sättet har man ett binärt sökträd, så kallat eftersom det går så snabbt att söka reda på en nod i trädet. Låt oss säga att vi söker efter 666. Vår algoritm blir följande

  • Kolla först rottalet.
  • Om talet är 666 har vi funnit vad vi söker.
  • Om talet är större än 666 letar vi vidare efter 666 i högerträdet.
  • Om det är mindre än 666 letar vi vidare i vänsterträdet.
  • ...men om vi når en None-referens finns inte 666 i sökträdet.

Algoritmer som går igenom varje nod i trädet (t ex utskrift) har tidskomplexitet O(n). Men sökningen tar bara O(logn) om trädet är balanserat, därför att vi som mest går igenom trädets höjd.

def finns(p,value):
        letar = True
        while letar:
            if p == None: 
                return False
            if value == p.value: 
                return True
            if value < p.value: 
                p = p.left
            if value > p.value: 
                p = p.right

Rekursiva tankar för binärträd

Fråga: Hur många noder finns i binärträdet? 
Rekursivt svar: En nod mer än i vänsterträdet och högerträdet tillsammans
Basfall: Ett tomt träd har noll noder.

    def antal(p):
        if p == None: 
            return 0
        else:
            return 1 + antal(p.left) + antal(p.right)

Anropet antal(root) ger nu rätt svar!

Sökning i ett binärt sökträd kan implementeras rekursivt om man låter anropet finns(p,value) returnera True ifall ordet finns i det delträd där p är rot.

    def finns(p,value):
        if p == None: 
            return False
        if value == p.value: 
            return True
        if value < p.value: 
            return finns(p.left,value)
        if value > p.value: 
            return finns(p.right,value)

Binärt sökträd som alternativ till hashmap

Ett binärt sökträd kan också ha en key-value struktur och fungera som ett alternativ till hashmap. Man sorterar trädet med avseende på nyckel (key) och varje nod har en värdepekare (value). Det blir inte lika snabb sökning som hashmap men en fördel är att man kan skriva ut nycklarna i sorteringsordning vilket man inte kan i en standard hashimplementation.

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ästatalet, 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

Trappa- prioritetskö

Den bästa implementationen av en prioritetskö är en trappa, (eng heap), som är en lista tolkad som binärträd.

HEAP

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]. Trappvillkoret är att föräldern är bäst, dvs varje tal ligger på två sämre tal.

Ett nytt tal läggs alltid in sist i trappan. Om trappvillkoret 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 upptrappning och kan i värsta fall föra det nya talet hela vägen upp till toppen, alltså tab[1].

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

Både insert och delMax har komplexitet log N om trappan 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

    def __str__(self):
        return "{0}:{1}".format(self.data, self.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():
            data = 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 data.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 trappa och sedan hämtar ut dom ett efter ett får man dom sorterade. Komplexiteten för denna heapsort blir O(N log N), alltså av lika god storleksordning som quicksort. Visserligen är quicksort lite snabbare, men heapsort har inte quicksorts dåliga värstafallsbeteende. och så kan ju en heap användas till andra saker än sortering också.

    heap = Heap()               
    for word in open("folksagor.txt").read().split():
        heap.insert(word, word)
    while not heap.isempty():
        print heap.delMax()

Bästaförstsökning

Labb d3 behandlar problemet att finna kortaste vägen från FAN till GUD. Man har då ett problemträd med FAN som stamfar/urmoder, på nivån därunder barnen MAN, FIN, FAT 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.