هیپ فیبوناتچی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در علوم کامپیوتر، هیپ فیبوناتچی به داده ساختار هیپی اطلاق می‌شود که شامل انبوهی از درخت‌ها است. این هیپ زمان اجرای سرشکن بهتری نسبت به هیپ دوجمله ای دارد. هیپ‌های فیبوناتچی توسط مایکل فردمن و رابرت تارجن در سال ۱۹۸۴ ایجاد شده اند، و برای اولین بار در یک مقاله علمی در سال ۱۹۸۷ منتشر شدند. ایده نام هیپ فیبوناتچی از اعداد فیبوناتچی که در اجرای تحلیل زمانی از آن استفاده می شود، گرفته شده است.

اعمال درج، یافتن کوچکترین مقدار، کاهش کلید، و ادغام(الحاق) در زمان سرشکن ثابت کار می کنند. اعمال حذف و حذف کوچکترین مقدار در زمان سرشکن O(log n ) کار می کنند. این بدین معناست که با شروع از یک داده ساختار خالی، a عمل از دستورات گروه اول و b عمل از دستورات گروه دوم، زمان اجرای O(a+b log n) خواهد داشت. در هیپ‌های دو جمله انجام چنین عملی نیاز به زمان اجرای O((a + b)log (n)) دارد. بنابراین زمانی که b از a کوچکتر باشد استفاده از هیپ فیبوناتچی به مراتب بهتر از استفاده از هیپ دوجمله ای است.

استفاده از هیپ‌های فیبوناتچی برای صف‌های اولویت‌دار زمان اجرای بعضی از الگوریتم‌های مهم را بهبود می بخشد، مثل الگوریتم دیکسترا برای محاسبه کوتاهترین مسیر در گراف، و یا الگوریتم پریم برای محاسبه درخت فراگیر مینیمم در یک گراف.

ساختار[ویرایش]

شکل 1: نمونه یک هیپ فیبوناتچی، با سه درخت از درجه 0،1، و 3. سه راس علامت دارند (رنگ آبی)، بنابراین پتانیل هیپ 9 است.

هیپ فیبوناتچی مجموعه ای از درخت هاست خصوصیت مینیمم هیپ را داراست، به عبارتی، کلید فرزند همواره بزرگتر یا مساوی کلید پدر است. بنابراین کوچکترین کلید همواره در ریشه یکی از درخت‌های قرار دارد. در مقایسه با هیپ دو جمله ای، هیپ فیبوناتچی ساختار از قابلیت تغییر پذیری بیشتری برخورارد است. درخت‌ها شکل مشخصی ندارند و در بدترین حالت هیپ می تواند تمام عناصرش را در یک درخت جدا و یا یک تک درخت با عمق n ذخیره کند. این قابلیت تغییر پذیری را می توان برای کند اجرا کردن برنامه‌ها به کار گرفت تا اجرای بعضی اعمال را به تاخیر انداخت. به طور مثال ادغام هیپ هارا می توان به آسانی با به هم پیوستن دو لیست از درخت‌ها انجام داد، و عمل کاهش کلید بعضی اوقات یک گره را از پدر جدا کرده و یک درخت جدید تشکیل می دهد.

با این حال در برخی موارد بعضی از دستورها نیاز دارند که برای رسیدن به زمان مورد نظر در حال اجرا به پشته معرفی شوند . به طور خاص، درجه گره‌ها (در اینجا به معنی تعداد فرزندان) را کم در نظر گرفته‌ایم : هر گره دارای درجه حداکثر O(log n) و اندازه زیر درخت گره از درجه k حداقل Fk + ۲ است، که در آن Fk که k امین عدد فیبوناچی است. این امر از آنجا حاصل می‌شود که ما می توانیم حداکثر یک فرزند از هر گره غیرریشه را قطع کنیم. هنگامی که فرزند دوم قطع می شود، گره خود باید از پدر یا مادر خود بریده و تبدیل به ریشه درخت جدید شود( در زیر می توانید اثبات مرزهای درجه را ببینید). تعداد درختان در عملیات حذف کوچکترین مقدار کاهش می یابد، که در آن درختان با هم مرتبط هستند.

