¿Cómo mantener el diccionario en un montón en Python?

requisitos previos:

• Estructura de datos de montón binario
• módulo heapq en Python
• Diccionario en Python .

El diccionario se puede mantener en el montón en función de la clave o del valor. Las convenciones a mantener se enumeran a continuación:

• El par clave-valor en el índice ‘ i ‘ se considera el padre del par clave-valor en los índices 2k+1 y 2k+2 .
• Para un montón mínimo, la clave/valor principal debe ser menor que sus elementos secundarios.
• Para un montón máximo, la clave/valor principal debe ser mayor que sus elementos secundarios.

Ejemplos:

Diccionario normal: {11:2, 0:4, 5:9, 22:7}

Montón basado en claves del diccionario: {0: 4, 1: 1, 5: 9, 22: 7, 11: 2}

Montón basado en valores del diccionario: {11: 2, 0: 4, 5: 9, 22: 7}

Este artículo muestra cómo mantener un diccionario en un montón mínimo usando el módulo heapq.

Diccionario normal como un montón

El diccionario normal con enteros/strings como clave se puede mantener en una estructura de montón con la ayuda del módulo heapq. Pero este módulo espera que se pase una lista. Entonces, el enfoque utilizado aquí es:

1. Convierta los pares clave-valor en una lista de tuplas.
2. Pase la lista de tuplas a la función heapify() .
3. Convierta la lista resultante en un diccionario nuevamente.

Nota: Heapify() en tuplas considera el primer elemento de la tupla para el proceso. Por lo tanto, de forma predeterminada, los diccionarios se mantienen en montón, basándose únicamente en la clave.

Ejemplo 1: basado en la clave para números enteros

Considere un diccionario donde las claves son números enteros positivos y los valores son sus cuadrados. Ahora, esto debe mantenerse en un montón.

# import modules
import heapq as hq
 
# dictionary to be heapified
dict_1 = {11: 121, 2: 4, 5: 25, 3: 9}
 
# convert dictionary to list of tuples
di = list(dict_1.items())
 
print("dictionary into list :", di)
 
# converting into heap
hq.heapify(di)
 
print("Heapified list of tuples :", di)
 
# converting heap to dictionary
di = dict(di)
 
print("Dictionary as heap :", di)

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}

Ejemplo 2: Basado en la clave para String 

Considere un diccionario que tiene una combinación de alfabetos como clave y su numeración como valores. Por ejemplo: “ abc”: 123. Esto debe mantenerse en el montón. 

# import modules
import heapq as hq
 
# dictionary to be heapified
dict_1 = {"yz": 2526, "ab": 12, "cd": 34, "ij": 910, "fg": 67}
 
# convert dictionary to list of tuples
di = list(dict_1.items())
 
print("dictionary into list :", di)
 
# converting into heap
hq.heapify(di)
 
print("Heapified list of tuples :", di)
 
# converting heap to dictionary
di = dict(di)
 
print("Dictionary as heap :", di)

Producción:

diccionario en lista: [(‘yz’, 2526), ​​(‘ab’, 12), (‘cd’, 34), (‘ij’, 910), (‘fg’, 67)] 
Lista acumulada de tuplas: [(‘ab’, 12), (‘fg’, 67), (‘cd’, 34), (‘ij’, 910), (‘yz’, 2526)] 
Diccionario como montón: {‘ab’: 12, ‘fg’: 67, ‘cd’: 34, ‘ij’: 910, ‘yz’: 2526}

Ejemplo 3: Basado en el valor

El enfoque difiere ligeramente aquí. Los pasos a realizar son:

1. Extraiga los valores del diccionario y añádalos a una lista.
2. Pase la lista a heapify().
3. Basándose en los valores de la lista acumulada, reconstruya un nuevo diccionario a partir del original iterándolo.

Aquí solo los valores satisfacen la propiedad del montón y no necesariamente las claves.

Ejemplo:

# import the module
import heapq as hq
 
# dictionary to be heapified
li_dict={11:121,2:4,5:25,3:9}
 
# List to hold values from dictionary
heap_dict=[]
 
# extract the values from dictionary
for i in li_dict.values():
    heap_dict.append(i)
     
# heapify the values
hq.heapify(heap_dict)  
print("Values of the dict after heapification :",heap_dict)
 
# list to hold final heapified dictionary
new_dict=[]
 
# mapping and reconstructing final dictionary
for i in range(0,len(heap_dict)):
     
    # Iterating the oringinal dictionary
    for k,v in li_dict.items():
       
        if v==heap_dict[i] and (k,v) not in new_dict:
            new_dict.append((k,v))
             
