Здравствуйте, BogusCoder, Вы писали:

BC>Ожидал: 1,2,3,4,5,6,7,8,9
BC>Получил: 1,2,4,3,7,8,5,9,6

BC>Почему?

priority_queue это вроде фибоначчиева куча, S[i]>=S[2i], S[i]>=S[2i+1]