Muito legal o post, guaracy.

Ainda pensando em utilizar funções da própria linguagem, proponho a seguinte solução: Criar uma fila de prioridades a partir da coleção de entrada. Com isso, fazer duas operações pop(mais que duas, no caso onde o primeiro elemento está duplicado).

Se a estrutura de filas é bem implementado, imagino que é tão eficiente quanto sua solução. E é mais simples, já que pode-se usar alguma biblioteca que implemente fila de prioridades. O que acha?