[νκ³Ό νμ λ ¬] ν μ λ ¬ (μμ°¨ν, μ΅λν)
[μ μ리 ν μ λ ¬]
- ν μμ± λ°©μμ μ½μ μ, μν₯μ μ€ μ무거λ μ¬μ©
- μμ°¨νμ ν΅ν΄ ꡬννλ€λ©΄ μΆκ° λ©λͺ¨λ¦¬λ₯Ό μ¬μ©νμ§ μκ³ μ μ리 ν μ λ ¬μ΄ κ°λ₯ν¨
- μ μΌν€
- μ€λ³΅ν€
- μ€λ³΅ ν€λ₯Ό μ²λ¦¬ν μ μλλ‘ μμ±λ μκ³ λ¦¬μ¦μ μ μΌ ν€ νκ²½μμλ μ νν μλνλ€. νμ§λ§ μ μΌ ν€λ₯Ό μ²λ¦¬ν μ μλλ‘ μμ±λ μκ³ λ¦¬μ¦μ μ€λ³΅ ν€ νκ²½μμλ μ νν μλνλ€λ 보μ₯μ μμ >> μ μΌν€ μκ³ λ¦¬μ¦μ = (λ±νΈ) κ²½μ°λ₯Ό λΉΌμ§μμλ€λ©΄ μ€λ³΅ν€ νκ²½μμλ μλν κ²μ΄λΌκ³ κ΅μλμ΄ κ°μ μ€ μΈκΈνμ¬
μλ μ½λλ μν₯μμΌλ‘ νμ μμ±νκ³ μ¬κ·ν¨μλ₯Ό μ΄μ©ν΄μ μ μ리 ν μ λ ¬μ νλ μκ³ λ¦¬μ¦μ΄λ€.
#include <stdio.h>
#include <stdlib.h>
int H[99];// ν
int n;// ν€ κ°μ(νμ ν¬κΈ°)
int s;// νμ μλ ν¬κΈ° μ μ₯ν λ³μ
void downHeap(int i) {
int left = i * 2;//μΌμͺ½ μμ
int right = i * 2 + 1;//μ€λ₯Έμͺ½ μμ
int big, tmp;
if (n < left && n < right)
return;
big = left;
if (n >= right) {
if (H[big] < H[right]) {
big = right;
}
}
if (H[big] <= H[i])
return;
tmp = H[i];
H[i] = H[big];
H[big] = tmp;
downHeap(big);
}
void rBuildHeap(int i) { // μν₯μ ν μμ± ν¨μ
if (i > n)
return;
rBuildHeap(i * 2);
rBuildHeap(i * 2 + 1);
downHeap(i);
return;
}
void inPlaceHeapSort() { // μ μ리 ν μ λ ¬ ν¨μ
int tmp;
s = n;
for (int i = n; i >= 2; i--) {
tmp = H[1];
H[1] = H[i];
H[i] = tmp;
n--;
downHeap(1);
}
}
void printArray() {
for (int i = 1; i <= s; i++) {
printf(" %d", H[i]);
}
printf("\n");
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &H[i]);
getchar();
}
rBuildHeap(1);
inPlaceHeapSort();
printArray();
return 0;
}