from heapq import *
Posted by: Gustavo Felisberto in Ciência/Tecnologia, Geral, tags: heap, pythonFantástico… Já gosto outra vez de python 
Em vez de ter de implementar uma heap como me aconteceu em Java, o meu querido python já tem uma implementada por mim.
Mas o que é uma heap?
Simplificando uma heap é uma estrutura em árvore que tem a particularidade de ter na raiz o nó com menor ou maio valor que existe na árvore. Em adição tem custos baixos, O( ln( n ) ) , para grande parte das operações básicas, tais como adição e remoção de nós.
Mas a implementação em python é uma min-heap e eu preciso de uma max
Duhhhhh….. em vez de:
[code lang="python"]def __cmp__(self, other):
return cmp(self.getHeuristica(), other.getHeuristica())[/code]
Basta usar:
[code lang="python"]def __cmp__(self, other):
return other.getHeuristica() - self.getHeuristica() [/code]
Não li atentamente o código da heap que vem com o python, mas fiquei com a ideia que seria a clássica Heap Binária. No meu caso onde facilmente tenho algumas dezenas de milhares de nós e estou constantemente a tirar um e meter uns 20, talvez fosse interessante uma fibonacci heap……. Fica para outro dia.
Entries (RSS)