Automatically assigned DDC number: 005131
Manually assigned DDC number: 005131

Number of references: 8

Title: Optimal Purely Functional Priority Queues

Author:

Author:

Subject: Gerth StØlting Brodal,Chris Okasaki Optimal Purely Functional Priority Queues

Description: Brodal recently introduced the first implementation of imperative priority queues to support findMin, insert, and meld in O(1) worst-case time, and deleteMin in O(log n) worstcase time. These bounds are asymptotically optimal among all comparison-based priority queues. In this paper, we adapt Brodal's data structure to a purely functional setting. In doing so, we both simplify the data structure and clarify its relationship to the binomial queues of Vuillemin, which support all four operations in O(log n) time. Specifically, we derive our implementation from binomial queues in three steps: first, we reduce the running time of insert to O(1) by eliminating the possibility of cascading links; second, we reduce the running time of findMin to O(1) by adding a global root to hold the minimum element; and finally, we reduce the running time of meld to O(1) by allowing priority queues to contain other priority queues. Each of these steps is expressed using ML-style functors. The last transfo...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1997-05-19

Pubyear: 1996

Format: ps

Identifier: http://citeseer.ist.psu.edu/162069.html

Source: http://www.cs.columbia.edu/~cdo/priority.ps

Language: en

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Relation:

Rights: unrestricted

Graph

<?xml version="1.0" encoding="UTF-8"?>

<references_metadata>

<rec ID="/506989.html" Type="inproceedings" CiteSeer_Book="Workshop on Algorithms and Data Structures" CiteSeer_Volume="" Title="Fast Meldable Priority Queues,">

<identifier Org="ISBN:0521663504" Paper_ID="/506989.html" Extracted="0521663504" DDC="005.7/3" Normalized_DDC="00573" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:0897917855" Paper_ID="/506989.html" Extracted="0897917855" />

<identifier Org="ISBN:0898713668" Paper_ID="/506989.html" Extracted="0898713668" />

<identifier Org="ISBN:1581134959" Paper_ID="/506989.html" Extracted="1581134959" />

<identifier Org="ISBN:1584884355" Paper_ID="/506989.html" Extracted="1584884355" DDC="005.7/3" Normalized_DDC="00573" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:3540223398" Paper_ID="/506989.html" Extracted="3540223398" DDC="518/.1" Normalized_DDC="5181" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:3540602208" Paper_ID="/506989.html" Extracted="3540602208" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:3540614222" Paper_ID="/506989.html" Extracted="3540614222" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:3540652604" Paper_ID="/506989.html" Extracted="3540652604" DDC="004" Normalized_DDC="004" Normalized_Weight="0.16666666666666666" />

</rec>

<rec ID="/184048.html" Type="inproceedings" CiteSeer_Book="SODA ACMSIAM Symposium on Discrete Algorithms A Conference on Theoretical and Experimental Analysis of Discrete Algorithms" CiteSeer_Volume="" Title="Confluently Persistent Deques via Data Structural Bootstrapping,">

<identifier Org="ISBN:0521663504" Paper_ID="/184048.html" Extracted="0521663504" DDC="005.7/3" Normalized_DDC="00573" Normalized_Weight="0.2" />

<identifier Org="ISBN:0780331214" Paper_ID="/184048.html" Extracted="0780331214" />

<identifier Org="ISBN:0849326494" Paper_ID="/184048.html" Extracted="0849326494" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.2" />

<identifier Org="ISBN:0897919068" Paper_ID="/184048.html" Extracted="0897919068" DDC="005.2/75" Normalized_DDC="005275" Normalized_Weight="0.2" />

<identifier Org="ISBN:0898713137" Paper_ID="/184048.html" Extracted="0898713137" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.2" />

<identifier Org="ISBN:1880446480" Paper_ID="/184048.html" Extracted="1880446480" />

<identifier Org="ISBN:3540648240" Paper_ID="/184048.html" Extracted="3540648240" DDC="004" Normalized_DDC="004" Normalized_Weight="0.2" />

</rec>

<rec ID="/580108.html" Type="inproceedings" CiteSeer_Book="European Symposium on Programming" CiteSeer_Volume="" Title="{A} Semantics for Higher-order Functors,">

<identifier Org="ISBN:0262162288" Paper_ID="/580108.html" Extracted="0262162288" DDC="005.13" Normalized_DDC="00513" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0262631814" Paper_ID="/580108.html" Extracted="0262631814" DDC="005.13/3" Normalized_DDC="005133" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0387948759" Paper_ID="/580108.html" Extracted="0387948759" DDC="005.2" Normalized_DDC="0052" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0521663504" Paper_ID="/580108.html" Extracted="0521663504" DDC="005.7/3" Normalized_DDC="00573" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0521771641" Paper_ID="/580108.html" Extracted="0521771641" DDC="005.3" Normalized_DDC="0053" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:084931240X" Paper_ID="/580108.html" Extracted="084931240X" DDC="005.4/53" Normalized_DDC="005453" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:0897916972" Paper_ID="/580108.html" Extracted="0897916972" />

