Academic
Publications
Purely functional representations of catenable sorted lists

Purely functional representations of catenable sorted lists,10.1145/237814.237865,Haim Kaplanl,Robert Endre Tarjan

Purely functional representations of catenable sorted lists   (Citations: 27)
BibTex | RIS | RefWorks Download
The power of purely functional programming in the construction of data structures has receivedmuch attention, not only because functional languages have many desirable properties,but because structures built purely functionally are automatically fully persistent: any andall versions of a structure can coexist indefinitely. Recent results illustrate the surprisingpower of pure functionality. One such result was the development of a representation ofdouble-ended queues with catenation that...
Conference: ACM Symposium on Theory of Computing - STOC , pp. 202-211, 1996
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Our algorithm uses 2-3 finger trees [6], [23] to maintain the list of leaves in each subtree...
    • ...These require no layout decision, and can be made into a singleton finger tree of size 1 in constant time [23]...
    • ...Complexity: Kaplan and Tarjan [23] describe split and append (þþ) operations on 2-3 finger trees...
    • ...The total complexity is bounded by the shared complexity of lines 5, 6, and 10. Since the sum of the logarithms is maximized when all the dis are equal [23], the complexity is thus Oð P i�j qj log diÞ¼Oðjqjlogð jpj jqj ÞÞ...

    Balaji Venkatachalamet al. Untangling Tanglegrams: Comparing Trees by Their Drawings

    • ...For further examples of structures that use the regular system, see [8,9]...
    • ...This approach was used in [14] for constructing catenable deques, in [9] for constructing catenable finger search trees, and in [8] for constructing meldable priority queues...

    Amr Elmasryet al. Strictly-Regular Number System and Data Structures

    • ...For each internal node, we not only decide the optimal order for its children, we also construct a 2-3 finger tree , an ordered search tree with fast split and append operations [17]...
    • ...These require no layout decision, and can be made into a singleton finger tree of size 1 in constant time [17]...
    • ...Complexity Kaplan and Tarjan [17] describe split and append (+ +) operations on 2-3 finger trees...
    • ...The total complexity is bounded by the shared complexity of lines 6, 7 and 11. Since the sum of the logarithms is maximized when all the dis are equal [17], the complexity is thus O �P...

    Balaji Venkatachalamet al. Untangling Tanglegrams: Comparing Trees by Their Drawings

    • ...Kaplan and Tarjan (1996) dened two functional data structures with the same time bounds as here, except that their bounds are worst case, and do not require laziness...

    Ralf Hinzeet al. Finger trees: a simple general-purpose data structure

    • ...Since the seminal paper of Driscoll et al. [14], there has been considerable development of persistent data structures [21, 22, 23, 24]...

    Sung Eun Baeet al. Improved Algorithms for the K-Maximum Subarray Problem

Sort by: