Kandidatspeciale af Claus Jensen
Prioritetskøer er en gammel og velstuderet datastruktur, for hvilket der allerede er udført meget teoretisk og praktisk arbejde. En prioritetskø kan realiseres på mange måder, nogle af de mest almindelige datastrukturer, der bliver brugt til dette, er binære hobe og binomiale hobe.
I dette speciale studeres prioritetskøers effektivitet i tre separate artikler.
I den første artikel, som studerer den praktiske effektivitet af prioritetskøer (An extended truth about heaps) bliver en række alternative implementeringer af minimumsplads-d-vejs hobe studeret. Der er blevet foretaget en eksperimentel evaluering af implementeringerne og C++ standardbibliotekets hob. Implementeringerne er blevet evalueret ved brugen af forskellige typer af inddata og forskellige ordensfunktioner. Resultatet at eksperimenterne er, at ingen enkelt hob-ordningsstrategi har den bedste ydeevne for alle de forskellige typer af inddata og ordensfunktioner, men at en bottom-up hobordningsstrategi har en god ydeevne for de flest typer af inddata og ordensfunktioner.
I den anden artikel om den praktiske effektivitet af prioritetskøer (An experimental evaluation of navigation piles) bliver tre forskellige implementeringer af navigation pile studeret. Implementeringernes effektivitet bliver eksperimentelt evalueret sammen med to forskellige implementeringer af binære hobe; igen foretages eksperimenterne med forskellige typer af inddata og ordensfunktioner. Udover dette bruges flere forskellige operationsgenererende modeller til at udvide eksperimenterne. Eksperimenterne viser, at når elementflytninger er dyre, kan navigation pile være et alternativ til binære hobe. Udover studiet af navigation pile datastrukturens praktiske effektivitet, introduceres first-ancestor teknikken og en ny og simplere måde til at transformere en statisk navigation pile til en dynamisk navigation pile.
I den tredje artikel (A framework for speeding up priority-queue operations) bliver den teoretiske effektivitet af prioritetskøer studeret, og et framework til at reducere antallet af elementsammenligninger i forbindelse med udførelsen af prioritetskø-operationerne bliver introduceret. Ved at bruge dette framework opnås en prioritetskø, der garanterer værstefaldsomkostninger på O(1) pr. find-min og insert operation; og en værstefaldsomkostning på O(log n) med maximalt log n + O(1) elementsammenligner pr. delete-min og delete operation. Her angiver n antallet af elementer, der er indeholdt i datastrukturen før en given operation udføres, og log n er lig med maksimum af {1, log2 n}. Yderligere præsenteres en prioritetskø, der udover de ovennævnte operationer tilbyder operationen decrease (også kaldet decrease-key). Denne prioritetskø opnår en værstefaldsomkostning på O(1) pr. find-min, insert og decrease operation; og en værstefaldsomkostning på O(log n) med maximalt log n + O(log log n) elementsammenligner pr. delete-min og delete operation.
Det er muligt at downloade følgende filer: