题解 | #单词倒排#

import java.util.* ;
public class Main{
    public static void main(String...args) {
        Scanner sc = new Scanner(System.in) ;
        while(sc.hasNextLine()) {
            char[] arr = sc.nextLine().toCharArray() ;
            sort(arr) ;
            System.out.println(new String(arr)) ;
        }
    }
    //使用堆排序
    public static void sort(char[] arr) {
        //初始化堆
        for(int i = (arr.length-1-1)/2 ; i >= 0 ; i --) {
            heapify(arr , i , arr.length-1) ;
        }
        //逐个交换
        for(int j = arr.length-1 ; j > 0 ; j--) {
            char t = arr[0] ;
            arr[0] = arr[j] ;
            arr[j] = t ;
            heapify(arr , 0 , j-1) ;
        }
    }
    public static void heapify(char[] arr , int s , int e) {
        int c1 = 2*s+1 ;
        int c2 = 2*s+2 ;
        int max = s ;
        if(c1 <= e && arr[c1] > arr[max]) {
            max = c1 ;
        }
        if(c2 <= e && arr[c2] > arr[max]) {
            max = c2 ;
        }
        if(max != s) {
            char t = arr[s] ;
            arr[s] = arr[max] ;
            arr[max] = t ;
            heapify(arr , max , e) ;
        }
    }
    
}