<identifier Org="ISBN:0897919068" Paper_ID="/580108.html" Extracted="0897919068" DDC="005.2/75" Normalized_DDC="005275" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:1581136285" Paper_ID="/580108.html" Extracted="1581136285" />

<identifier Org="ISBN:1586031724" Paper_ID="/580108.html" Extracted="1586031724" DDC="005.101" Normalized_DDC="005101" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540421963" Paper_ID="/580108.html" Extracted="3540421963" DDC="005.4/53" Normalized_DDC="005453" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540440445" Paper_ID="/580108.html" Extracted="3540440445" DDC="005.13/1" Normalized_DDC="005131" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540578803" Paper_ID="/580108.html" Extracted="3540578803" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540584501" Paper_ID="/580108.html" Extracted="3540584501" DDC="004/.01/5113" Normalized_DDC="004015113" Normalized_Weight="0.07692307692307693" />

<identifier Org="ISBN:3540679588" Paper_ID="/580108.html" Extracted="3540679588" DDC="005.13" Normalized_DDC="00513" Normalized_Weight="0.07692307692307693" />

</rec>

<rec ID="/27428.html" Type="inproceedings" CiteSeer_Book="Functional Programming Languages and Computer Architecture" CiteSeer_Volume="" Title="Purely Functional Random-Access Lists,">

<identifier Org="ISBN:052156543X" Paper_ID="/27428.html" Extracted="052156543X" DDC="005.13/3" Normalized_DDC="005133" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:0521663504" Paper_ID="/27428.html" Extracted="0521663504" DDC="005.7/3" Normalized_DDC="00573" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:0897917707" Paper_ID="/27428.html" Extracted="0897917707" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:1584884355" Paper_ID="/27428.html" Extracted="1584884355" DDC="005.7/3" Normalized_DDC="00573" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:3540401903" Paper_ID="/27428.html" Extracted="3540401903" DDC="005.13" Normalized_DDC="00513" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:3540655271" Paper_ID="/27428.html" Extracted="3540655271" DDC="005.13/1" Normalized_DDC="005131" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:3540921818" Paper_ID="/27428.html" Extracted="3540921818" />

</rec>

<rec ID="/158610.html" Type="article" CiteSeer_Book="Journal of Functional Programming" CiteSeer_Volume="5" Title="Simple and Efficient Purely Functional Queues and Deques,">

<identifier Org="ISBN:0521663504" Paper_ID="/158610.html" Extracted="0521663504" DDC="005.7/3" Normalized_DDC="00573" Normalized_Weight="0.125" />

<identifier Org="ISBN:0780331214" Paper_ID="/158610.html" Extracted="0780331214" />

<identifier Org="ISBN:0897917189" Paper_ID="/158610.html" Extracted="0897917189" DDC="004" Normalized_DDC="004" Normalized_Weight="0.125" />

<identifier Org="ISBN:0897917707" Paper_ID="/158610.html" Extracted="0897917707" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.125" />

<identifier Org="ISBN:0897919068" Paper_ID="/158610.html" Extracted="0897919068" DDC="005.2/75" Normalized_DDC="005275" Normalized_Weight="0.125" />

<identifier Org="ISBN:1584884355" Paper_ID="/158610.html" Extracted="1584884355" DDC="005.7/3" Normalized_DDC="00573" Normalized_Weight="0.125" />

<identifier Org="ISBN:3540433635" Paper_ID="/158610.html" Extracted="3540433635" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.125" />

<identifier Org="ISBN:3540438572" Paper_ID="/158610.html" Extracted="3540438572" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.125" />

<identifier Org="ISBN:3540648496" Paper_ID="/158610.html" Extracted="3540648496" DDC="005.13" Normalized_DDC="00513" Normalized_Weight="0.125" />

</rec>

<rec ID="/175796.html" Type="inproceedings" CiteSeer_Book="Proceedings of the ACM SIGPLAN International Conference on Functional Programming ICFP 96" CiteSeer_Volume="" Title="The Role of Lazy Evaluation in Amortized Data Structures,">

<identifier Org="ISBN:0521663504" Paper_ID="/175796.html" Extracted="0521663504" DDC="005.7/3" Normalized_DDC="00573" Normalized_Weight="0.2" />

<identifier Org="ISBN:0849326494" Paper_ID="/175796.html" Extracted="0849326494" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.2" />

