हीप सॉर्ट एल्गोरिथ्म
हीप सॉर्ट एक तुलना-आधारित सॉर्टिंग एल्गोरिथ्म है, जो किसी ऐरे (array) को सुव्यवस्थित (sort) करने के लिए हीप डेटा स्ट्रक्चर का उपयोग करता है। इस एल्गोरिथ्म का मूल विचार यह है कि सबसे पहले ऐरे के तत्वों से एक हीप बनाई जाए। उसके बाद, जब तक हीप में कोई तत्व बचा हो, तब तक नियमित रूप से हीप से सबसे छोटा या सबसे बड़ा तत्व (इस बात पर निर्भर करता है कि आप मिन-हीप या मैक्स-हीप का इस्तेमाल कर रहे हैं) निकाला जाए और उसे ऐरे के अंतिम हिस्से में रख दिया जाए।
आपसे मिन-हीप का उपयोग करते हुए हीप सॉर्ट एल्गोरिथ्म को कार्यान्वित (implement) करने के लिए कहा गया है।
इनपुट
इनपुट की पहली पंक्ति में एक पूर्णांक
n (1 ≤ n ≤ 100 000) होता है, जो तत्वों की संख्या बताता है।अगली पंक्ति में
n स्थान-से-अलग किए गए पूर्णांक () होते हैं, जिन्हें क्रमबद्ध (sort) करना होता है।आउटपुट
प्रोग्राम को अंतिम क्रमबद्ध ऐरे को बढ़ते हुए क्रम में प्रिंट करना चाहिए।
उदाहरण
Input | Output |
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