Föreläsning 17 - Prioritetskö, trappa, heapsort

Prioritetskö

En prioritetskö är en abstrakt datastruktur som man kan putta in data i och sedan hämta ut dom igen ur. Hur den skiljer sej från en stack och från en vanlig kö ser man av följande exempel.
    q.put(3);
    q.put(1);
    q.put(2);
    x = q.get(); // x blir 1 
En kö hade skickat tillbaka det först instoppade talet 3; en stack hade skickat tillbaka det senast instoppade talet, 2; prioritetskön skickar tillbaka det bästa talet, 1. I denna prio-kö betraktar vi minsta talet som bäst - vi har en så kallad min-prio-kö. Det finns förstås också max-prio-köer, där det största talet betraktas som bäst.

Prioritetsköer har många användningar. Man kan tänka sej en auktion där budgivarna puttar in sina bud i en max-prio-kö och auktionsförrättaren efter "första, andra, tredje" gör q.get() för att få reda på det vinnande budet. För att han ska veta vem som lagt detta bud behövs en ytterligare parameter i q.put().

    q.put(bud, person); //person är ett objekt med budgivarens namn mm
    winner = q.get();   //budgivaren med högst bud 

Trappa

Den bästa implementeringen av en prioritetskö är en trappa, (eng heap), som är en hakvektor (array) tab tolkad som binärträd. Rotenär tab[1], dess båda söner är tab[2] och tab[3] o.s.v. Allmänt gäller att tab[i] har sönerna tab[2*i] och tab[2*i+1]. Trappvillkoret är att pappa ä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 nya talet är bättre än sin far, byter far och son plats och så fortgår det tills villkoret uppfyllts.

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 bäste son. Det upprepas till villkoret åter gäller.

Både put() och get() har komplexitet log N om trappan har N element. Nackdelen med trappan är man måste bestämma vektorns storlek från början.

Heapsort

Om man puttar 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 (O(N^2)). Och så kan ju en heap användas till andra saker än sortering också.

Interface, behövs det?

I binärträd, hashvektorer och prioritetsköer är nyckeln (det värde man söker efter eller sorterar på) antingen int eller String. I våra exempel kan det verka som om det bara är själva talet eller ordet som sparas i strukturen, men i allmänhet är det förstås en hel massa uppgifter samlade i en post, där exempelvis personnumret är nyckeln. Det finns två sätt att ta hand om posten - ett enkelt och ett intressant! Det är onödigt krångligt att använda interface i det här fallet men i ett annat sammanhang är dom oumbärliga, och det gäller stora programprojekt med flera programmerare inblandade. Två klasser som skrivs av olika programmerare måste kunna anropa varandra och kunna kompileras var för sej. Det åstadkommer man genom att först komma överens om gränssnitten och skriva alla interface-filer.

Bästaförstsökning

Labb 7 behandlar problemet att finna kortaste vägen från FAN till GUD. Man har då ett problemträd med FAN som stamfar, på nivån därunder sönerna MAN, FIN, FAT osv, på nästa nivå fans sonsöner osv. Om man lägger sönerna 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 prio-kö får man bästaförstsökning, dvs den mest lovande sonen prioriteras och får föda söner.

Exempel 1: Sök billigaste transport från Teknis till Honolulu. All världens resprislistor finns tillgängliga.
Problemträdets poster innehåller en plats, ett pris och en faderspekare. Överst i trädet står Teknis med priset noll. Sönerna är alla platser man kan komma till med en transport och priset, till exempel T-centralen, 9.50. Man söker en Honolulupost i problemträdet. Med breddenförstsökning får man den resa som har så få transportsteg som möjligt. Med bästaförstsökning får man den billigaste resan. Detta påstående är inte helt självklart utan man får tänka lite för att inse det.

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 poster innehåller substansnamn och procenttal. Överst i trädet står utgångssubstansen med procenttalet 100. Sönerna är alla substanser man kan framställa med en reaktion och utbytet, till exempel C2H5OH, 96%. Med en max-prio-kö får man fram den effektivaste process som leder till målet.


^ Upp till kurssidan.


Sidansvarig: <efo@nada.kth.se>
Senast ändrad 2 februari 2001
Tekniskt stöd: <webmaster@nada.kth.se>