ہیپسورٹ ٹائم پیچیدگی

ایک ہیپ کو 'جزوی طور پر ترتیب دیا گیا' کہا جاتا ہے نہ کہ 'جزوی طور پر ترتیب دیا گیا'۔ لفظ 'ترتیب' کا مطلب ہے مکمل ترتیب (مکمل ترتیب)۔ ایک ڈھیر کو جزوی طور پر من مانی طور پر حکم نہیں دیا جاتا ہے۔ ایک ہیپ کو جزوی طور پر ایک معیار (پیٹرن) کے بعد ترتیب دیا گیا ہے، جیسا کہ ذیل میں دکھایا گیا ہے۔

لہذا، ہیپسورٹ دو مراحل پر مشتمل ہے: ہیپ کی تعمیر اور ڈھیر کے اوپر سے ترتیب شدہ عنصر کو نکالنا۔ دوسرے مرحلے میں، ہر نکالنے کے بعد، ڈھیر دوبارہ بنایا جاتا ہے۔ ہر تعمیر نو اصل عمارت کے عمل سے تیز ہوتی ہے کیونکہ دوبارہ تعمیر پچھلی تعمیر سے کی جاتی ہے، جہاں ایک عنصر کو ہٹا دیا گیا ہے۔ اور اس کے ساتھ، heapsort مکمل طور پر غیر ترتیب شدہ فہرست کو ترتیب دیتا ہے۔

اس مضمون کا مقصد مختصر طور پر ہیپسورٹ کی وضاحت کرنا اور پھر اس کی وقت کی پیچیدگی پیدا کرنا ہے (ذیل میں وقت کی پیچیدگی کے معنی دیکھیں)۔ آخر میں، کوڈنگ C++ میں کی جاتی ہے۔

کم از کم ڈھیر

ڈھیر کم از کم یا زیادہ سے زیادہ ڈھیر ہو سکتا ہے۔ ایک max-heap وہ ہے جہاں پہلا عنصر سب سے زیادہ عنصر ہے، اور پورے درخت یا متعلقہ فہرست کو جزوی طور پر نزولی ترتیب میں ترتیب دیا گیا ہے۔ ایک منٹ ہیپ وہ ہے جہاں پہلا عنصر کم سے کم عنصر ہے، اور پوری فہرست کو جزوی طور پر صعودی ترتیب میں ترتیب دیا گیا ہے۔ اس مضمون میں، صرف کم از کم ڈھیر پر غور کیا گیا ہے۔ نوٹ: ہیپ کے موضوع میں، ایک عنصر کو نوڈ بھی کہا جاتا ہے۔

ایک ڈھیر ایک مکمل بائنری درخت ہے۔ بائنری درخت کو ایک صف (فہرست) کے طور پر ظاہر کیا جا سکتا ہے؛ اوپر سے نیچے اور بائیں سے دائیں پڑھیں۔ کم ہیپ کے لیے ہیپ کی خاصیت یہ ہے کہ پیرنٹ نوڈ اس کے دو بچوں میں سے ہر ایک سے کم یا اس کے برابر ہے۔ غیر ترتیب شدہ فہرست کی ایک مثال یہ ہے:

اس جدول کی پہلی قطار صف کے عناصر ہیں۔ دوسری قطار میں صفر پر مبنی اشاریہ جات ہیں۔ عناصر کی اس فہرست کو درخت کے طور پر ظاہر کیا جا سکتا ہے۔ مکمل بائنری ٹری بنانے کے لیے کالعدم عناصر کو شامل کیا گیا ہے۔ سخت الفاظ میں، کالعدم عناصر فہرست (درخت) کا حصہ نہیں ہیں۔ اس فہرست میں کوئی ترتیب نہیں ہے، لہذا یہ ابھی تک کوئی ڈھیر نہیں ہے۔ ہیپ پراپرٹی کے مطابق جب اس کی جزوی ترتیب ہو جائے گی تو یہ ہیپ بن جائے گا۔

