Lesson 3

Exploring Sorted Dictionaries with Python and the sortedcontainers Library

Diving into Sorted Maps

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.

Introduction: Sorted Maps in Python

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.

Discovering SortedDict

To create a SortedDict object, pass a dictionary or any key-value pair iterable, ensuring that the keys are immutable. For instance:

Python
1from 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})
Traversing SortedDict Methods

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:

Python
1from 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)
Lesson Summary

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!

Enjoy this lesson? Now it's time to practice with Cosmo!

Practice is how you turn knowledge into actual skills.