✤  الگوریتم مرتب‌سازی هرمی

مرتب‌سازی هرمی (Heap Sort) یکی از روش‌های مشهور مرتب‌سازی داده‌ها است که بر اساس خصوصیات درخت heap (هیپ، هرم یا کپه)  و عملکرد آن پیاده‌سازی شده است.

بر اساس تعریف درخت heap، در یک max-heap (یا min-heap) بزرگترین (یا کوچکترین) مقدار بین داده‌ها همواره در ریشه درخت قرار دارد. یافتن بزرگترین (یا کوچکترین) عنصر بین عناصر، هزینه ثابت ( Ө( 1 دارد. با حذف این عنصر از درخت، بزرگترین (یا کوچکترین) عنصر بعدی مجددا در ریشه قرار می‌گیرد. به این ترتیب با حذف متوالی عناصر درخت heap و درج آنها در محل جدید، یک آرایه مرتب‌شده نزولی (یا صعودی) به دست خواهد آمد.

به عنوان نمونه، min-heap زیر را در نظر بگیرید:

  

درخت هیپ

  

مراحل مرتب‌سازی هرمی به ترتیب زیر خواهد بود:

  

Step 0 )   min-heap: 1, 4, 5, 8, 6, 9      -    list:

Step 1 )   min-heap: 4, 6, 5, 8, 9          -    list: 1

Step 2 )   min-heap: 5, 6, 9, 8              -    list: 1, 4

Step 3 )   min-heap: 6, 8, 9                  -    list: 1, 4, 5

Step 4 )   min-heap: 8, 9                      -    list: 1, 4, 5, 6

Step 5 )   min-heap: 9                          -    list: 1, 4, 5, 6, 8

Step 6 )   min-heap:                             -    list: 1, 4, 5, 6, 8, 9

  

در پایان، آرایه list شامل اطلاعات مرتب‌شده صعودی است.

  

بررسی پیچیدگی زمانی مرتب‌سازی هرمی

  [برگرد بالا]