new_dict=dict(new_dict)
 
print("Final dictionary :",new_dict)

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

Lista de diccionarios como un montón

Los ejemplos vistos arriba se basan en un solo diccionario. Considere una lista de diccionarios que debe mantenerse como un montón. El enfoque utilizado es: 

• Convierta cada diccionario en una tupla utilizando la comprensión de listas.
• Pase la lista a heapify().
• Convierta la lista resultante de tuplas acumuladas en el diccionario.

Nota: Heapify() en tuplas considera el primer elemento de la tupla para el proceso. Por lo tanto, de forma predeterminada, los diccionarios se mantienen en montón, basándose únicamente en la clave.

Ejemplo : 

# import modules
import heapq as hq
 
# list of dictionaries
li_dict=[{11:121},{2:4},{5:25},{3:9}]
 
#temporary list to hold tuple of key-value pairs
heap_dict=[]
 
# convert each dict to tuple
heap_dict=[(k,v) for i in li_dict for k,v in i.items() ]
 
print("After extraction :",heap_dict)
 
# heapify the list of tuples
hq.heapify(heap_dict)  
 
print("Heapified key-value pairs :",heap_dict)
 
# reconvert to dictionary
final=dict(heap_dict)
print("Heapified dictionaries :",final)

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}

Diccionarios anidados

En el caso de los diccionarios anidados, la tarea requiere más pasos para mantener el diccionario en el montón. Si el diccionario debe mantenerse en función de la clave en un diccionario interno, se puede utilizar el siguiente enfoque.

• Convierte el diccionario en una lista de tuplas donde la clave del diccionario externo es tupla[0] y la clave del diccionario interno es tupla[1].
• Extraiga los valores de la clave en los diccionarios internos en una lista.
• Aplicar heapify() en esa lista.
• Reconstruya un nuevo diccionario ordenándolos en función de los resultados acumulados.

Por ejemplo, considere un registro de empleados como un diccionario anidado. El registro aparece como se indica a continuación: 

{

   «emp01»:{

       “nombre”:”Kate”,

       «edad»: 22,

       “designación”: “Analista”,

       “Salario”:30000

   },

   «emp02»:{

       “nombre”:”Rina”,

       «edad»: 20,

       “designación”:”Programador”,

       “Salario”:25000

   },

   «emp03»:{

       “nombre”:”Vikas”,

       «edad»: 42,

       “designación”:”Gerente”,

       “Salario”:35000

   },

   «emp04»:{

       «nombre»:»manish»,

       «edad»: 42,

       “designación”:”Gerente”,

       “Salario”:15000

   }

}

Ahora mantengamos esto en un montón mínimo basado en los valores salariales. Así, el empleado con salario mínimo aparece como primer registro. Para una mejor legibilidad y comprensión, podemos dividir el código en funciones.

Paso 1: Defina la función para convertir el diccionario en una lista 

def get_list(d):
     
    list_li=list(d.items())
     
    print("Dictionary as list",list_li,"\n")
     
    return(list_li)

 
Paso 2: Defina la función que realiza la acumulación. Toma como parámetro la lista de tuplas. 

def convert_heap(list_li):
     
    # list to hold salary values
    sal_li=[]
 
    # extract salary values
    for i in range(0,len(list_li)):
       
        sal_li.append(list_li[i][1]['Salary'])
 
    print("Before heapify :",sal_li,"\n")
 
    # heapify the salary values
    hq.heapify(sal_li)
 
    print("After salary :",sal_li,"\n")
 
    # list to hold the final dictionary as heap
    final=[]
 
    # reconstruction of dictionary as heap
    # yields a list of tuples of key-value pairs
    for i in range(0,len(sal_li)):
       
        for j in range(0,len(sal_li)):
           
            if list_li[j][1]['Salary']==sal_li[i]:
                final.append(list_li[j])
             
    # list of tuples to dictionary
    final=dict(final)
    
    return final

Paso 3: Defina el diccionario y llame a las funciones apropiadamente.

nested_dict={
    "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
    }
}
 
list_li=get_list(nested_dict)
 
final=convert_heap(list_li)
 
print("Dictionary as heap :",final)

Ahora, al juntar todo el código, obtenemos un diccionario anidado que se mantiene en el montón, en función de los valores del salario.

import heapq as hq
 
def get_list(d):
     
    list_li=list(d.items())
     
    print("Dictionary as list",list_li,"\n")
     
    return(list_li)
   
