Heap տեսակավորում (Heap Sort)
Heap տեսակավորումն համեմատության վրա հիմնված տեսակավորման ալգորիթմ է, որն օգտագործում է Heap տվյալների կառուցվածքը զանգվածը տեսակավորելու համար։ Ալգորիթմի հիմնական գաղափարը հետևյալն է. նախ զանգվածի տարրերից կազմում ենք Heap, այնուհետև կրկնվողաբար հեռացնում ենք Heap-ի ամենամեծ կամ ամենափոքր էլեմենտը (կախված, թե Heap-ը max-heap է, թե min-heap) և այն տեղափոխում զանգվածի վերջ, մինչև Heap-ը դատարկվի:
Ձեզ խնդրում են իրականացնել Heap տեսակավորման ալգորիթմը min-heap-ը օգտագործելով:
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ 100 000), որը ցույց է տալիս էլեմենտների քանակը:Հաջորդ տողում տրված են
n թվեր ( ), որոնք պետք է տեսակավորվեն:Ելք
Ծրագիրը պետք է տպի վերջնական տեսակավորված զանգվածը աճման կարգով:
Օրինակներ
Мուտք | Ելք |
7
4 3 8 -2 9 0 2 | -2 0 2 3 4 8 9 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB