Heapq con predicado personalizado en Python

Requisito previo: módulo heapq

El módulo heapq tiene varias funciones que toman la lista como un parámetro y la organizan en un orden de montón mínimo. El problema con estas funciones es que esperan una lista o una lista de tuplas como parámetro. No admiten comparaciones entre otros iterables u objetos. Por ejemplo, considere un diccionario que debe mantenerse en montón.

import heapq as hq
  
my_dict={'a':'apple', 'b':'ball', 'c': 'cat'}
hq.heapify(my_dict)
  
print(my_dict)

Producción 

TypeError: heap argument must be a list

La función heapify() espera que el parámetro sea una lista. Entonces, si consideramos una lista de diccionarios, mire a continuación lo que sucede.

import heapq as hq
  
my_dict=[{'a':'apple'}, {'b':'ball'}, {'c': 'cat'}]
  
hq.heapify(my_dict)
  
print(my_dict)

Producción:

TypeError: ‘<‘ no se admite entre instancias de ‘dict’ y ‘dict’ 
 

Por lo tanto, no podemos comparar dos diccionarios usando el módulo heapq. A veces puede que tengamos que comparar objetos de una clase y mantenerlos en un montón. La comparación entre dichos objetos tampoco es factible con este módulo.

#import module
import heapq as hq
  
# the dictionary to be as heap
my_dict = {'z': 'zebra', 'b': 'ball', 'w': 'whale', 
           'a': 'apple', 'm': 'monkey', 'c': 'cat'}
  
# conversion to tuple
my_list = [(k, v) for k, v in my_dict.items()]
  
print("Before organizing as heap :", my_list)
  
# arrange as min-heap
hq.heapify(my_list)
  
print("After organizing as heap :", my_list)
  
# re convert to dictionary
my_dict = dict(my_list)
  
print("Resultant dictionary :", my_dict)

Este artículo analiza cómo superar los problemas mencionados anteriormente.

Personalizando la ordenación en heapq

Las funciones del módulo heapq pueden tomar una lista de elementos o una lista de tuplas como parámetro. Por lo tanto, hay dos formas de personalizar el proceso de clasificación:

1.  Convierta el iterable en una lista de tuplas/lista para comparar.
2.  Escriba una clase contenedora que anule el operador ‘<‘.

Conversión a lista de artículos

Este método es simple y puede usarse para resolver problemas de comparación de diccionarios. Los elementos del diccionario se pueden convertir en una lista de tuplas y luego pasar al método heapify.

Ejemplo 1: un diccionario simple

#import module
import heapq as hq
  
# the dictionary to be as heap
my_dict = {'z': 'zebra', 'b': 'ball', 'w': 'whale',
           'a': 'apple', 'm': 'monkey', 'c': 'cat'}
  
# conversion to tuple
my_list = [(k, v) for k, v in my_dict.items()]
  
print("Before organizing as heap :", my_list)
  
# arrange as min-heap
hq.heapify(my_list)
  
print("After organizing as heap :", my_list)
  
# re convert to dictionary
my_dict = dict(my_list)
  
print("Resultant dictionary :", my_dict)

Producción:

Antes de organizar como montón: [(‘z’, ‘cebra’), (‘b’, ‘pelota’), (‘w’, ‘ballena’), (‘a’, ‘manzana’), (‘m’ , ‘mono’), (‘c’, ‘gato’)] 
Después de organizar como montón: [(‘a’, ‘manzana’), (‘b’, ‘pelota’), (‘c’, ‘gato’ ), (‘z’, ‘cebra’), (‘m’, ‘mono’), (‘w’, ‘ballena’)] Diccionario resultante: {‘a’: ‘manzana’, ‘b’: ‘ 
bola ‘, ‘c’: ‘gato’, ‘z’: ‘cebra’, ‘m’: ‘mono’, ‘w’: ‘ballena’}

Ejemplo 2: una lista de diccionarios

#import module
import heapq as hq
  
# the list of dictionaries to be as heap
my_dict = [{'z': 'zebra'}, {'b': 'ball'}, {'w': 'whale'},
           {'a': 'apple'}, {'m': 'monkey'}, {'c': 'cat'}]
  
# conversion to tuple
my_list = [(k, v) for i in my_dict for k, v in i.items()]
  
print("Before organizing as heap :", my_list)
  
# arrange as min-heap
hq.heapify(my_list)
  
print("After organizing as heap :", my_list)
  
# re convert to dictionary
my_dict = dict(my_list)
  
print("Resultant dictionary :", my_dict)

Producción:

Antes de organizar como montón: [(‘z’, ‘cebra’), (‘b’, ‘pelota’), (‘w’, ‘ballena’), (‘a’, ‘manzana’), (‘m’ , ‘mono’), (‘c’, ‘gato’)] 
Después de organizar como montón: [(‘a’, ‘manzana’), (‘b’, ‘pelota’), (‘c’, ‘gato’ ), (‘z’, ‘cebra’), (‘m’, ‘mono’), (‘w’, ‘ballena’)] Diccionario resultante: {‘a’: ‘manzana’, ‘b’: ‘ 
bola ‘, ‘c’: ‘gato’, ‘z’: ‘cebra’, ‘m’: ‘mono’, ‘w’: ‘ballena’}

Los métodos anteriores se pueden utilizar para un diccionario con cualquier tipo de datos. 

Usando una clase contenedora

Considere una situación en la que los objetos de una clase deben mantenerse en un montón mínimo. Por ejemplo, consideremos una clase que tiene atributos como ‘ nombre ‘, ‘ designación ‘, ‘ yos ‘ (años de servicio), ‘ salario ‘. Los objetos de esta clase deben mantenerse en min-heap en función de ‘ yos ‘ (años de servicio). 

Aquí, anulamos el operador relacional ‘ < ‘ de modo que compare los años de servicio de cada empleado y devuelva verdadero o falso. Según el valor booleano devuelto, el módulo heapq organiza los objetos en orden de montón mínimo.

# import required module
import heapq as hq
  
# class definition
class employee:
  
  # constructor
    def __init__(self, n, d, yos, s):
        self.name = n
        self.des = d
        self.yos = yos
        self.sal = s
  
  # function for customized printing
    def print_me(self):
        print("Name :", self.name)
        print("Designation :", self.des)
        print("Years of service :", str(self.yos))
        print("salary :", str(self.sal))
  
   # override the comparison operator
    def __lt__(self, nxt):
        return self.yos < nxt.yos
  
  
# creating objects
e1 = employee('Anish', 'manager', 3, 24000)
e2 = employee('kathy', 'programmer', 2, 15000)
e3 = employee('Rina', 'Analyst', 5, 30000)
e4 = employee('Vinay', 'programmer', 1, 10000)
  
# list of employee objects
emp = [e1, e2, e3, e4]
  
# converting to min-heap
# based on yos
hq.heapify(emp)
  
# printing the results
for i in range(0, len(emp)):
    emp[i].print_me()
    print()

Name : Vinay
Designation : programmer
Years of service : 1
salary : 10000

Name : kathy
Designation : programmer
Years of service : 2
salary : 15000

Name : Rina
Designation : Analyst
Years of service : 5
salary : 30000

Name : Anish
Designation : manager
Years of service : 3
salary : 24000