प्रौद्योगिकी साझेदारी

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

राशः

राशः प्राथमिकता च पङ्क्तिः : १.

प्राथमिकतापङ्क्तिः अमूर्तदत्तांशप्रकारः अस्ति, तथा च राशौ दत्तांशसंरचना अस्ति, अतः राशौ प्राथमिकतापङ्क्तिः न भवति ।
प्राथमिकतापङ्क्तयः कार्यान्वितुं बहवः उपायाः सन्ति, यथा सरणीः, लिङ्क्ड् सूचीः च । परन्तु एते कार्यान्वयनम् केवलं गारण्टीं दातुं शक्नुवन्ति यत् सम्मिलन-विलोपन-क्रियासु एकं O(1)O(1) समयजटिलतायां सम्पन्नं कर्तुं शक्यते, यदा तु अन्यं कार्यं O(N)O(N) Completed within the कालजटिलता। ढेरः प्राथमिकतापङ्क्तिस्य सम्मिलनक्रियां O(log N)O(logN) इत्यस्य समयजटिलतायाः अन्तः पूर्णं कर्तुं सक्षमं कर्तुं शक्नोति, तथा च O(log N)O(logN) इत्यस्य समयजटिलतायाः अन्तः विलोपनक्रियायाः पूर्णतां कर्तुं शक्नोति । .

राशौ एकः विशेषः द्विचक्रीयः वृक्षः अस्ति यः निम्नलिखितशर्ताः पूरयति ।

1. सम्पूर्णः द्विचक्रीयवृक्षः (नोड्स् वामतः दक्षिणतः क्रमेण स्थापिताः भवन्ति);
2. प्रत्येकस्य नोडस्य मूल्यं तस्य बालनोडस्य मूल्यात् अधिकं वा समं वा न्यूनं वा समानं वा भवितुमर्हति।

राशेः विशेषताः : १.

1. O(logN) समयजटिलतायां राशेः तत्त्वानि सम्मिलितुं शक्यन्ते;
2. O(logN) समयजटिलतायां राशेः तत्त्वानि विलोपयितुं शक्यन्ते;
3. राशे अधिकतमं न्यूनतमं वा मूल्यं O(1) समयजटिलतायाः अन्तः प्राप्तुं शक्यते ।

राशौ वर्गीकरणम् : १.

Max heap: ढेरस्य प्रत्येकस्य नोड् इत्यस्य मूल्यं तस्य बालनोड् इत्यस्य मूल्यात् अधिकं वा समानं वा भवति । max heap इत्यस्य उपरितनं तत्त्वं (root node) राशेः अधिकतमं मूल्यं भवति ।
न्यूनतमं राशौ : राशौ प्रत्येकस्य नोड् इत्यस्य मूल्यं तस्य बालनोड् इत्यस्य मूल्यात् न्यूनं वा समानं वा भवति । min-heap इत्यस्य उपरितनतत्त्वं (root node) राशेः न्यूनतमं मूल्यं भवति ।
वर्तमान नोड् सङ्ख्या i, वामबालकसङ्ख्या 2i, दक्षिणबालकसङ्ख्या 2i+1 च ।

कालजटिलता अन्तरिक्षजटिलता च

राशः प्रकारः

सिद्धान्तः : Heap sort इति अक्रमिततत्त्वानां समुच्चयं क्रमयितुं heap इत्यस्य data structure इत्यस्य उपयोगं निर्दिशति ।

min-heap sort algorithm इत्यस्य सोपानानि निम्नलिखितरूपेण सन्ति ।

सर्वाणि तत्त्वानि न्यूनतमराशिरूपेण राशौ कुर्वन्तु;
राशेः उपरितनतत्त्वं बहिः निष्कास्य विलोपयन्तु, तथा च क्रमिततत्त्वानि संग्रहयति इति दत्तांशसमूहे T मध्ये राशेः उपरितनतत्त्वं स्थापयन्तु;
अस्मिन् समये, राशौ नूतनं न्यूनतमराशिं प्रति समायोजितः भविष्यति;
यावत् राशेः तत्त्वानि न सन्ति तावत् यावत् ३, ४ च पदानि पुनः पुनः कुर्वन्तु;
अस्मिन् क्षणे नूतनः दत्तांशसमूहः T प्राप्यते, यस्मिन् तत्त्वानि लघुतः बृहत्पर्यन्तं क्रमेण व्यवस्थितानि भवन्ति ।

max heap sort algorithm इत्यस्य सोपानानि निम्नलिखितरूपेण सन्ति ।

सर्वाणि तत्त्वानि अधिकतमराशिरूपेण राशौ कुर्वन्तु;
राशेः उपरितनतत्त्वं बहिः निष्कास्य विलोपयन्तु, तथा च क्रमिततत्त्वानि संग्रहयति इति दत्तांशसमूहे T मध्ये राशेः उपरितनतत्त्वं स्थापयन्तु;
अस्मिन् समये, राशौ नूतनं अधिकतमराशिं प्रति समायोजितः भविष्यति;
यावत् राशेः तत्त्वानि न सन्ति तावत् यावत् ३, ४ च पदानि पुनः पुनः कुर्वन्तु;
अस्मिन् क्षणे नूतनः दत्तांशसमूहः T प्राप्यते, यस्मिन् तत्त्वानि बृहत्तः लघुपर्यन्तं क्रमेण व्यवस्थितानि भवन्ति ।
समय जटिलता: O(Nlog N). N इति राशौ तत्त्वानां संख्या ।

अन्तरिक्ष जटिलता : O(N). N इति राशौ तत्त्वानां संख्या ।