با توجه به ساختار راحت آن، انجام بعضی اعمال زمان طولانی لازم دارد در حالی که بعضی دیگر به سرعت انجام می شوند. در تحلیل زمان اجرای سرشکن ما وانمود می کنیم که اعمال خیلی سریع، کندتر از زمانی که باید اجرا شوند اجرا می شوند. این زمان اضافه در انتها از زمان اعمال کند کم می شود. این زمان ذخیره شده را می توان در هر زمانی با استفاده از تابع پتانسیل محاسبه نمود. پتانسیل هیپ فیبوناتچی با استفاده از فرمول زیر محاسبه می شود:

Potential = t + ۲m

که t در آن تعداد درختان هیپ فیبوناتچی است، و m تعداد گره‌های علامت گزاری شده است. گره علامت دار به گره ای گفته می‌شود که حداقل یکی از فرزندانش قطع شده باشد از زمانی که این گره خود فرزند گره دیگری شده بود (تمام ریشه‌ها بدون علامتند).

بنابراین، ریشه هر درخت در هیپ یک واحد زمان در خود ذخیره دارد. این واحد زمان را می توان برای پیوند دادن یک درخت با درخت دیگر در زمان سرشکن صفر استفاده کرد. هم چنین، هر گره علامت گذاری شده دو واحد زمان در خود ذخیره دارد. یک واحد برای جدا کردن گره از والدینش به کار می رود. اگر این اتفاق بیفتد، گره تبدیل به یک ریشه می‌شود و واحد زمان دوم در آن ذخیره می شود، مانند بقیه ریشه ها.

اجرای دستورات[ویرایش]

برای انجام سریع عملیات الحاق و پاک کردن، ریشه‌های تمام درختان توسط یک لیست پیوندی دوسویه به هم پیوند داده شده اند. فرزندان هر گره هم به همین روش به هم پیوند داده شده اند. برای هر گره، فرزندان آن را چه گره علامت دار باشد چه نباشد، حفظ می کنیم. هم چنین اشاره گری به ریشه که حاوی کوچکترین کلید است در نظر می گیریم.

عمل یافتن کوچکترین مقدار الان دیگر بی اهمیت است چونکه ما اشاره گری به گره داریم که حاوی آن است. این عمل پتانسیل هیپ را تحت تاثیر قرار نمی‌دهد، بنابراین مقدار دو هزینه سرشکن و واقعی ثابت خواهند ماند. همانطور که در بالا اشاره شد، عمل ادغام صرفاً با الحاق لیست ریشه‌های درخت دو هیپ انجام می شود. این عمل می تواند در زمان ثابت انجام شود و پتانسیل تغییر نکند، که باز هم منجر به زمان سرشکن ثابت می شود. عمل درج را می توان با ساختن یک هیپ جدید با یک عضو و انجام عمل ادغام، انجام داد. این عمل نیز در زمان ثابت انجام می شود، و پتانسیل یک واحد افزایش می یابد، به خاطر اینکه تعداد درختان افزایش می یابد. بنابراین این عمل سرشکن نیز ثابت است.

هیپ فیبوناتچی شکل 1 پس از اولین فاز استخراج مینیمم، گره با کلید 1 (مینیمم) پاک شده و فرزندانش به عنوان درختان جدید اضافه شده اند.

عمل استخراج مینیمم ( مانند پاک کردن مینیمم ) در سه فاز انجام می شود. اول ریشه ای که حاوی مینیمم است یافته و آن را پاک می کنیم. فرزندانش ریشه‌های درختان جدید خواهند شد. اگر تعداد فرزندان d باشد، زمان O(d) برای پردازش ریشه‌های جدید لازم خواهد بود و پتانسیل به اندازه d-۱ افزایش می یابد. بنابراین زمان اجرای سرشکن این فاز خواهد بود O(d)=O(log n) .