نوڈس اور اشاریہ جات کے درمیان تعلق

یاد رکھیں، ہیپ کنفیگریشن (ہیپ پراپرٹی) ہونے سے پہلے ہیپ ایک مکمل بائنری ٹری ہے۔ پچھلی فہرست ابھی تک ڈھیر نہیں ہے، کیونکہ عناصر ہیپ پراپرٹی کو نہیں مانتے۔ عناصر کو جزوی ترتیب میں کم سے کم ہیپ پراپرٹی کے مطابق دوبارہ ترتیب دینے کے بعد یہ ایک ہیپ بن جاتا ہے۔ جزوی ترتیب کو جزوی ترتیب کے طور پر دیکھا جا سکتا ہے (حالانکہ لفظ 'ترتیب' کا مطلب مکمل ترتیب ہے)۔

چاہے ایک بائنری درخت ڈھیر ہو یا نہ ہو، ہر والدین کے دو بچے ہوتے ہیں، سوائے لیف (آخری) نوڈس کے۔ ہر والدین اور اس کے بچوں کے درمیان اشاریہ جات میں ایک ریاضیاتی تعلق ہوتا ہے۔ یہ مندرجہ ذیل ہے: اگر والدین انڈیکس i پر ہیں، تو بائیں بچہ انڈیکس پر ہے:

اور صحیح بچہ انڈیکس پر ہے:

یہ صفر پر مبنی اشاریہ سازی کے لیے ہے۔ اور اس طرح، انڈیکس 0 پر والدین کا بائیں بچہ انڈیکس 2×0+1=1 پر ہوتا ہے اور اس کا دایاں بچہ 2×0+2=2 پر ہوتا ہے۔ انڈیکس 1 پر والدین کا بائیں بچہ انڈیکس 2×1+1=3 پر اور دایاں بچہ انڈیکس 2×1+2=4 پر ہوتا ہے۔ اور اسی طرح.

کم سے کم ہیپ پراپرٹی کے لحاظ سے، i میں والدین 2i+1 پر بائیں بچے سے کم یا اس کے برابر اور 2i+2 پر دائیں بچے سے کم یا اس کے برابر ہیں۔

ڈھیر

Heapifying کا مطلب ہے ڈھیر بنانا۔ اس کا مطلب فہرست کے عناصر (یا متعلقہ درخت) کو دوبارہ ترتیب دینا ہے تاکہ وہ ہیپ پراپرٹی کو پورا کر سکیں۔ ڈھیر لگانے کے عمل کے اختتام پر، فہرست یا درخت ایک ڈھیر ہے۔

اگر پچھلی غیر ترتیب شدہ فہرست کا ڈھیر لگا دیا جاتا ہے، تو یہ ہو جائے گا:

نوٹ: فہرست میں 12 عناصر ہیں نہ کہ 15۔ دوسری قطار میں اشاریہ جات ہیں۔ ڈھیر بنانے کے عمل میں، عناصر کی جانچ پڑتال کی جانی تھی، اور کچھ کو تبدیل کرنا تھا۔

دھیان دیں کہ سب سے چھوٹا اور پہلا عنصر 3 ہے۔ باقی عناصر ایک چڑھتے ہوئے لیکن غیر متزلزل انداز میں چلتے ہیں۔ اگر 2i+1 اور 2i+2 پوزیشن پر بائیں اور دائیں بچے ہر ایک i پر والدین سے زیادہ یا برابر ہیں، تو یہ ایک کم از کم ہیپ ہے۔ یہ مکمل ترتیب یا ترتیب نہیں ہے۔ ہیپ پراپرٹی کے مطابق یہ جزوی ترتیب ہے۔ یہیں سے ہیپ چھانٹنے کا اگلا مرحلہ شروع ہوتا ہے۔

Heapify وقت کی پیچیدگی