def convert_heap(list_li):
     
    # list to hold salary values
    sal_li=[]
 
    # extract salary values
    for i in range(0,len(list_li)):
       
        sal_li.append(list_li[i][1]['Salary'])
 
    print("Before heapify :",sal_li,"\n")
 
    # heapify the salary values
    hq.heapify(sal_li)
 
    print("After heapify :",sal_li,"\n")
 
    # list to hold the final dictionary as heap
    final=[]
 
    # reconstruction of dictionary as heap
    # yields a list of tuples of key-value pairs
    for i in range(0,len(sal_li)):
       
        for j in range(0,len(sal_li)):
           
            if list_li[j][1]['Salary']==sal_li[i]:
                final.append(list_li[j])
             
    # list of tuples to dictionary
    final=dict(final)
    
    return final
   
nested_dict={
    "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
    }
}
 
list_li=get_list(nested_dict)
 
final=convert_heap(list_li)
 
print("Dictionary as heap :",final)

Producción

Diccionario como lista [(‘emp01′, {‘name’: ‘Kate’, ‘age’: 22, ‘designation’: ‘Analyst’, ‘Salary’: 30000}), (‘emp02′, {‘name’: ‘Rina’, ‘edad’: 20, ‘designación’: ‘Programador’, ‘Salario’: 25000}), (‘emp03′, {‘name’: ‘Vikas’, ‘edad’: 42, ‘designación’: ‘Gerente’, ‘Salario’: 35000}), (‘emp04′, {‘nombre’: ‘manish’, ‘edad’: 42, ‘designación’: ‘Gerente’, ‘Salario’: 15000})]

 Antes de acumular: [30000, 25000, 35000, 15000] 

 Después de heapificar: [15000, 25000, 35000, 30000] 

Diccionario como montón: {‘emp04′: {‘name’: ‘manish’, ‘age’: 42, ‘designation’: ‘Manager’, ‘Salary’: 15000}, ‘emp02′: {‘name’: ‘Rina ‘, ‘edad’: 20, ‘designación’: ‘Programador’, ‘Salario’: 25000}, ‘emp03′: {‘nombre’: ‘Vikas’, ‘edad’: 42, ‘designación’: ‘Gerente’, ‘Salario’: 35000}, ‘emp01′: {‘nombre’: ‘Kate’, ‘edad’: 22, ‘designación’: ‘Analista’, ‘Salario’: 30000}}

Inserción en el diccionario mantenida como un montón

La inserción de nuevos valores se puede hacer directamente usando el método heappush() en el módulo heapq . Su sintaxis es la siguiente.

heapq. heappush (lista, nuevo_valor)

Ahora la lista de tuplas junto con una nueva tupla se puede pasar a esta función para agregar el par de valor de nueva clave.

Ejemplo :

import heapq as hq
 
# list of dictionaries
li_dict=[{11:121},{2:4},{5:25},{3:9}]
 
# list to hold tuples
heap_dict=[]
 
# convert each dict to tuple of (key,value)
heap_dict=[(k,v) for i in li_dict for k,v in i.items() ]
 
print("List of tuples :",heap_dict)
 
# applying heapify()
hq.heapify(heap_dict)  
 
print("After heapification :",heap_dict)
 
# reconvert to dict
final=dict(heap_dict)
 
print("Dictionary as heap :",final)
 
# add new value (1,1)
hq.heappush(heap_dict,(1,1))
 
print("After insertion & heapification",heap_dict)
 
#reconvert the result
final=dict(heap_dict)
 
print("New dictionary :",final)

Producción:

Lista de tuplas: [(11, 121), (2, 4), (5, 25), (3, 9)] 
Después de la acumulación: [(2, 4), (3, 9), (5, 25) , (11, 121)] 
Diccionario como pila: {2: 4, 3: 9, 5: 25, 11: 121} 
Después de la inserción y acumulación [(1, 1), (2, 4), (5, 25) , (11, 121), (3, 9)] 
Nuevo diccionario: {1: 1, 2: 4, 5: 25, 11: 121, 3: 9}

Otro método que se puede hacer es tener una función que apile el diccionario y llamarlo después de actualizar el diccionario. 

Ejemplo :

import heapq as hq
 
def heapify_dict(d):
   
      # convert to list of tuples
    li=list(dict1.items())
     
    hq.heapify(li)
     
    li=dict(li)
     
    print("Dictionary as heap :",li)
     
dict1={11:121,2:4,5:25,3:9}
 
print("Before adding new values")
heapify_dict(dict1)
 
# add new values to dictionary
dict1[4]=16
dict1[1]=1
 
print("Updated dictionary :",dict1)
 
print("After adding new values")
heapify_dict(dict1)

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}