Python List Advanced Exercise - Sort a list of dictionaries based on values of a key

Last update on December 21 2024 07:33:59 (UTC/GMT +8 hours)

Write a Python function to sort a list of dictionaries based on values of a key.

Sample Solution:

Python Code:

# Import the necessary functions and classes from the 'heapq' module
from heapq import heapify, heappush, heappop

# Define a function to merge k sorted lists into a single sorted list
def merge_k_sorted_lists(nums):
    # Create an empty list 'heap_lst' to act as a min-heap
    heap_lst = []
    # Turn 'heap_lst' into a valid min-heap
    heapify(heap_lst)
    # Iterate through the input list of sorted lists 'nums'
    for lst in nums:
        # Iterate through the elements in each sorted list
        for val in lst:
            # Push each value onto the min-heap
            heappush(heap_lst, val)
    # Create a sorted list by repeatedly popping the smallest value from the min-heap
    return [heappop(heap_lst) for _ in range(len(heap_lst))]

# Create a list of sorted lists containing integers
nums = [[1, 4, 5], [1, 3, 4], [2, 6, 7, 8]]

# Print the original list of sorted lists
print("Original list:")
print(nums)

# Call the merge_k_sorted_lists function with the list of sorted lists and store the result in 'result'
result = merge_k_sorted_lists(nums)

# Print the result, which is a merged and sorted list
print("Merge k Sorted Lists into a list:")
print(result)

# Create another list of sorted lists containing integers
nums = [[1, 2], [-1, -2, -3], [0]]

# Print the original list of sorted lists
print("\nOriginal list:")
print(nums)

# Call the merge_k_sorted_lists function with the second list of sorted lists and store the result in 'result'
result = merge_k_sorted_lists(nums)

# Print the result, which is a merged and sorted list
print("Merge k Sorted Lists into a list:")
print(result) 

Sample Output:

Original list:
[[1, 4, 5], [1, 3, 4], [2, 6, 7, 8]]
Merge k Sorted Lists into a list:
[1, 1, 2, 3, 4, 4, 5, 6, 7, 8]

Original list:
[[1, 2], [-1, -2, -3], [0]]
Merge k Sorted Lists into a list:
[-3, -2, -1, 0, 1, 2]

Flowchart:

What is the time complexity and space complexity of the following Python code?

from heapq import heapify, heappush, heappop
def merge_k_sorted_lists(nums):
    heap_lst = []
    heapify(heap_lst)
    for lst in nums:
        for val in lst:
            heappush(heap_lst, val)
    return [heappop(heap_lst) for _ in range(len(heap_lst))]

Time complexity - The time complexity of the merge_k_sorted_lists() function is O(n log n), where n is the total number of elements across all the lists. Each element in each list is iterated over and pushed onto the heap, which takes O(log n) time, and then it is popped off the heap, which also takes O(log n) time.

Space complexity - The space complexity is O(n), because we store all the elements from the input lists on the heap. The heap will take up O(n) space, since it needs to store all the elements. Additionally, we create a list of lengths n to hold the output, but this is negligible compared to the size of the heap.

Python Code Editor:

Previous: Implement a LRU cache.
Next: List all pairs whose sum equals a given value.