Trở về đầu
Mời các bạn download tại: Click here
#include <fstream>
#include <string.h>
#define fi "heapsort.INP"
#define fo "heapsort.OUT"
const int MAXN = 10000;
/// #define MAXN 10000
using namespace std;
int n;
int a[MAXN];
fstream f, g;
void Nhap() {
f.open(fi, ios::in);
f >> n;
int i, j;
for (i=1; i <= n; i++)
f >> a[i];
f.close();
}
void hoandoi(int & a, int & b){
int temp;
temp=a;
a=b;
b=temp;
}
void vundong(int i, int n) { /// O(log(n))
/// gia su j nhan gap doi lap k lan
/// vay 2^k = n
/// suy ra: k = log(n)
/// i là gốc
/// cây con trái của i là đống: 2*i
/// cây con phải của i là đống: 2*i + 1
int j = 2*i;
while (j <= n) {
if (j+1 <= n)
if (a[j] < a[j+1]) j = j+1;
/// a[j] là con lớn nhất của a[i]
if (a[j/2] < a[j]) {
hoandoi(a[j/2], a[j]);
j = 2*j;
}
else { /// a[j/2] >= a[j]
return; /// Không làm gì, kết thúc vun đống
}
}
}
void taodong() {
int i;
for (i=n/2; i>=1; i--)
vundong(i, n);
}
void sapxepvundong() {
taodong();
int i;
for (i=n; i>=2; i--) {
hoandoi(a[1], a[i]);
vundong(1, i-1);
}
}
void InKQ(){
g.open(fo, ios:: out);
for(int i=1; i<=n; i++)
g<<a[i]<<" ";
g.close();
}
int main() {
Nhap();
sapxepvundong();
InKQ();
}