Actually some of these long distance flyers got a slighty modified lung system from ours. Works pretty well at high altitudes. And hollow shafts in feathers make a pretty good insulation too.
Never forget, they flew around our skies when we were still sitting in a hole in the ground...