class HeapStructure:

    def __init__(self, ls):

        self.ls = ls

    def shift_up(self, index):  # 上移使符合堆要求

        if index == 0:

            return

        ls = self.ls

        par_index = (index - 1) // 2

        if ls[par_index] < ls[index]:

            ls[par_index], ls[index] = ls[index], ls[par_index]

        self.shift_up(index-1)

    def shift_down(self, index, last_index):  # 下移使符合堆要求

        ls = self.ls

        child_left, child_right = 2 * index + 1, 2 * index + 2

        if child_left > last_index:

            return

        if child_left < last_index and ls[child_left] < ls[child_right]:

            if ls[index] < ls[child_right]:  # 与右子节点交换

                ls[index], ls[child_right] = ls[child_right], ls[index]

                self.shift_down(child_right, last_index)

        else:

            if ls[index] < ls[child_left]:  # 与左子节点交换

                ls[index], ls[child_left] = ls[child_left], ls[index]

                self.shift_down(child_left, last_index)

    def sort(self):

        i = len(self.ls)

        if i == 0:

            return self.ls

        last_index = i - 1

        self.shift_up(last_index) # 变为最大堆

        self.ls[0], self.ls[last_index] = self.ls[last_index], self.ls[0] # 最大值移动到队尾

        last_index -= 1

        while last_index:

            self.shift_down(0, last_index=last_index) # 调整为最大堆

            self.ls[0], self.ls[last_index] = self.ls[last_index], self.ls[0]

            last_index -= 1

        return self.ls

if __name__ == '__main__':

    ls = [5, 1, 2, 4, 8, 0, 9]

    print(HeapStructure(ls).sort())

    ls = []

    print(HeapStructure(ls).sort())