Menu
Is there a name for the following data structure? Are there papers and citations available?
One way to implement an efficient set abstract data type is to have a collection of sorted arrays, where each array has a unique power-of-2 size.
For example, a set of 13 elements {1, 2, ..., 13} can be represented by this collection of sorted arrays: {[5], [2, 3, 9, 13], [1, 4, 6, 7, 8, 10, 11, 12]}.
In general, the arrays that are in the collection have sizes that correspond to the 1 bits in the binary representation of the size of the set. The data structure is efficient because insertion can be performed in amortized O(1) time, and search can be performed in O((log n)2) time (which is better than linear search). Also, it uses only O(log n) space overhead for pointers, unlike balanced binary trees and B-trees which use O(n) extra space for pointers. Thus, almost all the space is used for payload data.
I've looked at Wikipedia's list of data structures but didn't find a match. It's true that the book Introduction to Algorithms ("CLRS") describes this data structure as a homework problem in the "Amortized Analysis" section, but because it's a question rather than an example, the book doesn't say much about it.
460
A sorted array is an array data structure in which each element is sorted in numerical, alphabetical, or some other order, and placed at equally spaced addresses in computer memory. It is typically used in computer science to implement static lookup tables to hold multiple values which have the same data type.
What Are Arrays in Data Structures? An array is a linear data structure that collects elements of the same data type and stores them in contiguous and adjacent memory locations. Arrays work on an index system starting from 0 to (n-1), where n is the size of the array.
Given an array of n elements, where each element is at most k away from its target position, devise an algorithm that sorts in O(n log k) time. For example, let us consider k is 2, an element at index 7 in the sorted array, can be at indexes 5, 6, 7, 8, 9 in the given array.
Merge Sort works similar to quick Sort where one uses a divide and conquer algorithm to sort the array of elements. It uses a key process Merge(myarr, left,m, right) to combine the sub-arrays divided using m position element.
A similar idea dates back at least to Jean Vuillemin's original publication on binomial heaps in the April 1978 issue of CACM. I would expect the paper that introduced this data structure to cite or be cited by Vuillemin, but none of the papers on the "references" and "cited by" lists look promising.
If I were you, I would ask cstheory and then write to CLRS, but given the suboptimal bounds and lack of deletion, I don't expect anything to turn up unless the succinct data structure community took an interest at some point.
Is there something in particular you wanted to know?
71
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
