Efficient Sorted Data Structure in JavaScript

Question

I'm looking for a way to take a bunch of JSON objects and store them in a data structure that allows both fast lookup and also fast manipulation which might change the position in the structure for a particular object.

An example object:

{
    name: 'Bill',
    dob: '2014-05-17T15:31:00Z'
}

Given a sort by name ascending and dob descending, how would you go about storing the objects so that if I have a new object to insert, I know very quickly where in the data structure to place it so that the object's position is sorted against the other objects?

In terms of lookup, I need to be able to say, "Give me the object at index 12" and it pulls it quickly.

I can modify the objects to include data that would be helpful such as storing current index position etc in a property e.g. {_indexData: {someNumber: 23, someNeighbour: Object}} although I would prefer not to.

I have looked at b-trees and think this is likely to be the answer but was unsure how to implement using multiple sort arguments (name: ascending, dob: descending) unless I implemented two trees?

Does anyone have a good way to solve this?

Assuming you don't add an index property, how would you know what index to use when fetching records? — Johan, Oct 02 '14 at 08:08
@Johan At point of insertion I think I'd need the index it was given so if I insert a, c and b, a === index 0, b === 1 and c === 2. Alternatively after insert if the structure can be flatened to an array I can do an indexOf() to find the current index although that will use a linear search so not be that efficient. — Rob Evans, Oct 02 '14 at 09:21
If you're really concerned about lookup complexity I think that a plain object with index as keys will be faster than an `indexOf`, `for` etc. on an array. — Johan, Oct 02 '14 at 09:24

score 1 · Answer 1 · edited May 23 '17 at 11:57

First thing you need to do is store all the objects in an array. That'll be your best bet in terms of lookup considering you want "Give me the object at index 12", you can easily access that object like data[11]

Now coming towards storing and sorting them, consider you have the following array of those objects:

var data = [{
    name: 'Bill',
    dob: '2014-05-17T15:31:00Z'
},
{
    name: 'John',
    dob: '2013-06-17T15:31:00Z'
},
{
    name: 'Alex',
    dob: '2010-06-17T15:31:00Z'
}];

The following simple function (taken from here) will help you in sorting them based on their properties:

function sortResults(prop, asc) {
    data = data.sort(function(a, b) {
        if (asc) return (a[prop] > b[prop]);
        else return (b[prop] > a[prop]);
    });
}

First parameter is the property name on which you want to sort e.g. 'name' and second one is a boolean of ascending sort, if false, it will sort descendingly.

Next step, you need to call this function and give the desired values:

sortResults('name', true);

and Wola! Your array is now sorted ascendingly w.r.t names. Now you can access the objects like data[11], just like you wished to access them and they are sorted as well.

You can play around with the example HERE. If i missed anything or couldn't understand your problem properly, feel free to explain and i'll tweak my solution.

EDIT: Going through your question again, i think i missed that dynamically adding objects bit. With my solution, you'll have to call the sortResults function everytime you add an object which might get expensive.

Hey, thanks for that. Yup the basic sort of an array is the easy bit although your solution only sorts by name and not also by dob. The complex part of this is handling a sort against multiple properties in both ascending and descending order whilst also not calling the sort every time for each new item... — Rob Evans, Oct 02 '14 at 08:44
yea.. figured that out later. For that you're right some sort of tree or why don't you go for hashing? — Abdul Jabbar, Oct 02 '14 at 08:48

Efficient Sorted Data Structure in JavaScript

1 Answers1