[백준/c++] 최대 힙

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

---

 

힙 자료구조 c++로 직접 구현 (힙 라이브러리 x)

#include <iostream>
#define HEAP_SIZE 100000

using namespace std;

int heap[HEAP_SIZE];
int heap_count = 0;

void swap(int*a, int*b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void push(int data){
    heap_count ++;
    heap[heap_count] = data;
    int child = heap_count;
    int parent = heap_count/2;
    while (child>1 && heap[child]>heap[parent]){
        swap(&heap[child], &heap[parent]);
        child = parent;
        parent = child/2;
    }
}

void pop(){
    if (heap_count <= 0) {cout << 0 << "\n";}
    else {
        cout << heap[1] << "\n"; //나중에 Return
        swap(&heap[1], &heap[heap_count]);
        heap_count--;

        int parent = 1;
        int child = 2;
        if ((heap_count > 2) && (heap[child+1]>heap[child])) {
            child ++;}

        while ((child <= heap_count) && heap[parent] < heap[child]) {
            swap(&heap[parent], &heap[child]);

            parent = child;
            child = parent * 2;
            if (child <= heap_count){
                if ((child < heap_count) && (heap[child+1] > heap[child])){
                    child ++;
                }
            }
            else {break;}
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int N;
    cin>>N;
    int input;
    for (int i=0; i<N; i++){
        cin >> input;
        if (input==0){
            pop();
        }
        else {
            push(input);
        }
    }
}

😁

메모

- pointer를 사용한 swap 함수: 주소는 그대로, 해당 주소에 아이템 자체를 바꿈

- pop함수에 유의

특히, 인덱스 다룰 때는 반드시 해당 인덱스 value가 False가 아닌지 조건문으로 먼저 체크해야 함!!!⭐️✌️

 

- 조건연산자 개념

(condition) ? value_if_true : value_if_false

//condition이 참이면 value_if_true가 반환됩니다.
//condition이 거짓이면 value_if_false가 반환됩니다.

int a = 5;
int b = 8;
int max_value = (a > b) ? a : b;
//max_value에는 b의 값인 8이 할당

 

- 시간초과 관련 팁

1) ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); 

2) endl; 말고 "\n"

https://www.acmicpc.net/board/view/22716

글 읽기 - 추가 설명 및 다른 언어 빠른 입출력 방법

- 끄적 메모

 

1. 힙 자료구조 선언: 1차원 int array

 

2. 힙 원소 삽입(push)

메커니즘

- heap size를 하나 늘림

- 마지막 노드에 삽입

- 반복: (그것의 부모 노드보다 크면 swap)

 

3. 힙 원소 삭제(pop) (=최대값 꺼내기)

메커니즘

- root 노드의 내용물 임시 저장

- root 노드와 마지막 노드를 swap(주소는 그대로, 내용물만 바꿈, 애초에 swap 함수 입력을 포인터 주소값으로 받음)

- heap size를 하나 줄임

 

<heapify(=reconstruct)>

: 자식노드가 heap 자료구조에 이미 포함되어 있다면, 부모노드가 더 큰 자식노드보다 커진 상태가 완성될 때까지 swap한다

—> 둘 중에 더 큰 것을 비교! 

 

- 첫번째 swap을 위해, parent와 child를 지정해주어야 함

: parent = 1, child = parent*2. 

이때 child 중 어느 것이 더 큰지 모르므로 비교한 후 child에 입력.

 

If child의 idx가 heap_count 이하라면(=해당 child가 heap 자료구조에 포함된 원소이고) swap

이후부터 while문으로 힙 성질 만족할 때까지 반복

- return 저장된 최대값 내용물

 

 

4. Swap 함수.

---

 

References

https://velog.io/@junhok82/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%9E%99heap

[자료구조] 힙(heap)

https://velog.io/@kon6443/Data-Structure-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-C-%ED%9E%99

[Data Structure] 자료구조 / C++ / 힙

 

다른 사람 코드

https://kyunstudio.tistory.com/241

---

- priority queue 라이브러리 사용

https://cherishvert.tistory.com/98