heapq — Algoritm för heap-köer

Källkod: Lib/heapq.py

Denna modul ger en implementation av heap-köalgoritmen, även känd som prioritetsköalgoritmen.

Min-heaps är binära träd där varje föräldernod har ett värde som är mindre än eller lika med något av dess barn. Vi hänvisar till detta villkor som heap-invariant.

För min-heaps använder den här implementationen listor för vilka heap[k] <= heap[2*k+1] och heap[k] <= heap[2*k+2] för alla k för vilka de jämförda elementen finns. Elementen räknas från noll. Den intressanta egenskapen hos en min-heap är att dess minsta element alltid är roten, heap[0].

Max-heaps uppfyller den omvända invarianten: varje överordnad nod har ett värde som är större än något av dess barn. Dessa implementeras som listor för vilka maxheap[2*k+1] <= maxheap[k] och maxheap[2*k+2] <= maxheap[k] för alla k för vilka de jämförda elementen finns. Roten, maxheap[0], innehåller det största elementet; heap.sort(reverse=True) upprätthåller max-heap-invariansen.

API:et heapq skiljer sig från lärobokens heap-algoritmer i två avseenden: (a) Vi använder nollbaserad indexering. Detta gör förhållandet mellan indexet för en nod och indexen för dess barn något mindre uppenbart, men är mer lämpligt eftersom Python använder nollbaserad indexering. (b) Läroböcker fokuserar ofta på max-heaps på grund av deras lämplighet för in-place-sortering. Vår implementation föredrar min-heaps eftersom de bättre motsvarar Python lists.

Dessa två aspekter gör det möjligt att se högen som en vanlig Python-lista utan överraskningar: heap[0] är det minsta objektet, och heap.sort() upprätthåller heap-invarianten!

Liksom list.sort() använder denna implementation endast operatorn < för jämförelser, för både min-heaps och max-heaps.

I API:et nedan, och i den här dokumentationen, avser den okvalificerade termen heap i allmänhet en min-heap. API:et för max-heaps namnges med suffixet _max.

För att skapa en hög använder du en lista som initierats som [], eller omvandlar en befintlig lista till en min- eller maxhög med hjälp av funktionerna heapify() respektive heapify_max().

Följande funktioner finns för min-högar:

heapq.heappush(heap, item)

Skjut upp värdet item på heap, med bibehållen min-heap-invariant.

heapq.heappop(heap)

Plockar ut och returnerar det minsta objektet från högen, med bibehållen min-heap-invariant. Om högen är tom, uppstår IndexError. För att komma åt det minsta objektet utan att poppa det, använd heap[0].

heapq.heappushpop(heap, item)

Skjut objekt på högen, sedan popa upp och returnera det minsta objektet från högen. Den kombinerade åtgärden körs mer effektivt än heappush() följt av ett separat anrop till heappop().

heapq.heapify(x)

Omvandla listan x till en min-heap, på plats, i linjär tid.

heapq.heapreplace(heap, item)

Popa och returnera det minsta objektet från heapen, och även pusha det nya objektet. Stapelns storlek ändras inte. Om högen är tom, uppstår IndexError.

Denna operation i ett steg är mer effektiv än heappop() följt av heappush() och kan vara mer lämplig när man använder en heap med fast storlek. Kombinationen pop/push returnerar alltid ett element från högen och ersätter det med item.

Det returnerade värdet kan vara större än det tillagda objektet. Om detta inte är önskvärt kan du överväga att använda heappushpop() istället. Dess push/pop-kombination returnerar det mindre av de två värdena och lämnar det större värdet på högen.

För max-heaps finns följande funktioner:

heapq.heapify_max(x)

Omvandla listan x till en max-heap, på plats, i linjär tid.

Tillagd i version 3.14.

heapq.heappush_max(heap, item)

Skjut upp värdet item till max-heap heap, med bibehållen max-heap-invariant.

Tillagd i version 3.14.

heapq.heappop_max(heap)

Plockar ut och returnerar det största objektet från max-heap heap, med bibehållen max-heap-invariant. Om max-heap är tom, uppstår IndexError. För att komma åt det största objektet utan att poppa det, använd maxheap[0].

Tillagd i version 3.14.

heapq.heappushpop_max(heap, item)

Tryck item på max-heap heap, sedan popa och returnera det största objektet från heap. Den kombinerade åtgärden körs mer effektivt än heappush_max() följt av ett separat anrop till heappop_max().

Tillagd i version 3.14.

heapq.heapreplace_max(heap, item)

Popa och returnera det största objektet från max-heap heap och pusha även det nya objektet. Storleken på max-heap ändras inte. Om max-heapen är tom, IndexError tas upp.

Det returnerade värdet kan vara mindre än det tillagda objektet. Se den analoga funktionen heapreplace() för detaljerade användningsanvisningar.

Tillagd i version 3.14.

Modulen erbjuder också tre allmänna funktioner baserade på heaps.

heapq.merge(*iterables, key=None, reverse=False)

Sammanfogar flera sorterade indata till en enda sorterad utdata (t.ex. sammanfogar tidsstämplade poster från flera loggfiler). Returnerar en iterator över de sorterade värdena.

Liknar sorted(itertools.chain(*iterables)) men returnerar en iterabel, drar inte in data i minnet på en gång och förutsätter att var och en av inmatningsströmmarna redan är sorterade (minsta till största).

Har två valfria argument som måste anges som nyckelordsargument.

key anger en key function med ett argument som används för att extrahera en jämförelsenyckel från varje inmatat element. Standardvärdet är None (jämför elementen direkt).

reverse är ett booleanskt värde. Om värdet är satt till True slås inmatningselementen samman som om varje jämförelse var omvänd. För att uppnå ett beteende som liknar sorted(itertools.chain(*iterables), reverse=True) måste alla iterables sorteras från största till minsta.

Ändrad i version 3.5: Lagt till de valfria parametrarna key och reverse.

heapq.nlargest(n, iterable, key=None)

Returnerar en lista med de n största elementen från datasetet som definieras av iterable. key, om den anges, specificerar en funktion med ett argument som används för att extrahera en jämförelsenyckel från varje element i iterable (t.ex. key=str.lower). Likvärdig med: sorted(iterable, key=key, reverse=True)[:n].

heapq.nsmallest(n, iterable, key=None)

Returnerar en lista med de n minsta elementen från datasetet som definieras av iterable. key, om det anges, specificerar en funktion med ett argument som används för att extrahera en jämförelsenyckel från varje element i iterable (till exempel key=str.lower). Likvärdig med: sorted(iterable, key=key)[:n].

De två sistnämnda funktionerna fungerar bäst för mindre värden på n. För större värden är det mer effektivt att använda funktionen sorted(). När n==1 är det också mer effektivt att använda de inbyggda funktionerna min() och max(). Om det krävs upprepad användning av dessa funktioner bör du överväga att göra om iterabeln till en faktisk hög.

Grundläggande exempel

En heapsort kan implementeras genom att lägga alla värden på en hög och sedan plocka bort de minsta värdena ett i taget:

>>> def heapsort(iterable):
...     h = []
...     for value in iterable:
...         heappush(h, value)
...     return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Detta liknar sorted(iterable), men till skillnad från sorted() är denna implementation inte stabil.

Heap-element kan vara tupler. Detta är användbart för att tilldela jämförelsevärden (t.ex. uppgiftsprioriteringar) vid sidan av den huvudsakliga post som spåras:

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')

Anvisningar för implementering av prioriterad kö

En prioritetskö är en vanlig användning för en hög, och den innebär flera implementeringsutmaningar:

  • Sorteringsstabilitet: Hur får man två uppgifter med samma prioritet att returneras i den ordning de ursprungligen lades till?

  • Tupeljämförelsen bryts för (prioritet, uppgift)-par om prioriteringarna är lika och uppgifterna inte har en standardjämförelseordning.

  • Om prioriteten för en uppgift ändras, hur flyttar du den till en ny position i högen?

  • Eller om en väntande uppgift behöver raderas, hur hittar du den och tar bort den från kön?

En lösning på de två första utmaningarna är att lagra poster som en lista med tre element, inklusive prioriteten, ett antal poster och uppgiften. Entry count fungerar som en tie-breaker så att två uppgifter med samma prioritet returneras i den ordning de lades till. Och eftersom ingen posträkning är den andra lik kommer tuple-jämförelsen aldrig att försöka jämföra två uppgifter direkt.

En annan lösning på problemet med icke jämförbara uppgifter är att skapa en omslutande klass som ignorerar uppgiftsobjektet och endast jämför prioritetsfältet:

from dataclasses import dataclass, field
from typing import Any

@dataclass(order=True)
class PrioritizedItem:
    priority: int
    item: Any=field(compare=False)

De återstående utmaningarna handlar om att hitta en väntande uppgift och ändra dess prioritet eller ta bort den helt och hållet. Att hitta en uppgift kan göras med en ordbok som pekar på en post i kön.

