حل تشریحی سوال شماره 16 ساختمان داده ها و طراحی الگوریتم ها
کنکور دکتری مهندسی کامپیوتر 1404
فرض کنید یک هرم دودویی کامل (Complete Binary Heap)، به صورت آرایه پیاده سازی شده است. می خواهیم یک الگوریتم بهینه طراحی کنیم که بدون تغییر ساختار هرم، دومین بزرگ ترین مقدار در هرم بیشینه (Max-Heap) را پیدا کند. کدام یک از موارد زیر درست است؟
دومین بزرگ ترین مقدار در یک هرم بیشینه همیشه در آخرین سطح هرم قرار دارد و می توان آن را در زمان O(1) پیدا کرد.
دومین بزرگ ترین مقدار در یک هرم بیشینه همیشه یکی از دو فرزند گره ریشه است و می توان آن را در زمان O(1) با مقایسه مقادیر این دو گره به دست آورد.
برای پیدا کردن دومین بزرگ ترین مقدار در یک هرم بیشینه، تنها کافی است گره های فرزند ریشه (سطح اول زیر ریشه) ر بررسی کنیم. این فرایند پیچیدگی زمانی O(logn) دارد.
برای پیدا کردن دومین بزرگ ترین مقدار در یک هرم بیشینه، باید تمام گره های هرم بررسی شوند، زیرا دومین بزرگ ترین مقدار ممکن است در هر سطح قرار داشته باشد. ین فرایند پیچیدگی زمانی o(N) دارد.