صف اولویت
Priority QueuePriority Queue داده را بر اساس اولویت خارج می‌کند، نه لزوماً بر اساس زمان ورود. معمولاً با Heap پیاده‌سازی می‌شود.
اول این مفهوم را در ذهن نگه دار
Priority Queue داده را بر اساس اولویت خارج می‌کند، نه لزوماً بر اساس زمان ورود. معمولاً با Heap پیاده‌سازی می‌شود.
چطور کار می‌کند؟ ساده و مرحله‌ای
Priority Queue یک مفهوم انتزاعی است و Heap یکی از پیاده‌سازی‌های رایج آن است.
هرجا مرتب لازم است بهترین یا مهم‌ترین آیتم بعدی انتخاب شود، این ساختار کاربرد دارد.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
Invariant اصلی ساختار را مشخص کن.
مسیر read/update را در ساختار دنبال کن.
بعد از mutation قبل از return invariant را دوباره برقرار کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای صف اولویت هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
insert/remove O(log n)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- Dijkstra/A*
- Schedulerها
- شبیه‌سازی eventها
کجا معمولاً اشتباه می‌کنیم؟
- پیچیدگی را بدون فهم representation حفظ نکن.
- بدترین شکل ساختار یا هزینه resize/rebalance را نادیده نگیر.
مدل یک پاسخ حرفه‌ای
در مصاحبه فرق ADT و implementation را بگو: Priority Queue رفتار را تعریف می‌کند و Binary Heap یکی از راه‌های پیاده‌سازی آن است.
صف اولویت چه مسئله‌ای را حل می‌کند؟
Priority Queue داده را بر اساس اولویت خارج می‌کند، نه لزوماً بر اساس زمان ورود. معمولاً با Heap پیاده‌سازی می‌شود.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا insert/remove O(log n) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
پیچیدگی را بدون فهم representation حفظ نکن.