وقت کی پیچیدگی کچھ کوڈ کا رشتہ دار چلانے کا وقت ہے۔ اسے اس کوڈ کے مکمل ہونے کے لیے اہم کارروائیوں کی تعداد کے طور پر دیکھا جا سکتا ہے۔ ہیپ بلڈنگ کے لیے مختلف الگورتھم ہیں۔ سب سے زیادہ موثر اور تیز ترین مسلسل فہرست کو دو سے تقسیم کرتا ہے، نیچے سے عناصر کو چیک کرتا ہے، اور پھر عناصر کی کچھ تبدیلیاں کرتا ہے۔ فہرست میں N کو عملی عناصر کی تعداد ہونے دیں۔ اس الگورتھم کے ساتھ، مین آپریشنز (سواپنگ) کی زیادہ سے زیادہ تعداد N ہے۔ ہیپیفائنگ کے لیے وقت کی پیچیدگی پہلے اس طرح دی گئی ہے:

جہاں n N ہے اور مین آپریشنز کی زیادہ سے زیادہ ممکنہ تعداد ہے۔ اس اشارے کو Big-O نوٹیشن کہا جاتا ہے۔ یہ بڑے حروف میں O سے شروع ہوتا ہے، اس کے بعد قوسین ہوتا ہے۔ قوسین کے اندر ممکنہ سب سے زیادہ تعداد میں کارروائیوں کا اظہار ہے۔

یاد رکھیں: اضافہ ضرب بن سکتا ہے اگر ایک ہی چیز کو جوڑا جا رہا ہے دہرایا جائے۔

ہیپسورٹ کی مثال

پچھلی غیر ترتیب شدہ فہرست کو ہیپسورٹ کی وضاحت کے لیے استعمال کیا جائے گا۔ دی گئی فہرست یہ ہے:

فہرست سے تیار کردہ کم سے کم ہیپ یہ ہے:

ہیپسورٹ میں پہلا مرحلہ اس ہیپ کو تیار کرنا ہے جو تیار کیا گیا ہے۔ یہ جزوی طور پر ترتیب دی گئی فہرست ہے۔ یہ ایک ترتیب شدہ (مکمل طور پر ترتیب شدہ) فہرست نہیں ہے۔

دوسرا مرحلہ کم سے کم عنصر کو ہٹانے پر مشتمل ہے، جو کہ پہلا عنصر ہے، ڈھیر سے، بقیہ ہیپ کو دوبارہ ہیپ کرنا، اور نتائج میں سب سے کم عناصر کو ہٹانا۔ کم از کم عنصر ہمیشہ دوبارہ ہیپیفائیڈ ہیپ میں پہلا عنصر ہوتا ہے۔ عناصر کو ہٹا کر پھینک نہیں دیا جاتا ہے۔ انہیں جس ترتیب میں ہٹایا گیا ہے اس میں مختلف صفوں میں بھیجا جا سکتا ہے۔

آخر میں، نئی صف میں تمام عناصر کو صعودی ترتیب میں (مکمل طور پر) ترتیب دیا جائے گا۔ اور اب صرف جزوی طور پر آرڈر نہیں کیا گیا ہے۔

دوسرے مرحلے میں، سب سے پہلے 3 کو ہٹانا اور اسے نئی صف میں رکھنا ہے۔ نتائج یہ ہیں:

اور

پہلے عنصر کو نکالنے سے پہلے باقی عناصر کو ڈھیر لگانا پڑتا ہے۔ باقی عناصر کا ڈھیر بن سکتا ہے:

5 کو نکالنا اور نئی فہرست (سرنی) میں شامل کرنا نتائج دیتا ہے:

اور

بقیہ سیٹ کو ہیپ کرنے سے یہ ملے گا:

6 کو نکالنا اور نئی فہرست (سرنی) میں شامل کرنا نتائج دیتا ہے:

اور

بقیہ سیٹ کو ہیپ کرنے سے یہ ملے گا:

7 کو نکالنا اور اسے نئی فہرست میں شامل کرنا نتائج دیتا ہے:

اور

بقیہ سیٹ کو ہیپ کرنے سے یہ ملتا ہے:

9 کو نکالنا اور نئی فہرست میں شامل کرنا، نتائج دیتا ہے:

اور

بقیہ سیٹ کو ہیپ کرنے سے یہ ملتا ہے:

11 کو نکالنا اور اسے نئی فہرست میں شامل کرنا نتائج دیتا ہے:

اور

بقیہ سیٹ کو ہیپ کرنے سے یہ ملے گا:

14 کو نکالنا اور اسے نئی فہرست میں شامل کرنا نتائج دیتا ہے:

اور

بقیہ سیٹ کو ہیپ کرنے سے یہ ملے گا:

15 کو نکالنا اور اسے نئی فہرست میں شامل کرنا نتائج دیتا ہے:

اور

بقیہ سیٹ کو ہیپ کرنے سے یہ ملے گا:

17 کو نکالنا اور اسے نئی فہرست میں شامل کرنا نتائج دیتا ہے:

اور

بقیہ سیٹ کو ہیپ کرنے سے یہ ملے گا:

19 کو نکالنا اور اسے نئی فہرست میں شامل کرنا نتائج دیتا ہے:

اور

بقیہ سیٹ کو ہیپ کرنے سے یہ ملتا ہے:

22 کو نکالنا اور اسے نئی فہرست میں شامل کرنا نتائج دیتا ہے:

اور

بقیہ سیٹ کو ہیپ کرنے سے یہ ملتا ہے:

24 کو نکالنا اور اسے نئی فہرست میں شامل کرنا نتائج دیتا ہے:

اور

ہیپ سرنی اب خالی ہے۔ اس کے شروع میں جتنے بھی عناصر تھے وہ اب نئی صف (فہرست) میں ہیں اور ترتیب دیے گئے ہیں۔

ہیپسورٹ الگورتھم

اگرچہ قاری نے نصابی کتب میں پڑھا ہو گا کہ ہیپسورٹ دو مراحل پر مشتمل ہے، پھر بھی ہیپسورٹ کو ایک سٹیج پر مشتمل دیکھا جا سکتا ہے، جو بار بار دی گئی صف سے سکڑ جاتا ہے۔ اس کے ساتھ، ہیپسورٹ کے ساتھ ترتیب دینے کا الگورتھم درج ذیل ہے:

• غیر ترتیب شدہ فہرست کا ڈھیر بنائیں۔
• ہیپ کا پہلا عنصر نکالیں اور اسے نئی فہرست کے پہلے عنصر کے طور پر رکھیں۔
• بقیہ فہرست کو ہیپ کریں۔
• نئے ہیپ کا پہلا عنصر نکالیں اور نئی فہرست کے اگلے عنصر کے طور پر ڈالیں۔
• پچھلے مراحل کو ترتیب سے دہرائیں جب تک کہ ہیپ لسٹ خالی نہ ہو۔ آخر میں، نئی فہرست ترتیب دی گئی ہے۔

ہیپسورٹ ٹائم پیچیدگی مناسب

ہیپسورٹ کے لیے وقت کی پیچیدگی کا تعین کرنے کے لیے ایک مرحلے کا طریقہ استعمال کیا جاتا ہے۔ فرض کریں کہ 8 غیر ترتیب شدہ عناصر کو ترتیب دیا جانا ہے۔

آپریشنز کی ممکنہ زیادہ سے زیادہ تعداد یہ ہے:

ان کارروائیوں کی اوسط یہ ہے:

نوٹ کریں کہ پچھلی مثال میں آخری چار ڈھیر تبدیل نہیں ہوئے، جب پہلا عنصر ہٹا دیا گیا تھا۔ جب پہلا عنصر ہٹا دیا گیا تھا تو پچھلے ڈھیروں میں سے کچھ بھی تبدیل نہیں ہوئے تھے۔ اس کے ساتھ، مین آپریشنز کی بہتر اوسط تعداد 3 ہے نہ کہ 4.5۔ لہذا، مین آپریشنز کی ایک بہتر کل اوسط تعداد یہ ہے:

