[Jungol] 정올 2082 힙정렬2 (Heap_Sort)

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2283&sca=4020

Approach

[그래프] 힙(Heap) 자료구조란? 

힙(Heap) 자료구조란?

▶ 최대힙(Max Heap)을 만들어 출력한다.

 

최대힙 특징

① 완전 이진 트리(Complete Binary Tree)

②  부모 노드의 값 ≥ 자식 노드의 값

  (마지막 노드가 반드시 전체원소의 최소값은 아닙니다.

   다만, 단말(leaf) 노드 중에 최소값은 존재합니다.)

③ 트리의 임의의 인덱스를 『K』라고 했을 때, 

    - Left Child → 2 * K

    - Right Child → 2 * K + 1

    - Parent Node → K / 2  

(시작 인덱스 = 1 ← 관계식을 쉽게 표현하기 위해 0보다는 1로 표현하기도 함)

---

#include <stdio.h>
 
const int LM = 1 << 19;
int N, heap[LM], heapSize;
inline void swap(int& a, int& b) { int t = a; a = b; b = t; }
 
void push_heap(int num) {
    heap[++heapSize] = num;
    int child = heapSize;
    while (child > 1 && heap[child] > heap[child / 2]) {
        swap(heap[child], heap[child / 2]);
        child /= 2;
    }
}
 
void pop_heap() {
    int parent = 1, child = 2;
    swap(heap[1], heap[heapSize--]);
    while (child <= heapSize) {
        if (child < heapSize && heap[child + 1] > heap[child])
            child++;
        if (heap[child] <= heap[parent])
            break;
        
        swap(heap[child], heap[parent]);
        parent = child, child *= 2;
    }
}
 
void output() {
    for (int i = 1; i <= N; ++i)
        printf("%d ", heap[i]);
    puts("");
}
 
void makeHeap() {
    int i, val;
    scanf("%d", &N);
    for (i = 0; i < N; ++i) {
        scanf("%d", &val);
        push_heap(val);
    }
    output();
}
 
void solve() {
    for (int i = 0; i < N; ++i) 
        pop_heap();
    output();
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    makeHeap();
    solve();
}