A collection of Data Structures & Algorithms in javascript
var algo = require('algorithm');
Queue/FIFO Operations & Properties:
(constructor) pushes every argument that is passed into the queue
push(1, 2, 3, 4): Pushes 4 integers into the queue - O(1)
pop(): Removes the earliest value from the queue and returns it - O(1)
top: Returns the earliest pushed value without removing it - O(1)
length: Returns the number of elements in the queue
var q = new algo.Queue(1, 2, 3, 4);
Stack/FILO/LIFO Operations & Properties:
MinHeap Operations & Properties:
Similarly, we have MaxHeap as well.
There is also a general Heap/PriorityQueue that can be constructed using a comparator and an existing array:
var h = new algo.PriorityQueue(algo.cmp_lt, [92, 19, 192, 11, 0, 3])
MinMaxHeap/PriorityDequeue Operations & Properties:
(constructor) takes in a less-than comparator and an (possibly non-empty) array which will be used for storage
push/insert(1, 2, 3, 4): Pushes 4 integers into the heap - O(log n)
pop_min(): Removes the smallest value from the heap and returns it - O(log n)
pop_max(): Removes the largest value from the heap and returns it - O(log n)
min: Returns the smallest value in the heap without removing it - O(1)
max: Returns the largest value in the heap without removing it - O(1)
length: Returns the number of elements in the heap
var mmh = new algo.MinMaxHeap(algo.cmp_lt, [45, 2, 54, 12, 21, 99, 1]);
Trie Operations & Properties:
A Trie is like a set. Adding an element multiple times does not increase the length of the Trie by more than 1.
Disjoint Set Operations & Properties:
AVL Tree Operations & Properties:
range(range/array, start index, one after end index): Retuns a range of values from the passed array. The returned range is also an array. O(n)
lower_bound(range, value, cmp_lt): (range MUST be sorted) Returns the first location before which 'value' can safely be inserted so that the resulting range is also sorted. Will return one past the last valid index if value is greater than any element in the list. O(log n)
upper_bound(range, value, cmp_lt): (range MUST be sorted) Returns the last location before which 'value' can safely be inserted so that the resulting range is also sorted. Will return one past the last valid index if value is greater than any element in the list. O(log n)
equal_range(range, value, cmp_lt): (range MUST be sorted) Returns the first and last locations before and after which 'value' can safely be inserted so that the resulting range is also sorted. O(log n)
binary_search(range, value, cmp_lt): (range MUST be sorted) Returns the first index where value is equal to the value at index. Returns -1 if the value is not to be found in the range. O(log n)
partition(range, pivot, cmp_lt): Partitions a range around 'pivot' and returns the index in the modified range that corresponds to the location before which pivot can be inserted so that the partition remains. Time Complexity: O(n) Space Complexity: O(1)
stable_partition: Same as above, but retains the original order of elements. Time Complexity: O(n) Space Complexity: O(n)
merge(range1, range2, cmp_lt): Merges 2 sorted ranges and returns a new merged range. Time Complexity: O(n) Space Complexity: O(n)
is_sorted(range, cmp_lt): Returns true or false depending on whether range is sorted according to 'cmp_lt'.
is_heap(range, cmp_lt): Returns true or false depending on whether range is a heap according to 'cmp_lt'. If 'cmp_gt' is used, then is_heap will check range for being in Max-Heap order. If 'cmp_lt' is used, it will check for range to be in Min-Heap order.
heap_sort(input, cmp): Sorts 'input' using comparator 'cmp'. Sorts the array 'input' in-place. Returns the sorted array. The array passed as 'input' WILL be modified. This is an unstable sort - O(n log n)
All Comparators return either true or false only.
cmp_lt(lhs, rhs): Returns whatever lhs < rhs returns
cmp_gt(lhs, rhs): Uses < to do a > comparison
cmp_lt_eq(lhs, rhs): Uses < to do a <= comparison
cmp_gt_eq(lhs, rhs): Uses < to do a >= comparison
cmp_eq(lhs, rhs): Uses < to do an == comparison
cmp_gt_gen(cmp_lt): Given a less-than comparator, generates a greater-than comparator from it
cmp_gt_eq_gen(cmp_lt): Given a less-than comparator, generates a greater-than or equal to comparator from it
cmp_lt_eq_gen(cmp_lt): Given a less-than comparator, generates a less-than or equal to comparator from it
cmp_eq_gen(cmp_lt): Given a less-than comparator, generates an equal to comparator from it