برای مرتب‌کردن عناصر با استفاده از درخت heap، نیاز به n عمل حذف گره ریشه از درخت (یا عمل pop) وجود دارد. عمل حذف گره ریشه در درخت heap خود از مرتبه ( Θ( log n است. در نتیجه کل این عملیات از مرتبه ( Θ( n log n خواهد بود.

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

  

بررسی فضای مصرفی مرتب‌سازی هرمی

  [برگرد بالا]

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

درخت min-heap مثال فوق را در نظر بگیرید. با حذف عدد یک به عنوان گره ریشه درخت و اعمال تغییرات لازم به نتیجه زیر می‌رسیم:

  

مرتب‌سازی هرمی

  

خط عمودی پررنگ، انتهای اطلاعات درخت در آرایه را نشان می‌دهد. خانه شماره 6 حاوی اطلاعات سوخته و بلا استفاده است. پس می‌توانیم عنصر حذف شده را در آن قرار دهیم:

  

مرتب‌سازی هرمی

  

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

  

مرتب‌سازی هرمی

  

و با درج عنصر حذف شده در محل بلا استفاده:

  

مرتب‌سازی هرمی

  

به همین ترتیب با تکرار الگوریتم نتیجه نهایی حاصل می‌شود:

  

مرتب‌سازی هرمی

  

البته توجه داشته باشید که بر خلاف نتیجه نهایی روش قبل، در این حالت عناصر به صورت نزولی به دست آمده‌اند. یعنی در این روش از درخت min-heap برای مرتب‌سازی نزولی و از درخت max-heap برای مرتب‌سازی صعودی استفاده می‌شود.

مسعود اقدسی فام

مسعود اقدسی فام هستم.

دانش‌آموخته‌ی علوم کامپیوتر و فعال حوزه‌های علم داده و یادگیری ماشین؛ علاقه‌مند به یاد دادن و یاد گرفتن :)

algs.ir/spyqnyj     اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram
نوشته‌ها از این دست
       ✦   الگوریتم آنلاین
آخرین نوشته‌ها
       ✦   الگوریتم آنلاین
نوشته‌های پرمخاطب
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

پست الکترونیک (محرمانه):

متن پیام: *  

01 02 06 07 08 09 10 11 12 13 14

• مارالانی
یکشنبه، ۱۶ تیر ماه ۱۳۸۷، ساعت ۲۲:۰۲

عالی بود  .

مسعود اقدسی فام
یکشنبه، ۱۶ تیر ماه ۱۳۸۷، ساعت ۲۳:۱۱

مخلصیم مهدی جان.

• فرهاد
دوشنبه، ۱۷ تیر ماه ۱۳۸۷، ساعت ۱۳:۵۹

مسعود جان واقعا دمت گرم خسته نباشی ، سایت خیلی خوبی دارین.

مسعود اقدسی فام
دوشنبه، ۱۷ تیر ماه ۱۳۸۷، ساعت ۲۳:۰۱

ارادتمندم فرهاد جان. این سایت فقط کار من نیست. دوستان عزیز دیگه ای هم زحمت می کشن. ممنون از لطفت.

• عسل
دوشنبه، ۱۴ بهمن ماه ۱۳۸۷، ساعت ۱۱:۴۴

سلام

دستتون دردنکنه بابت این سایت واقعاً مفید و به درد بخوره فقط یه سوال داشتم آقایون تابع های مرتب سازی را که نوشتید وقتی اونا رو توی کلاس می نویسم در برنامه اصلی چه جوری باید فراخوانی کنم ؟ لطفاً کمکم کنید

• مجید نصیری
شنبه، ۱ فروردین ماه ۱۳۸۸، ساعت ۲۲:۲۸

واقعا دمتون گرم خسته نباشید ، سایت خیلی خوبی دارین.

• مینا
چهارشنبه، ۲ اردیبهشت ماه ۱۳۸۸، ساعت ۱۲:۰۰

ba salam be shoam man barnamei mikham ke tamame algorithm haye moratab sazi ro piade sazi koneage mishe in barnama ro baram mail bezanid  mozo  kheili hayatie ba tashkor az tamame dostan

• mina
چهارشنبه، ۲ اردیبهشت ماه ۱۳۸۸، ساعت ۱۲:۰۲

این سایت واقعا عالیه  خسته نباشید

• نجمه
جمعه، ۶ آبان ماه ۱۳۹۰، ساعت ۲۳:۲۵

خیلی ممنون

خیلی خوبه...کاش کد هرمی رو هم قرار داده بودید060612

• حسین
چهارشنبه، ۷ دی ماه ۱۳۹۰، ساعت ۲۰:۰۲

لطفا کد هرمی رو هم قرار دهید

• محسن
جمعه، ۳۰ دی ماه ۱۳۹۰، ساعت ۰۹:۵۴

ممنون ..

• منادی
یکشنبه، ۲ بهمن ماه ۱۳۹۰، ساعت ۱۵:۵۷

پرمحتوایی داری

متشکر

12

• ali
یکشنبه، ۲۱ آبان ماه ۱۳۹۱، ساعت ۲۰:۳۸

aliiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii     ey kash code  boodeesh.ke  beshe  khodemon trace konim motevajeh beshiim

یکشنبه، ۲۱ آبان ماه ۱۳۹۱، ساعت ۲۰:۵۹
• مسعود اقدسی فام

ممنون دوستان عزیز.

کد در قسمت معرفی درخت هیپ موجوده.

• شیوا
دوشنبه، ۱۳ آذر ماه ۱۳۹۱، ساعت ۱۳:۰۶

سلام اگه میشه در مورد این سوال منو راهنمایی کنید:

برنامه ای بنویسید که با دریافت عدد nمشخص کند با این عدد چه تعداد max-heap می توان ساخت به عنوان مثال اگر کاربر عدد 7 را وارد کند پاسخ 80 میشود.

گفتن باید یک فرمول دربیارید!!!!!!

• ارد
سه‌شنبه، ۱۴ آذر ماه ۱۳۹۱، ساعت ۰۷:۵۰

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

هاراهم به مطالبتان اضافه فرمایید.01

• محمد
شنبه، ۲ دی ماه ۱۳۹۱، ساعت ۱۰:۱۳

با سلام خدمت شما دوست عزیز یک سوال از شما داشتم.

مرتبه زمانی الگوریتم هافمن برابر تتا (n log n) بر اساس عملکرد هافمن و بررسی مفهوم maxheap و minheap تحلیل کنید چرا مرتبه ی زمانی هافمن برابر زمان ذکر شده است؟

با تشکر

ضمناً مطالب سایت آموزنده می باشد.

• فرزاد کمالی فر
شنبه، ۱۶ دی ماه ۱۳۹۱، ساعت ۲۳:۲۲

توضیحات روان و قابل درک بود

متشکر

• مریم
سه‌شنبه، ۲۴ اردیبهشت ماه ۱۳۹۲، ساعت ۱۴:۲۳

با سلام حذف یک عنصر از درخت مکس هیپ رو میخواستم

• محمدعلی
یکشنبه، ۲۰ مرداد ماه ۱۳۹۲، ساعت ۱۹:۳۹

حذف از درخت مکس هیپ از ریشه صورت میگیرد به این صورت آخرین داده درخت (که کامل بودن درخت را نقض نکند) به جای ریشه قرار میگیرد و مجددا عمل heaping انجام میشود. به سایت ماهم سر بزنید:

mohajerunivercity.blogfa.com

• نجمه
سه‌شنبه، ۱۹ فروردین ماه ۱۳۹۳، ساعت ۱۴:۲۲

سلام

عالی بود

ممنون01

• علی
سه‌شنبه، ۱۳ خرداد ماه ۱۳۹۳، ساعت ۱۴:۵۵

خواهشن کد...

• simon
چهارشنبه، ۱۹ تیر ماه ۱۳۹۸، ساعت ۱۵:۰۷

عالی

خسته نباشید