Hello again! This lesson's topic is Sorted Maps (or Sorted Dicts). Similar to dictionaries, Sorted Maps are data structures that store key-value pairs but in an ordered manner. Learning about Sorted Maps enriches our set of tools for organized and efficient data manipulation. Today's goal is to work with Sorted Maps using the Python sortedcontainers
library.
In Python, we differentiate between standard dictionaries and Sorted Maps. Comparing regular dictionaries to Sorted Maps is akin to comparing a messy bookshelf to a well-organized library — the latter maintains order. Although Python natively does not include Sorted Maps, we'll leverage an external library, sortedcontainers
.
The sortedcontainers
library is a Python package that offers a Sorted List, Sorted Set, and Sorted Dict. Unlike regular collections, sorted collections maintain an order for their elements, which can be valuable for many algorithms and applications. Today, we'll utilize the SortedDict
class from sortedcontainers
, a dictionary that sorts its keys.
To create a SortedDict
object, pass a dictionary or any key-value pair iterable, ensuring that the keys are immutable. For instance:
Python1from sortedcontainers import SortedDict 2 3# Dictionary with fruits as keys and corresponding counts as values 4sd = SortedDict({'banana': 3, 'apple': 4, 'pear': 1, 'orange': 2}) 5 6# Print the SortedDict 7print(sd) # Output: SortedDict({'apple': 4, 'banana': 3, 'orange': 2, 'pear': 1})
A SortedDict
object boasts several useful methods. Here are some crucial ones:
SortedDict.bisect_left(key)
: This identifies an insertion point for a new key. If the key already exists, the insertion point is to the left of any current entries.SortedDict.bisect_right(key)
: This is similar to bisect_left
, but with the insertion point to the right of existing entries.SortedDict.pop(key[, default])
: This removes the specified key and returns its associated value.SortedDict.get(key[, default])
: This presents the value for the key if it exists; otherwise, it returns a default value.SortedDict.peekitem(index=-1)
: This method allows you to peek at an item in the sorted dictionary without removing it. By default, it returns the last (maximum) item as a (key, value)
tuple. You can specify an index to peek at an item in a specific position based on its key order.Consider the following Python code, which incorporates these methods:
Python1from sortedcontainers import SortedDict 2 3# Initialize SortedDict 4sd = SortedDict({'banana': 3, 'apple': 4, 'pear': 1, 'orange': 2}) 5 6# 'apple' is found at index 0 7print(sd.bisect_left('apple')) # Output: 0 8# 'apple' is found before index 1 9print(sd.bisect_right('apple')) # Output: 1 10 11# Remove 'apple' and print the removed item 12item = sd.pop('apple') 13print('Popped item:', item) # Output: Popped: 4 14 15# Attempt to fetch a nonexisting key 16value = sd.get('apple', 'Not found') 17print('Value:', value) # Output: Value: Not found 18 19# Peek at the last item 20last_item = sd.peekitem() 21print('Last item:', last_item) # Output: Last item: ('pear', 1)
Congratulations! You have successfully delved into sorted maps. This exploration included understanding the sortedcontainers
library, creating SortedDict
instances, and navigating SortedDict
's valuable methods. Next, you can look forward to hands-on exercises to fortify your understanding and expand your skillset. Keep practicing!