Parece estar muy claro en la explicación por qué prioritario es O(1): porque se mantiene un puntero al nodo.
¿La falta de claridad es por qué eliminarPrioritario no es O(1)? Si es eso es porque al eliminar el prioritario hay que buscar el nuevo prioritario. Si bien mantener un puntero al padre puede ser útil para otras aplicaciones no lo es para esta, porque el nuevo prioritario puede estar en el subárbol derecho del que hasta ese momento era el prioritario.