SXHEAP - Sắp xếp vun đống
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

      Để sắp xếp tăng dần một mảng A gồm n phần tử a1, a2,..., an, đầu tiên thuật toán sắp xếp vun đống tạo một max heap từ mảng A. Sau đó thực hiện sắp xếp trong n -1 bước. Tại bước i, lấy phần tử lớn nhất trong heap chuyển ra sau mảng, sau khi chyển phần tử này được sắp. Heap được hiệu chỉnh cho bước tiếp theo. Ví dụ minh họa:

      Sắp xếp mảng 6 phần tử:  8  5  2  7  9  3

      Heap ban đầu: 9  8  3  7  5  2

        Sau bước 1: 8  7  3  2  5  9

        Sau bước 2: 7  5  3  2  8  9

        Sau bước 3: 5  2  3  7  8  9

        Sau bước 4: 3  2  5  7  8  9

        Sau bước 5: 2  3  5  7  8  9

      (Các số gạch dưới là heap)

      Cho mảng n phần tử bất kỳ, bạn hãy cho biết heap ban đầu và heap sau mỗi bước thực hiện sắp xếp.

Dữ liệu nhập:

- Dòng đầu tiên là số nguyên n (2 ≤ n ≤ 20) là số phần tử của mảng.

- Dòng tiếp theo gồm n số nguyên a1, a2,..., an (1 ≤ ai ≤ 100), mỗi số cách nhau một khoảng trắng.

Dữ liệu xuất: gồm n dòng

- Dòng đầu tiên gồm n số nguyên thể hiện heap ban đầu, mỗi số cách nhau một khoảng trắng.

- Trong n-1 dòng tiếp theo (ký hiệu 1 đến n-1), tại dòng thứ i thể hiện heap sau bước sắp xếp thứ i. Gồm n-i số nguyên, mỗi số cách nhau một khoảng trắng. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ví dụ

  • input
    6
    8 5 2 7 9 3
    output
    9 8 3 7 5 2
    8 7 3 2 5
    7 5 3 2
    5 2 3
    3 2
    2
Back to Top