Trở về đầu

foto1 foto2 foto3 foto4 foto5
Giảng viên
Nguyễn Tô Sơn - Thủ khoa Đại học Sư phạm Hà Nội
ĐT: 091.333.2869

HỌC TIN CÙNG THỦ KHOA

Thành công không phải đích đến, mà là cả một hành trình

Tìm kiếm

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();

}

Giảng viên Nguyễn Tô Sơn, Thủ khoa Đại học Sư phạm Hà Nội. Điện thoại: 091.333.2869