"Fast and small resizable arrays",
Dr. Dobb's Journal, July 2001, pp. 132-134.
Brodnik, A., Carlsson, S., Munro, J.I., Sedgewick, R., Demaine, E., "Resizable arrays in optimal time and space, Proc 6th Inter Workshop on Algorithms and Data Structures, August 1999, vol. 1663 of Lecture Notes in Computer Science.
see also: Sitarski, E., "HATs: Hashed Array Trees," Dr. Dobb's Journal, September 1996
|132 ;;Quote: HAT structure is a two level array; all blocks of a power of two; only top block and last bottom block may be partial|
|133 ;;Quote: HAT structure can grow and shrink at the beginning; for double-ended queues and deques|
|133 ;;Quote: avoid resizing of HAT structure by doubling size of low-level blocks; 2 sqrt n wasted space; optimal
ThesaHelp: references c-d (337 items)
Topic: arrays (57 items)
Group: data structures (12 topics, 275 quotes)
Group: sequences (7 topics, 96 quotes)