هیپ فیبوناتچی شکل 1 پس از اینکه استخراج مینیمم کامل شده است، ابتدا گره های 3 و 6 به هم پیوند زده می شوند. سپس نتیجه به درختی که ریشه در گره 2 دارد پیوند داده می شود. در آخر مینیمم جدید پیدا می شود .

برای کامل کردن عمل استخراج مینیمم، باید اشاره گر به ریشه حاوی مینیمم را به روز کنیم. متأسفانه ممکن است n ریشه برای بررسی کردن وجود داشته باشد. در فاز دوم با پیوند دادن ریشه‌های هم درجه تعداد ریشه‌ها را کاهش می دهیم. زمانی که دو ریشه u و v درجه یکسانی داشته باشند، ما یکی از آنها را فرزند دیگری قرار می دهیم در نتیجه آن که کلید کوچکتری دارد ریشه باقی می ماند. درجه اش یک واحد افزایش می یابد. این عمل تا آنجا ادامه می یابد تا همه ریشه‌ها درجه متفاوتی داشته باشند. برای یافتن درختان هم درجه، آرایه ای با طول O(log n ) و که به ریشه از هر درجه یک اشاره گر نگه می داریم. وقتی ریشه دومی از یک درجه پیدا شود، آن دو به پیوند داده می شوند و آرایه به روز می شود. زمان اجرای واقعی آن O(log n +m) که m تعداد ریشه‌ها در اول فاز دوم است. در آخر حداکثر O(log n) ریشه دارد ( چون هر کدام درجه متفاوتی دارد ). بنابراین کاهش پتانسیل حداقل m-O(log n) زمان اجرای سرشکن O(log n).

در فاز سوم ریشه‌های باقی‌مانده را بررسی می کنیم و مینیمم را پیدا می کنیم، این عمل زمان O(log n) می گیرد و پتانسیل تغییر نمی‌کند. پس زمان اجرای سرشکن کل استخراج مینیمم خواهد بود O(log n).

هیپ فیبوناتچی شکل 1 پس از کاهش کلید گره از 9 به 0. این گره همانند دو جد علامت زده اش از درخت ریشه در 1 جدا می شود و به عنوان ریشه جدید قرار می گیرد.

عمل کاهش کلید گره را می گیرد، کلید را کاهش می دهد و اگر خاصیت هیپ در حال از بین رفتن بود( کلید جدید کوچکتر از کلید والدین باشد )، گره از والدینش جدا می شود. اگر پدر ریشه نباشد، علامت زده می شود. اگر از قبل علامت زده باشد، قطع می‌شود و پدرش علامت زده می شود. انقدر بالا می رویم تا یا به یک ریشه برسیم یا به یک گره علامت نزده. در طول این اعمال تعدادی درخت جدید به طور مثال k تا به وجود می آوریم. تمام این درختان به جز اولی، علامت دار هستند اما به عنوان ریشه بدون علامت می شوند. یک گره می تواند علامت دار شود. بنابراین کاهش پتانسیل آن k-۲ خواهد بود. زمان واقعی برای اجرای عمل قطع کردن O(k) بود، بنابراین هزینه اجرای سرشکن ثابت است.

نهایتاً، عمل پاک کردن را می توان به آسانی با کاهش کلید عنصر تا بینهایت منفی، و آن را به مینیمم هیپ تبدیل می کند. سپس عمل استخراج مینیمم را صدا می زنیم تا آن را پاک کنیم. هزینه اجرای سرشکن این عمل O(log n).

اثبات مرزهای درجه[ویرایش]

اجرای سرشکن یک هیپ فیبوناتچی بستگی به درجه ( تعداد فرزندان ) ریشه درخت O(log n) دارد، که در آن n اندازه هیپ است. در اینجا ما می خواهیم نشان دهیم که اندازه (زیر)درخت که ریشه در گره x با درجه d در هیپ دارد، باید اندازه حداقل Fd، که Fk در آن k امین عدد فیبوناتچی است. مرز درجه از این و اینکه F_{d+2} \ge \varphi^d برای همه اعداد صحیح d\ge 0، که در آن \varphi = (1+\sqrt 5)/2 \doteq 1.62، نتیجه می شود(بعدها خواهیم داشت n \ge F_{d+2} \ge \varphi^d، که از آن نتیجه می‌شود \varphi).

گره دلخواه x را در هیپ در نظر بگیرید(نیازی نیست که ریشه یکی از درختان اصلی باشد). Size(x) را اندازه درختی که ریشه در گره x دارد تعریف می کنیم ( تعداد فرزندان x به علاوه خود x ). با استقراء روی ارتفاع x ( طول ساده‌ترین مسیر از x به شاخه فرزند )، اثبات می کنیم که size(x) ≥ Fd، که در آن d درجه x است.

شرایط اولیه: اگر ارتفاع x صفر باشد، آنگاه d صفر، و Size(x) = ۱ خواهد بود.

استقراء:فرض کنید x ارتفاع و درجه مثبت داشته باشد، فرض می کنیم y۱، y۲، ...، yd فرزندان x باشند که به ترتیب زمان مرتب شده‌اند ( y۱ اولین عنصر باشد )، و c۱، c۲، ...، cd به ترتیب درجه هایشان باشند. ما ادعا می کنیم که برای هر i با شرط ۲≤id، خواهیم داشت ci ≥ i-۲. قبل از اینکه yi فرزند x شود، y۱،...،yi-۱ فرزندهای x بوده اند، بنابراین x از درجه i-۱ بوده است. چون درخت‌های فقط زمانی با هم ادغام می شوند که درجه ریشه هایشان برابر باشد، نتیجه می‌شود که yi زمانی که فرزند x می شد حداقل از درجه i-۱ بوده. از آن زمان تا گنون، yi می تواند حداکثر یک فرزند را از دست داده باشد( با توجه به رویه علامت گذاری )، بنابراین ci حداقل i-۲ است، این ادعای ما را اثبات می کند.

از آن جهت که ارتفاع تمام yiها کمتر از x است، می توانیم فرض استقراء را به آن‌ها اعمال کنیم تا size(yi) ≥ Fci ≥ F(i-۲)+۲ = Fi را بدست آوریم. گره‌های x و y۱ هر کدام حداقل یک واحد به اندازه x اصافه می کنند، بنابراین خواهیم داشت:

\textbf{size}(x) \ge 2 + \sum_{i=2}^d \textbf{size}(y_i) \ge 2 + \sum_{i=2}^d F_i = 1 + \sum_{i=0}^d F_i.

با استفاده از یک استقراء ساده به این نتیجه می رسیم که برای هر d\ge 0، 1 + \sum_{i=0}^d F_i = F_{d+2}. که مرز پایین Size(x) را به ما می دهد.

بدترین حالت[ویرایش]

هر چند زمان اجرای کل این اعمال که از یک ساختار خالی شروع می شوند با مرزهای مشخص شده محدود شده است، اما تعداد کمی از اعمال مثل پاک کردن، و پاک کردن مینیمم از آن جهت که زمان اجرایشان خطی است، زمان طولانی برای اجرا خواهند داشت. به همین دلیل هیپ فیبوناتچی و دیگر داده ساختارهای سرشکن برای محاسبات زمان واقعی مناسب نیستند.

خلاصه زمان‌های اجرا[ویرایش]

لیست پیوندی درخت دودویی متعادل هیپ مینیمم هیپ فیبوناتچی صف برودال [۱]
درج O(1) O(log n) O(log n) O(1) O(1)
دسترسی به مینیمم O(n) O(log n) or O(1) (**) O(1) O(1) O(1)
پاک کردن مینیمم O(n) O(log n) O(log n) O(log n)* O(log n)
کاهش کلید O(1) O(log n) O(log n) O(1)* O(1)
پاک کردن O(n) O(log n) O(log n) O(log n)* O(log n)
ادغام O(1) O(m log(n+m)) O(m log(n+m)) O(1) O(1)

(*)زمان سرشکن
(**)با تغییرات جزئی در درخت دودویی معمولی


منابع[ویرایش]

پیوند به بیرون[ویرایش]