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

مرتب‌سازی هرمی نوعی مرتب‌سازی مقایسه‌ای است که در پیچیدگی زمانی $\theta(n lg n)$ می‌تواند $n$ عدد را مرتب کند. منطق این مرتب‌سازی بسیار ساده بوده و مبتنی بر هرم است.

در ابتدا اعداد خود را در یک هرم اضافه کنید. برای این‌کار می‌توانید $n$ بار عملیات push روی یک هرم خالی انجام دهید. در این صورت پیچیدگی زمانی ساختن هرم از $\theta(n lg n)$ خواهد بود. راه دیگر ساختن هرم به طور مستقیم از روی $n$ عدد است که در $\theta(n)$ امکان‌پذیر است.

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

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

ساختن هرم از روی اعداد با توضیحات بالا در $O(n lg n)$ قابل انجام است. هربار عملیات pop از $O(lg n)$ است که پس در نهایت تمامی هزینه‌ی pop ها از $O(n lg n)$ خواهد بود. پس به طور کلی الگوریتم از $O(n lg 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;
}