Tree algorithm - arrange integer array numbers to form largest number

I have solved leetcode's Largest Number.

I am asking another question about it here, more from a theory perspective about "if" I had used a tree for the solution. I have a full functioning non-tree based solution that you can refer to my post on code review stack exchange. However, I had another approach that I was going to follow at first; which uses a tree (as described in my post on code review). I am interested in learning about the tree approach from a computer science theory approach.

I will paste here again my graphical explanation of the tree based algorithm I thought of:

It will traverse from leafs to parents following:

concatenate(parent key + greater integer nodes (ie greater than parent)) ---> parent integer value --> concatenate (parent key + smaller integer nodes (ie smaller than parent))

ie in this example 9 5 34 3 30

Questions

Update

For those interested, here is my implemented solution based on the feedback given by Minko_Minkov below, ie using max heap and heapsort. The code runs in 6ms (compared to 10ms using java sorting comparator).

class LargestNumber {
    public String largestNumber(int[] nums) {
        // Build max heap from array:
        // The max-heap tree will always keep
        // the biggest number at the top of the tree
        // then do a heap sort.
        heapSort(nums);

        StringBuilder str = new StringBuilder();
        // pop backwards: heapsort will sort using our lexical comparator function in an
        // increasing fashion. But the final string will be printed backward
        // to match.
        for (int i = nums.length - 1; i >= 0; i--)
            str.append(nums[i]);

        // if we get a string of all zeros, strip to 1 zero.
        if (str.charAt(0) == '0')
            return "0";

        return str.toString();
    }

    private static void heapSort(int[] A) {
        buildMaxHeap(A);
        for (int i = A.length - 1; i > 0; i--) {
            // Swap A[0] with A[i]
            swap(0, i, A);
            heapify(A, 0, i);
        }
    }

    // if ab > ba will return a positive number, and means i1 > i2
    // if ab <ba will return a negative number, and means i2 > i1
    // if ab = ba , choose any to return
    private static int LexicallyCompare(int i1, int i2) {
        String a = Integer.toString(i1);
        String b = Integer.toString(i2);

        return (a + b).compareTo(b + a);
    }

    // Swap using Xor
    private static void swap(int x, int y, int[] nums) {
        nums[x] = nums[x] ^ nums[y];
        nums[y] = nums[x] ^ nums[y];
        nums[x] = nums[x] ^ nums[y];
    }

    private static void buildMaxHeap(int[] A) {
        for (int i = (int) (Math.floor((double) A.length / 2) - 1); i >= 0; i--) {
            heapify(A, i, A.length);
        }
    }

    private static void heapify(int[] A, int i, int max) {
        int left = (2 * i) + 1;
        int right = (2 * i) + 2;
        int largest = i;

        if (left < max && LexicallyCompare(A[left], A[i]) > 0)
            largest = left;

        if (right < max && LexicallyCompare(A[right], A[largest]) > 0)
            largest = right;

        if (largest != i) {
            // swap A[i] with A[largest]
            swap(i, largest, A);
            heapify(A, largest, max);
        }

    }
}