Att ta bort posten eller ändra dess prioritet är svårare eftersom det skulle bryta mot invarianterna för heapstrukturen. En möjlig lösning är därför att markera posten som borttagen och lägga till en ny post med den reviderade prioriteten:

pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>'      # placeholder for a removed task
counter = itertools.count()     # unique sequence count

def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')

Teori

Heaps är matriser för vilka a[k] <= a[2*k+1] och a[k] <= a[2*k+2] för alla k, räknat med element från 0. För jämförelsens skull anses icke-existerande element vara oändliga. Den intressanta egenskapen hos en hög är att a[0] alltid är dess minsta element.

Den märkliga invarianten ovan är tänkt att vara en effektiv minnesrepresentation för en turnering. Siffrorna nedan är k, inte a[k]:

                               0

              1                                 2

      3               4                5               6

  7       8       9       10      11      12      13      14

15 16   17 18   19 20   21 22   23 24   25 26   27 28   29 30

I trädet ovan toppar varje cell k 2*k+1 och 2*k+2. I en vanlig binär turnering som vi ser i sport är varje cell vinnare över de två celler den toppar, och vi kan spåra vinnaren nedåt i trädet för att se alla motståndare han/hon hade. I många datortillämpningar av sådana turneringar behöver vi dock inte spåra en vinnares historia. För att vara mer minneseffektiva försöker vi ersätta en vinnare med något annat på en lägre nivå, och regeln blir att en cell och de två celler som den toppar innehåller tre olika saker, men att den översta cellen ”vinner” över de två toppade cellerna.

Om denna invariant i högen är skyddad hela tiden är index 0 helt klart den övergripande vinnaren. Det enklaste algoritmiska sättet att ta bort det och hitta ”nästa” vinnare är att flytta någon förlorare (låt oss säga cell 30 i diagrammet ovan) till 0-positionen och sedan perkolera denna nya 0 nedåt i trädet och utbyta värden tills invariansen återställs. Detta är tydligt logaritmiskt på det totala antalet objekt i trädet. Genom att iterera över alla objekt får du en O(n log n) sortering.

En trevlig egenskap hos denna sortering är att du effektivt kan infoga nya element medan sorteringen pågår, förutsatt att de infogade elementen inte är ”bättre” än det sista 0:e elementet du extraherade. Detta är särskilt användbart i simuleringssammanhang, där trädet innehåller alla inkommande händelser och ”win”-villkoret innebär den minsta schemalagda tiden. När en händelse schemalägger andra händelser för utförande schemaläggs de in i framtiden, så att de lätt kan hamna i högen. Så en hög är en bra struktur för att implementera schemaläggare (det är vad jag använde för min MIDI-sequencer :-).

Olika strukturer för att implementera schemaläggare har studerats ingående, och heaps är bra för detta, eftersom de är rimligt snabba, hastigheten är nästan konstant och det värsta fallet inte skiljer sig mycket från det genomsnittliga fallet. Det finns dock andra representationer som är mer effektiva överlag, men de värsta fallen kan vara fruktansvärda.

Heaps är också mycket användbara i stora disksorteringar. Du vet säkert alla att en stor sortering innebär att man producerar ”körningar” (som är försorterade sekvenser, vars storlek vanligtvis är relaterad till mängden CPU-minne), följt av ett sammanslagningspass för dessa körningar, vilken sammanslagning ofta är mycket smart organiserad [1]. Det är mycket viktigt att den inledande sorteringen ger så långa körningar som möjligt. Turneringar är ett bra sätt att uppnå detta. Om du använder allt minne som finns tillgängligt för att hålla en turnering, ersätter och perkolerar objekt som råkar passa den aktuella körningen, kommer du att producera körningar som är dubbelt så stora som minnet för slumpmässig inmatning, och mycket bättre för inmatning som är luddigt ordnad.

Dessutom, om du matar ut det 0:e objektet på disken och får en inmatning som inte får plats i den aktuella turneringen (eftersom värdet ”vinner” över det senaste utmatningsvärdet), kan det inte få plats i högen, så storleken på högen minskar. Det frigjorda minnet kan på ett smart sätt omedelbart återanvändas för att successivt bygga upp en andra hög, som växer i exakt samma takt som den första högen smälter. När den första högen helt försvinner byter man hög och startar en ny körning. Smart och ganska effektivt!

Kort sagt, heaps är användbara minnesstrukturer att känna till. Jag använder dem i några program, och jag tror att det är bra att ha en ”heap”-modul :-)

Fotnoter