همون طوری که در سوال گفته میخواهیم بجای هرم از جستجوی خطی استفاده کنیم
۱- آیا حالت پیش فرض برای ساخت هافمن درخت هیپه؟
۲- چرا از مرتبه n^2 هست؟
heap tanha bozorgtarin ro moarefe mikard va be ertefa vabaste bood
jostojoye khate
be tedad anasor vabaste ast va dar badtarin halat hey bayad
max ro dar n onsor peyda kone
farsi im hang karde ozrkhaham
(۲۰ بهمن ۱۳۹۰ ۰۲:۰۵ ق.ظ)mjjoon نوشته شده توسط: در کل در اکثر مسائل حریصانه هیپ جایگاه خاصی داره چون ما در مسائل حریصانه با اولویت کار داریم. و هیپ برای پیاده سازی اولویته.
در مورد سوال دوم تحلیل من اینه که در ابتدای کار شما میتونی با مرتب سازی از مرتبه nlogn مرتب کنی . اما هر بار که ۲ کاراکتر با کمترین فرکانس تکرار رو جمع کنی از ابتدای آرایه مرتب بر میداری . حالا هر بار باید حاصل جمع این دو رو باز در آرایه مرتب وارد کنی و دوباره آرایه مرتب بسازی و این کار با یک مرحله از الگوریتم مرتب سازی درجی با مرتبه n انجام میشه. منتها شما این کار رو به اندازه n-1 بار انجام میدید که در کل میشه از مرتبه n به توان دو.
یه موضوعی:
مطمئنید که بعد از انتخاب ۲ مورد در آرایه‌ی مرتب٬ باز هم نیاز به مرتب سازی هست؟ فرضاً اگر ترکیب ۲ کاراکتر رو داشته باشیم٬ به نظرتون نمیشه بدون مرتب‌سازی هم ترکیب بعدی رو پیدا کرد؟ یا اشتباه می‌کنم؟ (البته منظورم مرتب‌سازی دوباره‌ی آرایه با ترکیب جدید هست)