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>

www.000webhost.com