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

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

یک اجرا از الگوریتم مرتب‌سازی هرمی که یک آرایه از مقادیر پس و پیش تصادفی را مرتب می‌کند. در نخستین مرحله الگوریتم، عناصر آرایه برای راضی کردن هیپ دوباره مرتب می‌شوند. پیش از آنکه مرتب‌سازی حقیقی انجام شود، ساختار درختی هیپ بطور برای توضیح بطور مختصر نشان داده می‌شود.
کلاس الگوریتم مرتب‌سازی
داده ساختار آرایه
بدترین زمان اجرا O(n\log n)
بهترین زمان اجرا \Omega(n), O(n\log n)[۱]
زمان اجرای متوسط O(n\log n)
بدترین پیچیدگی حافظه O(1) کمکی
بهینه نه

مرتب‌سازی هرمی (به انگلیسی: Heapsort)، نوعی الگوریتم است که در آن از مقایسه برای چینش یک آرایه یا فهرست استفاده می‌شود. این الگوریتم بخشی از خانوادهٔ مرتب‌سازی انتخابی است. با وجود اینکه در اکثر رایانه‌ها از الگوریتم چینش سریع کند تر است ولی در بدترین حالت سرعت بالاتری (O(n\log n)) را دارا می‌باشد. این الگوریتم در محل است، ولی حالت پایداری ندارد.

در این مرتب سازی، ابتدا از کل آرایه داده شده یک درخت مکس هیپ (یا درخت مین هیپ) می‌سازد. سپس بزرگترین مقدار را بر می‌دارد و در انتهای آرایه مرتب شده قرار می‌دهد. بعد از حدف بزرگترین مقدار، دوباره از بقیه اعداد یک درخت مکس هییپ می‌سازد تا دومین عدد بزرگ یافت شود. بزرگ‌ترین مقدار در بین مقادیر باقی مانده را برمی دارد و آن را در مکان یکی قبل از انتهای آرایه قرار می‌دهد. این کار تا زمانی که هیچ مقداری در هرم باقی نماند و آرایه مرتب شده کامل شود، تکرار می‌شود.

