Sorted Map and Set

🦋 Proposals
1

Proposal : SortedMap and SortedSet in JavaScript.

This SortedMap and SortedSet are based on data structures from other languages, like Java, where they are known as TreeMap and TreeSet, respectively. This will serve many purposes in Javascript and drastically reduce time complexity while still keeping the property of not allowing duplicates. The elements are ordered using their natural ordering or by a Comparator provided at creation time. It uses a Red-Black Tree implementation that keeps data sorted with O(logn) complexity.

Sorted Sets : a SortedSet is a Set that is sorted according to the natural ordering of its keys or by a Comparator provided at set creation time.

Let's see how currently we achieve from arrays and why its, not the thing.

// using arrays
let users = []

function addUser(user){
    users.push(user)
    users.sort((a,b)=>b.followers-a.followers)) 
   // each addition takes O(nlogn) complexity 
}

function getFamousUser(){
    return users[0]
}

addUser({uid:1,username:"john",followers:78}) // O(nlogn) operation
addUser({uid:2,username:"joe",followers:978}) // O(nlogn) operation
.
.
.
.
// so on and for n operation it will take O(n*nlogn)  which is drastically bad

proposal for a new SortedSet, which will be a binary tree in terms of internal structure, the same as a TreeSet in Java. The proposed syntax will be the same as Set in JavaScript while still not allowing duplicates.

const set=new SortedSet((a,b)=>b.followers-a.followers)

set.add({uid:1,username:"john",followers:78}) // takes O(logn) complexity
set.add({uid:2,username:"joe",followers:978})

set.pop() // {uid:2,username:"joe",followers:978} // takes O(logn) complexity

const temp= {uid:3,username:"tary",followers:3}
set.add(temp)

set.has(temp) // true, O(logn)
set.add({uid:4,username:"tim",followers:643})

set.pop() // {uid:4,username:"tim",followers:643}
set.pop() // {uid:1,username:"john",followers:78}

// so for n operations on SortedSet, it will be O(nlogn)

Sorted Maps : a SortedMap is a Map that is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time.

const map=new SortedMap((a,b)=>b-a)
// salaries -> empIds[]
map.set(25000,[1,2,3,4])
map.set(5000,[5,6])
map.set(1000,[7,8,9])
map.set(15000,[10,11,13,12])

// if we want to find all the employers with the highest or lowest salary 
map.popEntry() //  [25000,[1,2,3,4]]
map.has(25000) // false, already popped out
map.popEntry() //  [15000,[10,11,13,12]]

// same here also for n operation it ill take O(logn*n) which is way better

References :

2

Note that there is no global ordering of values in JavaScript. For example the following throws a TypeError:

Symbol() < Symbol()
3

So not all primitive but few have like number and string type, while doing arr.sort it does based on the natural comparator it you provide advanced type it throws error so we define custom comparator, similarly for keys we can do.

4

What would you want the order of this to be:

const s = new SortedSet();
s.add("3")
s.add(1);
s.add(2);
s.add(10);
s.add(20);
s.add("15");

arr.toSorted() would return [1, 10, "15", 2, 20, "3"]

5 
const s = new SortedSet((a, b) => parseInt(a) - parseInt(b));
s.add("3")
s.add(1);
s.add(2);
s.add(10);
s.add(20);
s.add("15");

Otherwise we can mandate a comparator to constructor when object is created.

6

Honestly, anything other than array.toSorted()/array.sort() behavior wouod be surprising.

I could see the use in the proposal, as I sometimes have a need. My usual pattern is binary search + splice, which could be a bit difficult to find in SourceGraph.

1 Like