Fantá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.