На месте HeapSort

Мне поручено создать сортировку строки по возрастанию или убыванию значения, чтобы я мог решить остальную часть проблемы. Я выбрал по убыванию, и это почти работает на всех выходах. Я не могу использовать дополнительную память, и она должна работать в O (n log n), поэтому я знаю, что я должен использовать heapsort на месте. Я знаю, как выполнить сортировку с использованием O (n) дополнительной памяти, но это доставляет мне проблемы. Моя проблема в том, что первый символ в моей строке никогда не сортируется. Все остальное отсортировано, и я понимаю, почему оно не сортируется. У меня проблемы с поиском решения.

Для HeapSort на месте с моим пониманием:

1) Поменять элемент в нижней части кучи («последний элемент в строке») на корень

2) Чем использовать fixDown, чтобы опустить этот символ вниз, сравнивая с детьми

Первый символ не сортируется, потому что как только я поменяю его местами с последним элементом, я буду считать, что он отсортирован.

Моим первым предложенным решением было просто заменить первый символ строки на минимальный символ строки, поэтому, когда я делаю этот первоначальный обмен, он затем сортируется. Это вызвало больше проблем.

Вторым предложенным решением было вызвать fixDown (s, s.size () — 1,0). Таким образом, мы каждый раз опускаем верхний элемент, используя всю строку, но это привело меня к дальнейшему решению.

Спасибо за любую помощь, я действительно хочу узнать, как это исправить, и я пробовал много разных вещей, прежде чем я спросил здесь.

void count_chars(string s){

for(unsigned int i=s.size()-1;i>0;--i){
swap(s.at(i),s.at(0));
fixDown(s,i-1,0);
}
cout<<s<<endl;
}

static void fixDown(string &s,int size,int k){

while(2*k+1<=size){
int j=2*k+1;
if(j<size && s.at(j) > s.at(j+1))
++j;
if(s.at(k)<=s.at(j))
break;
swap(s.at(k),s.at(j));
k=j;
}