یکی از روش‌های مرتب‌سازی داده‌هااست,که براساس خصوصیات درخت 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 عمل حذف گره ریشه از درخت دارد. عمل حذف گره ریشه در درخت heap خود از مرتبه (Θ(log n است. در نتیجه کل این عملیات از مرتبه (Θ(n log n خواهد بود. نکته قابل توجه دیگر، ساخت درخت heap از عناصر مورد نظر برای مرتب‌سازی است. در حالت عادی عناصر به صورت نامرتب و با چیدمان تصادفی در اختیار هر الگوریتم مرتب‌سازی قرار می‌گیرند. در این حالت یک هزینه زمانی دیگر برای ساخت درخت heap از روی چنین فهرستی مورد نیاز است.

بررسی فضای مصرفی مرتب‌سازی هرمی[ویرایش]

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

11dheap.PNG

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

12dheap.PNG

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

12dheap.PNG

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

13dheap.PNG

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

14dheap.PNG

15dheap.PNG

16dheap.PNG

17dheap.PNG

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

ساختن یک درخت Max-Heap[ویرایش]

می‌توانیم برای تبدیل آرایه[A[1..n به یک max-Heap که [n=length[A از روال MAX-HEAPIFY به روش پایین به بالا استفاده کنیم. از آنجایی که عناصر زیر آرایه [A[(n/2)+1)...n همگی برگ‌های درخت هستند و بنابراین هر کدام یک Heap یک عنصری برای شروع است، روالBUILD-MAX-HEAP در راستای گره‌های باقیمانده درخت حرکت کرده و برای هر یک MAX-HEAPIFY را اجرا می‌کند.

BUILD-MAX-HEAP(A)
1 heap-size=length[A]
2 for i=length[A]/2 downto 1
3 do MAX-HEAPIFY(A,i)

روال MAX-HEAPIFY[ویرایش]

MAX-HEAPIFY یک زیرروال مهم برای دستکاری max-Heapها است. ورودی آن آرایهA و اندیس i در آرایه‌است. زمانی که MAX-HEAPIFY فراخوانی می‌شود، فرض می‌شود که درخت‌های دودویی مشتق شده از فرزندان چپ و راستش،max-Heap هستند، ولی عنصر[A[iممکن است کوچکتر از فرزندانش باشد، بنابراین ویژگی max-Heap مورد تخطی قرار می‌گیرد. وظیفه MAX-HEAPIFY این است که مقدار موجود در [A[i را در max-Heap به پایین حرکت دهد تا زیر درخت مشتق شده ازi، یک max-Heapشود.

MAX-HEAPIFY(A,i)
1 l=LEFT(i)
2 r=RIGTH(i)
3 if(l≤heap-size[A] &&A[l[>A[i]
4 then largest=l
5 else largest=i
6 if(r≤heap-size[A] && A[r]>A[largest]
7 then largest=r
8 if (largest≠i)
9 then swap(A[i],A[largest])
10 MAX-HEAPIFY(A,largest)

شبه کد مرتب سازی هرمی[ویرایش]

دو نوع Heap دودویی وجود دارد:max-Heapها وmin-Heapها. در هر دو نوع، مقادیر درون گره‌ها ویژگی Heap را ارضاء می‌کنند که ویژگی‌های هرکدام به نوع Heap بستگی دارند. ویژگیmax-Heap این است که برای هر گره i به جزء ریشه:

A[PARENT(i)]>A[i]

به طوری که:

PARENT(i)
return i/2

به عبارت دیگر مقدار یک گره حداکثر برابر مقدار پدرش است؛ بنابراین بزرگترین عضو max-Heap در ریشه ذخیره می‌شود. ویژگی min-Heap به صورت بر عکس شکل می‌گیرد. کوچکترین عضو در ریشه قرار می‌گیرد. در این الگوریتم مرتب سازی ازmax-Heap استفاده کردیم.

 HEAPSORT(A)
1 BIULD-MAX-HEAP(A)
2 for(i=length [A] downto 2)
3 do swap(A[1],A[i])
4 Heap-size[A]=Heap-size[A]-1
5 MAX-HEAPIFY(A,1)

زمان اجرا[ویرایش]

روال HEAPSORT زمان (O(n lgn را صرف می‌کند چون فراخوانی BUILD-HEAPزمان (O(n و هر یک از n-1 فراخوانی MAX-HEAPIFY زمان (O(lgn را صرف می‌کند.

بررسی فضای مصرفی مرتب‌سازی هرمی[ویرایش]

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

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

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

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

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

روش مرتب‌سازی انتخابی (Selection Sort) یکی از روش‌های اولیه مرتب‌سازی بر اساس مقایسه عناصر است. این الگوریتم طی چند مرحله عناصر فهرست را به صورت صعودی یا نزولی مرتب می‌کند. به این ترتیب که در هر مرحله با بررسی عناصر نامرتب، بزرگترین (یا کوچکترین) عنصر را پیدا کرده، و به انتهای فهرست منتقل می‌کند. فهرست اعداد زیر را در نظر بگیرید، که باید به صورت صعودی (کوچک به بزرگ) مرتب شود:

2 8 4 1 7

در مرحله اول، کل فهرست از ابتدا تا انتها بررسی شده، و بزرگترین عنصر با عنصر انتهای فهرست نامرتب جابجا می‌شود:

1) 2 8 4 1 7 -> 2 7 4 1 8

در مرحله دوم، پیمایش از ابتدای فهرست تا عنصر چهارم صورت گرفته، و بزرگترین عنصر با عنصر انتهای آن جابجا می‌شود:

2) 2 7 4 1 8 -> 2 1 4 7 8

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

3) 2 1 4 7 8 -> 2 1 4 7 8

و در مرحله آخر دو عنصر باقیمانده مقایسه می‌شوند:

4) 2 1 4 7 8 -> 1 2 4 7 8

و به این ترتیب فهرست مرتب می‌شود.

پانویس[ویرایش]

منابع[ویرایش]

جستجو در ویکی‌انبار در ویکی‌انبار پرونده‌هایی دربارهٔ مرتب‌سازی هرمی موجود است.
  • ویکی‌پدیا انگلیسی
  • مقدمه‌ای بر الگوریتم‌ها - پدیدآورنده: تامس کورمن، چارلز لیزرسان، رونالد دیوست، کلیفورد اشتاین - گروه مهندسی-پژوهشی خوارزمی (مترجم) - ناشر: درخشش