WFRF:(Munro Ian)
Search: WFRF:(Munro Ian) > Resizable arrays in...
- 9 of 17
- Previous record
- Next record
- To hitlist
- Brodnik, Andrej (author)
Resizable arrays in optimal time and space
- Article/chapterEnglish1999
Publisher, publication year, extent ...
- 2002-07-18
- Berlin :Encyclopedia of Global Archaeology/Springer Verlag,1999
- electronicrdacarrier
Numbers
- LIBRIS-ID:oai:DiVA.org:ltu-26832
- https://urn.kb.se/resolve?urn=urn:nbn:se:ltu:diva-26832URI
- https://doi.org/10.1007/3-540-48447-7DOI
Supplementary language notes
- Language:English
- Summary in:English
Part of subdatabase
- SwePubSwePub
Classification
Notes
- Godkänd; 1999; 20080313 (ysko)
- We present simple, practical and efficient data structures for the fundamental problem of maintaining a resizable one-dimensional array, A[l..l + n - 1], of fixed-size elements, as elements are added to or removed from one or both ends. Our structures also support access to the element in position i. All operations are performed in constant time. The extra space (i.e., the space used past storing the n current elements) is O(√n) at any point in time. This is shown to be within a constant factor of optimal, even if there are no constraints on the time. If desired, each memory block can be made to have size 2k - c for a specified constant c, and hence the scheme works effectively with the buddy system. The data structures can be used to solve a variety of problems with optimal bounds on time and extra storage. These include stacks, queues, randomized queues, priority queues, and deques.
Subject headings and genre
- NATURVETENSKAP Data- och informationsvetenskap Datavetenskap hsv//swe
- NATURAL SCIENCES Computer and Information Sciences Computer Sciences hsv//eng
- Dependable Communication and Computation Systems
- Kommunikations- och beräkningssystem
Added entries (persons, corporate bodies, meetings, titles ...)
- Carlsson, SvanteLuleå tekniska universitet (author)
- Demaine, Erik D.Department of Computer Science, University of Waterloo, Ontario (author)
- Munro, J. IanDepartment of Computer Science, University of Waterloo, Ontario (author)
- Sedgewick, RobertDepartment of Computer Science, Princeton University (author)
- Luleå tekniska universitetDepartment of Computer Science, University of Waterloo, Ontario (creator_code:org_t)
Related titles
- In:Algorithms and Data StructuresBerlin : Encyclopedia of Global Archaeology/Springer Verlag, s. 37-483540662790
Internet link
Find in a library
- Algorithms and Data Structures (Search for host publication in LIBRIS)
To the university's database
- 9 of 17
- Previous record
- Next record
- To hitlist
Find more in SwePub
- By the author/editor
- Brodnik, Andrej
- Carlsson, Svante
- Demaine, Erik D.
- Munro, J. Ian
- Sedgewick, Rober ...
- About the subject
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- and Computer Science ...
- Articles in the publication
- Algorithms and D ...
- By the university
- Luleå University of Technology
Search outside SwePub
- Extend your search to:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - National Library Systems
- LIBRIS.kb.se
