سلام
می دونم که زمان ساخت یک صف اولویت از O(nlogn) هست اما چند جا دیدم که اون رو از مرتبه O(n) در نظر گرفتن. ممکنه یکی بهم توضیح بده که بالاخره کدوم درسته؟
(۲۶ فروردین ۱۳۹۵ ۱۲:۴۳ ب.ظ)NarimanN2 نوشته شده توسط: سلامچیزی که در کتاب داده ساختار دکتر قدسی نوشته اینه برای صف اولویت گفته همون هرم است بعدش برای هزینه تبدیل یک آرایه n عضوی به هرم بیشینه [tex]\langle n\rangle O[/tex] حساب کرده نه [tex]\langle nlogn\rangle O[/tex]
می دونم که زمان ساخت یک صف اولویت از O(nlogn) هست اما چند جا دیدم که اون رو از مرتبه O(n) در نظر گرفتن. ممکنه یکی بهم توضیح بده که بالاخره کدوم درسته؟
تو CLRS کاملاً روی این موضوع بحث شده. اجمالاً، ما از برگ‌ها (یعنی نیمه‌ی آخر آرایه) شروع می‌کنیم و حداکثر روی n/2 عنصر عمل Heapify که در حالت کلی (logn)O به حساب میاد رو انجام میدیم. اما نکته اینجاست که این برگ‌ها در اجدادشان با هم همپوشانی دارند و برآیند عملیات انجام گرفته توسط همه‌ی این Heapifyها بیش از (n)O نمیشه (برای اثباتش به کتاب مراجعه کنید).
امیدوارم اشتباه نکرده باشم، چون مدت‌ها پیش خوندمش.
تا اونجایی که من میدونم بحث صف لولویت و هیپ از هم جدتست
صف اولویت رو در حالت کلی سه جور میشه ساخت
۱- لیست مرتب با مرتبه n به توان ۲
۲- لییت نا مرتب با مرتبه n
۳- هیپ با مرتبه nlogn
Sent from my HTC One_E8 dual sim using Tapatalk