⬡ Heap Sort Visualizer

الگوریتم Heap Sort چیست؟

مرتب‌سازی هرمی (Heap Sort) یک الگوریتم مرتب‌سازی مبتنی بر مقایسه است که از ساختمان داده‌ی هرم دودویی (Binary Heap) استفاده می‌کند. این الگوریتم ابتدا آرایه ورودی را به یک Max-Heap تبدیل می‌کند و سپس با جابجایی ریشه (بزرگ‌ترین عنصر) با آخرین عنصر و کاهش اندازه هرم، آرایه را مرتب می‌کند.

Max-Heap یک درخت دودویی کامل است که در آن مقدار هر گره بزرگ‌تر یا مساوی مقدار فرزندانش است. ریشه درخت همیشه بزرگ‌ترین عنصر را نگه می‌دارد.

مراحل الگوریتم

1. 1 ساخت Max-Heap از آرایه ورودی (Build Max-Heap)
2. 2 جابجایی ریشه (بزرگ‌ترین عنصر) با آخرین عنصر آرایه
3. 3 کاهش اندازه هرم به اندازه یک واحد
4. 4 اجرای Heapify روی ریشه برای بازسازی خاصیت Max-Heap
5. 5 تکرار مراحل ۲ تا ۴ تا زمانی که اندازه هرم به ۱ برسد

شبه‌کد الگوریتم

void heapify(vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();

    // ساخت Max-Heap
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // استخراج عناصر از هرم
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}