<identifier Org="ISBN:0897917707" Paper_ID="/175796.html" Extracted="0897917707" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.2" />

<identifier Org="ISBN:0897919068" Paper_ID="/175796.html" Extracted="0897919068" DDC="005.2/75" Normalized_DDC="005275" Normalized_Weight="0.2" />

<identifier Org="ISBN:0898714907" Paper_ID="/175796.html" Extracted="0898714907" />

<identifier Org="ISBN:3540648496" Paper_ID="/175796.html" Extracted="3540648496" DDC="005.13" Normalized_DDC="00513" Normalized_Weight="0.2" />

</rec>

<rec ID="/694031.html" Type="misc" CiteSeer_Book="" CiteSeer_Volume="" Title="Data Structures and Amortized Complexity in a Functional Setting,">

<identifier Org="ISBN:0521663504" Paper_ID="/694031.html" Extracted="0521663504" DDC="005.7/3" Normalized_DDC="00573" Normalized_Weight="0.5" />

<identifier Org="ISBN:0897917707" Paper_ID="/694031.html" Extracted="0897917707" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.5" />

</rec>

<rec ID="/28024.html" Type="inproceedings" CiteSeer_Book="IFIP TC 2 Working Conference on Programming Concepts and Methods Sea of Galilee Israel" CiteSeer_Volume="" Title="Linear types can change the world!,">

<identifier Org="ISBN:0521608570" Paper_ID="/28024.html" Extracted="0521608570" DDC="511.36" Normalized_DDC="51136" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540006222" Paper_ID="/28024.html" Extracted="3540006222" DDC="005.8/2" Normalized_DDC="00582" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540208135" Paper_ID="/28024.html" Extracted="3540208135" DDC="004" Normalized_DDC="004" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:354022159X" Paper_ID="/28024.html" Extracted="354022159X" DDC="005.1/1" Normalized_DDC="00511" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540255931" Paper_ID="/28024.html" Extracted="3540255931" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540291075" Paper_ID="/28024.html" Extracted="3540291075" DDC="004.24" Normalized_DDC="00424" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540403256" Paper_ID="/28024.html" Extracted="3540403256" DDC="005.13" Normalized_DDC="00513" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540405313" Paper_ID="/28024.html" Extracted="3540405313" DDC="005.1/17" Normalized_DDC="005117" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540433635" Paper_ID="/28024.html" Extracted="3540433635" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540442405" Paper_ID="/28024.html" Extracted="3540442405" DDC="005.1/01/5113" Normalized_DDC="0051015113" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540543961" Paper_ID="/28024.html" Extracted="3540543961" DDC="005.13" Normalized_DDC="00513" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540575294" Paper_ID="/28024.html" Extracted="3540575294" DDC="004" Normalized_DDC="004" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540601007" Paper_ID="/28024.html" Extracted="3540601007" DDC="005.74" Normalized_DDC="00574" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:354060359X" Paper_ID="/28024.html" Extracted="354060359X" DDC="005.13" Normalized_DDC="00513" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540649522" Paper_ID="/28024.html" Extracted="3540649522" DDC="004/.35" Normalized_DDC="00435" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:354066954X" Paper_ID="/28024.html" Extracted="354066954X" DDC="005.1/17" Normalized_DDC="005117" Normalized_Weight="0.058823529411764705" />

<identifier Org="ISBN:3540672575" Paper_ID="/28024.html" Extracted="3540672575" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.058823529411764705" />

</rec>

<rec ID="SELF" Type="SELF" CiteSeer_Book="SELF" CiteSeer_Volume="SELF" Title="Optimal Purely Functional Priority Queues">

<identifier Org="ISBN:0521663504" Paper_ID="SELF" Extracted="0521663504" DDC="005.7/3" Normalized_DDC="00573" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:0849326494" Paper_ID="SELF" Extracted="0849326494" DDC="511.3" Normalized_DDC="5113" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:0897917707" Paper_ID="SELF" Extracted="0897917707" DDC="005.1" Normalized_DDC="0051" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:0897917855" Paper_ID="SELF" Extracted="0897917855" />

<identifier Org="ISBN:1584884355" Paper_ID="SELF" Extracted="1584884355" DDC="005.7/3" Normalized_DDC="00573" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:3540000100" Paper_ID="SELF" Extracted="3540000100" DDC="006.3" Normalized_DDC="0063" Normalized_Weight="0.16666666666666666" />

<identifier Org="ISBN:3540655271" Paper_ID="SELF" Extracted="3540655271" DDC="005.13/1" Normalized_DDC="005131" Normalized_Weight="0.16666666666666666" />

</rec>

</references_metadata>