SortedList –
Sorted list is a sorted mutable sequence in which the values are maintained in sorted order.
Functions to add and remove elements:
add(value) : A function that takes one element as parameter and inserts it into the list by maintaining sorted order. Runtime Complexity: O(log(n))
update(iterable): A function that takes an iterable as input and updates the SortedList adding all the values from the iterable Runtime complexity: O(k*log(n)).
clear(): Remove all values from sorted list. Runtime complexity: O(n).
discard(value): Remove value from sorted list if it is a member. If value is not a member, do nothing. Runtime complexity: O(log(n)).
Below is the implementation –
# importing libraries from sortedcontainers import SortedList, SortedSet, SortedDict # initializing a sorted list with parameters # it takes an iterable as a parameter. sorted_list = SortedList([1, 2, 3, 4]) # initializing a sorted list using default constructor sorted_list = SortedList() # inserting values one by one using add() for i in range(5, 0, -1): sorted_list.add(i) # prints the elements in sorted order print('list after adding 5 elements: ', sorted_list) print('list elements are: ', end = '') # iterating through a sorted list for i in sorted_list: print(i, end = ' ') print() # removing all elements using clear() sorted_list.clear() # adding elements using the update() function elements = [10, 9, 8, 7, 6] sorted_list.update(elements) # prints the updated list in sorted order print('list after updating: ', sorted_list) # removing a particular element sorted_list.discard(8) print('list after removing one element: ', sorted_list) # removing all elements sorted_list.clear() print('list after removing all elements using clear: ', sorted_list) |
Output :
list after adding 5 elements: SortedList([1, 2, 3, 4, 5], load=1000) list elements are: 1 2 3 4 5 list after updating: SortedList([6, 7, 8, 9, 10], load=1000) list after removing one element: SortedList([6, 7, 9, 10], load=1000) list after removing all elements using clear: SortedList([], load=1000)
Python sorted containers | An Introduction
Sorted Containers is an Apache2 licensed sorted collections library, written in pure-Python, and fast as C-extensions. It was created by Grant Jenks and is an open source library. It is a collection of containers that allow us to insert and remove elements very efficiently while maintaining sorted order.
Features:
- Pure-Python
- Fully documented
- Benchmark comparison (alternatives, runtimes, load-factors
- Performance (often faster than C implementations)
- Compatible API (nearly identical to popular blist and rbtree modules)
- Feature-rich (e.g. get the five largest keys in a sorted dict: d.iloc[-5:])
- Pragmatic design (e.g. SortedSet is a Python set with a SortedList index)
Containers:
- SortedList
- SortedDict
- SortedSet
Installation:
Mac and Linux users can install via pip command:
sudo pip install sortedcontainers