مرتب‌سازی هرمی (Heap Sort) نوعی مرتب‌سازی مقایسه‌ای است که در پیچیدگی زمانی $\mathcal{\Theta}(n \log n)$ می‌تواند $n$ عدد را مرتب کند. منطق این مرتب‌سازی بسیار ساده بوده و مبتنی بر هرم است.

در ابتدا اعداد خود را در یک هرم اضافه کنید. برای این‌کار می‌توانید $n$ بار عملیات اضافه کردن روی یک هرم خالی انجام دهید. در این صورت پیچیدگی زمانی ساختن هرم از $\mathcal{O}(n \log n)$ خواهد بود. راه دیگر ساختن هرم به طور مستقیم از روی $n$ عدد است که در $\mathcal{\Theta}(n)$ امکان‌پذیر است.

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

در توضیحات بالا هیچ اشاره‌ای به مقایسه‌ی دو عنصر نشده است. با این وجود توجه کنید که برای پیاده‌سازی یک هرم نیاز است که عناصر قابل مقایسه باشند. در حقیقت، مقایسه‌ی عناصر در درون هرم انجام می‌شود.

ساختن هرم از روی اعداد با توضیحات بالا در $\mathcal{O}(n \log n)$ قابل انجام است. عملیات حذف از $\mathcal{O}(\log n)$ است که پس در نهایت در مجموع برای حذف‌کردن‌ها از $\mathcal{O}(n \log n)$ عملیات استفاده شده است. پس به طور کلی الگوریتم از $\mathcal{O}(n \log n)$ است.

heap_sort.cpp

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
priority_queue<int> p; // std implementation of max-heap
vector<int> v;
 
int main()
{
	int n;
	cin >> n;
	// Building heap
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		p.push(x);
	}
	// Pop operations
	for (int i = 0; i < n; i++)
	{
		v.push_back(p.top());
		p.pop();
	}
 
	for (int i = 0; i < n; i++)
		cout << v[i] << " ";
	cout << endl;
}

• https://en.wikipedia.org/wiki/Heapsort