Heap एक tree पर आधारित डेटा स्ट्रक्चर है जिसकी कुछ विशेष गुणधर्म होते है।
heap की निम्न बेसिक जरूरतें है:-
· Heap डेटा स्ट्रक्चर हमेशा एक complete binary tree (CBT) होता है अर्थात tree के सभी स्तर पूरी तरह से भरे हुए हों।
· प्रत्येक नोड में जो वैल्यू रखी है वह अपने दो children से बड़ी या बराबर होगी, इस heap को हम max heap कहते है।
या
प्रत्येक नोड में जो वैल्यू रखी है वह अपने दो children से छोटी या बराबर होगी, इस heap को हम min heap कहते है। अगर हम लिस्ट को ascending order (बढ़ते क्रम) में sort करना चाहते है तो हम min heap को create करते है। अगर हम लिस्ट को descending order (घटते क्रम) में sort करना चाहते है तो हम max heap को create करते है। heap sort की complexity merge sort की तरह O (n log n) होती है।
Heap Sort Algorithm
यह Algorithm max heap sort के लिए है।
step 1. Heap में नया नोड बनाओ।
step 2. नोड को एक वैल्यू assign करो।
step 3. child नोड की वैल्यू को parent नोड की वैल्यू के साथ compare करो ।
step 4. यदि parent node < child node से तो उन्हें आपस में बदल दो (swap कर दो)
step 5. स्टेप 3 तथा 4 को तब तक repeat करो जब तक कि heap सही ढंग से न बन जाएँ ।