لاگ کے بعد سے _دو 8 = 3۔

عام طور پر، heapsort کے لیے اوسط کیس وقت کی پیچیدگی ہے:

جہاں ڈاٹ کا مطلب ہے ضرب اور n کا مطلب ہے N، فہرست میں عناصر کی کل تعداد (یا تو فہرست)۔

نوٹ کریں کہ پہلے عنصر کو نکالنے کے عمل کو نظر انداز کر دیا گیا ہے۔ وقت کی پیچیدگی کے موضوع پر، نسبتاً کم وقت لینے والے آپریشنز کو نظر انداز کر دیا جاتا ہے۔

C++ میں کوڈنگ

C++ کی الگورتھم لائبریری میں، ایک make_heap() فنکشن موجود ہے۔ نحو ہے:

یہ ویکٹر کے پہلے عنصر کی طرف اشارہ کرنے والے تکرار کنندہ کو اپنی پہلی دلیل کے طور پر لیتا ہے اور پھر ویکٹر کے اختتام سے بالکل آگے اشارہ کرنے والے کو اس کی آخری دلیل کے طور پر لیتا ہے۔ پچھلی غیر ترتیب شدہ فہرست کے لیے، کم از کم ہیپ حاصل کرنے کے لیے نحو کا استعمال اس طرح کیا جائے گا:

یہ کوڈ ویکٹر کے مواد کو کم از کم ہیپ کنفیگریشن میں تبدیل کرتا ہے۔ درج ذیل C++ ویکٹرز میں، دو صفوں کے بجائے دو ویکٹر استعمال کیے جائیں گے۔

ویکٹر کے پہلے عنصر کو کاپی کرنے اور واپس کرنے کے لیے، ویکٹر نحو کا استعمال کریں:

ویکٹر کے پہلے عنصر کو ہٹانے اور اسے پھینکنے کے لیے، ویکٹر نحو کا استعمال کریں:

ویکٹر (اگلا عنصر) کے پیچھے ایک عنصر شامل کرنے کے لیے، ویکٹر نحو کا استعمال کریں:

پروگرام کا آغاز یہ ہے:

الگورتھم اور ویکٹر لائبریریاں شامل ہیں۔ پروگرام میں اگلا ہیپسورٹ() فنکشن ہے، جو یہ ہے:

یہ ایک تکراری فعل ہے۔ یہ C++ الگورتھم لائبریری کا make_heap() فنکشن استعمال کرتا ہے۔ فنکشن ڈیفینیشن میں دوسرا کوڈ سیگمنٹ ہیپ بلڈنگ کے بعد پرانے ویکٹر سے پہلا عنصر نکالتا ہے اور نئے ویکٹر کے لیے اگلے عنصر کے طور پر شامل کرتا ہے۔ نوٹ کریں کہ فنکشن کی تعریف میں، ویکٹر پیرامیٹرز حوالہ جات ہیں، جبکہ فنکشن کو شناخت کنندگان (نام) کے ساتھ کہا جاتا ہے۔

اس کے لیے ایک مناسب C++ مین فنکشن یہ ہے:

آؤٹ پٹ ہے:

ترتیب دیا گیا (مکمل طور پر)۔

نتیجہ

مضمون میں ہیپ سورٹ کی نوعیت اور کام کے بارے میں تفصیل سے بحث کی گئی ہے جسے عام طور پر ہیپسورٹ کے نام سے جانا جاتا ہے، چھانٹنے والے الگورتھم کے طور پر۔ Heapify Time Complexity، Heapsort illustration، اور Heapsort بطور الگورتھم کا احاطہ کیا گیا اور مثالوں کے ذریعے اس کی تائید کی گئی۔ اچھی طرح سے لکھے گئے ہیپسورٹ پروگرام کے لیے اوسط وقت کی پیچیدگی O(nlog(n)) ہے