힙( heap)

여러개의 값들 중에서 최소값 혹은 최대값을 빠르게 알아내기 위한 자료구조이다 

완전 이진 트리의 형태를 갖는다.

 

시간복잡도 : 최선, 평균, 최악 모두 O(n logn)

 

종류

---

최소 힙

부모 노드의 값이 자식 노드의 값보다 낮거나 같은 완전 이진 트리이다

 

최대 힙

부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리이다

 

구현

---

배열로 자료구조 힙을 만든다

예시) 최소 힙

access :

왼쪽 자식: 자신의 인덱스*2

오른쪽 자식: 자신의 인덱스*2 + 1

부모: 자신의 인덱스/2

push :

1. 배열의 맨 끝에 값을 넣는다

2-1. 부모 노드보다 값이 작다면 부모와 값을 바꿈

2-2. 배열의 맨 앞까지 왔거나, 자신보다 작은 부모를 만나기 전까지 2번 반복

pop :

0. 만약 배열이 비어있다면 -1를 호출한다

1. 가장 작은 노드인 루트 노드를 제외시키고, 배열의 맨 끝에 있는 값을 대신 넣는다

2-1. 자식 노드중 가장 작은 노드와 비교해서 크다면 자리를 바꾼다.

2-2. 더 이상 자식이 없거나, 자신보다 큰 자식 노드를 만나기 전까지 2번 반복

3. 제외시킨 루트 노드를 호출한다 

 

코드

---

#include <iostream>

using namespace std;

typedef struct heap{
    int arr[100001];
    int size;
} heap;

void initHeap(heap *hp){
    hp->size = 0;
}

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

void insert(heap *hp, int data){
    int here = ++hp->size;

    while(here!=1 && data < hp->arr[here/2]){
        hp->arr[here] = hp->arr[here/2];
        here /= 2;
    }
    hp->arr[here] = data;
}

int deleteData(heap *hp) {
    if (hp->size == 0) return 0;
    int ret = hp->arr[1];
    hp->arr[1]=hp->arr[hp->size--];
    int parent = 1;
    int child;
 
    while (1) {
        child = parent * 2;
        if (child + 1 <= hp->size && hp->arr[child]>hp->arr[child + 1])
            child++;
 
        if (child>hp->size||hp->arr[child] > hp->arr[parent]) break;
         
        swap(&hp->arr[parent], &hp->arr[child]);
        parent = child;
    }
     
    return ret;
     
}

int main(){
    int N;
    heap *hp = new heap;

    cin >> N;

    initHeap(hp);

    for(int i = 0; i < N; i++){
        int x;
        scanf("%d", &x);

        if(x == 0){		// 0입력시 pop
            printf("%d\n", deleteData(hp));
        }else{	// 0이 아닌 정수 입력시 push
            insert(hp, x);
        }
    }

    return 0;
}