How to maintain dictionary in a heap in Python ?

Prerequisites:

• Binary heap data structure
• heapq module in Python
• Dictionary in Python.

The dictionary can be maintained in heap either based on the key or on the value. The conventions to be maintained are listed below:

• The key-value pair at index ‘i‘ is considered to be the parent of key-value pair at the indices 2k+1 and 2k+2.
• For a min-heap, the parent key/value must be smaller than its children.
• For a max-heap, the parent key/value must be larger than its children.

Examples:

Normal dictionary : {11:2, 0:4, 5:9, 22:7}

Heap based on keys of the dictionary : {0: 4, 1: 1, 5: 9, 22: 7, 11: 2}

Heap based on values of the dictionary : {11: 2, 0: 4, 5: 9, 22: 7}

This article shows how to maintain a dictionary in a min-heap using the heapq module.

Normal dictionary as a heap

The normal dictionary with integers/strings as the key can be maintained in a heap structure with the help of the heapq module. But this module expects a list to be passed. So the approach used here is :

1. Convert the key-value pairs into a list of tuples.
2. Pass the list of tuples to heapify() function.
3. Convert the resulting list into a dictionary again.

Note: The heapify() on tuples considers the first element in the tuple for the process. Thus, by default, the dictionaries are maintained in heap, based on the key only.

Example 1: Based on the Key for integers

Consider a dictionary where the keys are positive integers and the values are their squares. Now, this should be maintained in a heap.

dictionary into list : [(11, 121), (2, 4), (5, 25), (3, 9)]
Heapified list of tuples : [(2, 4), (3, 9), (5, 25), (11, 121)]
Dictionary as heap : {2: 4, 3: 9, 5: 25, 11: 121}

Example 2: Based on key for String 

Consider a dictionary which has a combination of alphabets as key and their numbering as values. For example: “abc” : 123. This has to be maintained in heap. 

Output:

dictionary into list : [(‘yz’, 2526), (‘ab’, 12), (‘cd’, 34), (‘ij’, 910), (‘fg’, 67)] 
Heapified list of tuples : [(‘ab’, 12), (‘fg’, 67), (‘cd’, 34), (‘ij’, 910), (‘yz’, 2526)] 
Dictionary as heap : {‘ab’: 12, ‘fg’: 67, ‘cd’: 34, ‘ij’: 910, ‘yz’: 2526}

Example 3: Based on the value

The approach slightly differs here. The steps to be carried out are:

1. Extract the values in the dictionary and append to a list.
2. Pass the list to heapify().
3. Based on the heapified list values, reconstruct a new dictionary from the original one by iterating through it.

Here only the values satisfy the heap property and not necessarily the keys.

Example:

Values of the dict after heapification : [4, 9, 25, 121]
Final dictionary : {2: 4, 3: 9, 5: 25, 11: 121}

List of dictionaries as a heap

The examples seen above are based on a single dictionary. Consider a list of dictionaries which has to be maintained as a heap. The approach used is: 

• Convert each dictionary into a tuple using list comprehension.
• Pass the list to heapify().
• Convert the resulting list of heapified tuples into the dictionary.

Note: The heapify() on tuples considers the first element in the tuple for the process. Thus, by default, the dictionaries are maintained in heap, based on the key only.

Example : 

After extraction : [(11, 121), (2, 4), (5, 25), (3, 9)]
Heapified key-value pairs : [(2, 4), (3, 9), (5, 25), (11, 121)]
Heapified dictionaries : {2: 4, 3: 9, 5: 25, 11: 121}

Nested dictionaries

In the case of nested dictionaries, the task takes more steps to maintain the dictionary in heap. If the dictionary has to be maintained based on the key in a inner dictionary, then the following approach can be used.

• Convert the dictionary into list of tuples where the key of the outer dictionary is tuple[0] and the inner dictionary is tuple[1].
• Extract the values of the key in inner dictionaries into a list.
• Apply heapify() on that list.
• Re-construct a new dictionary by ordering them based on the heapified results.

For example, consider a record of employees as a nested dictionary. The record appears as given below: 

{

   “emp01”:{

       “name”:”Kate”,

       “age”:22,

       “designation”: “Analyst”,

       “Salary”:30000

   },

   “emp02”:{

       “name”:”Rina”,

       “age”:20,

       “designation”:”Programmer”,

       “Salary”:25000

   },

   “emp03”:{

       “name”:”Vikas”,

       “age”:42,

       “designation”:”Manager”,

       “Salary”:35000

   },

   “emp04”:{

       “name”:”manish”,

       “age”:42,

       “designation”:”Manager”,

       “Salary”:15000

   }

}

Now let us maintain this in a min-heap based on the salary values. Thus, the employee with minimum salary appears as the first record. For better readability and understanding we can split the code into functions.

Step 1:  Define the function to convert the dictionary into a list 

 
Step 2: Define the function that performs heapification. Takes the list of tuples as parameter. 

Step 3: Define the dictionary and call the functions appropriately.

Now putting all the code together we get a nested dictionary maintained in heap, based on the values of the salary.

Output

Dictionary as list [(’emp01′, {‘name’: ‘Kate’, ‘age’: 22, ‘designation’: ‘Analyst’, ‘Salary’: 30000}), (’emp02′, {‘name’: ‘Rina’, ‘age’: 20, ‘designation’: ‘Programmer’, ‘Salary’: 25000}), (’emp03′, {‘name’: ‘Vikas’, ‘age’: 42, ‘designation’: ‘Manager’, ‘Salary’: 35000}), (’emp04′, {‘name’: ‘manish’, ‘age’: 42, ‘designation’: ‘Manager’, ‘Salary’: 15000})]

 Before heapify : [30000, 25000, 35000, 15000] 

 After heapify : [15000, 25000, 35000, 30000] 

Dictionary as heap : {’emp04′: {‘name’: ‘manish’, ‘age’: 42, ‘designation’: ‘Manager’, ‘Salary’: 15000}, ’emp02′: {‘name’: ‘Rina’, ‘age’: 20, ‘designation’: ‘Programmer’, ‘Salary’: 25000}, ’emp03′: {‘name’: ‘Vikas’, ‘age’: 42, ‘designation’: ‘Manager’, ‘Salary’: 35000}, ’emp01′: {‘name’: ‘Kate’, ‘age’: 22, ‘designation’: ‘Analyst’, ‘Salary’: 30000}}

Insertion in dictionary maintained as a heap

The insertion of new values can be done directly using heappush() method in the heapq module. Its syntax is as follows.

heapq . heappush ( list , new_value )

Now the list of tuples along with a new tuple can be passed to this function to add the new-key value pair.

Example :

Output:

List of tuples : [(11, 121), (2, 4), (5, 25), (3, 9)] 
After heapification : [(2, 4), (3, 9), (5, 25), (11, 121)] 
Dictionary as heap : {2: 4, 3: 9, 5: 25, 11: 121} 
After insertion & heapification [(1, 1), (2, 4), (5, 25), (11, 121), (3, 9)] 
New dictionary : {1: 1, 2: 4, 5: 25, 11: 121, 3: 9}

Another method that can be done is to have a function that heapify the dictionary and calling it after updating the dictionary. 

Example :

Before adding new values
Dictionary as heap : {2: 4, 3: 9, 5: 25, 11: 121}
Updated dictionary : {11: 121, 2: 4, 5: 25, 3: 9, 4: 16, 1: 1}
After adding new values
Dictionary as heap : {1: 1, 2: 4, 5: 25, 3: 9, 4: 16, 11: 121}