Heap

힙

힙이란?

• 모든 부분 트리에서 사용자 지정 조건을 만족하는 완전이진트리
  • 특정 조건 : 최댓값 / 최솟값 등등 여러가지 기준을 손수 만들 수 있음
  • 특정 조건을 우선순위라고 얘기하기도 함
• 데이터를 정렬하는 경우에 주로 사용 ( 우선순위 큐 )
  • 배열을 이용하여 구현하지만, 순서가 항상 정렬되어있는 것은 아님 ( 반정렬 )

기본 구현 방법

1. 기본적으로 구현하기 위해서는 배열을 사용
2. 첫번째 index는 0이 아닌 1을 사용
3. 자식의 노드 번호는 $\times 2$, $\times 2+1$ 의 번호를 사용한다 ( parent가 1이라면 child는 2, 3 )
   • 따라서, 부모의 번호는 자식의 $÷2$
4. 노드 삽입의 경우 아래와 같은 순서를 따름
   • 노드를 힙의 가장 뒤에 삽입
   • 이후 부모 노드와 계속 비교하며 조건에 부합한다면 두 위치를 변경
   • 변경되지 않거나 root에 도달할 때까지 반복
5. 노드 제거의 경우 아래와 같은 순서를 따름
   • root node가 반환값이 됨 ( 우선순위가 가장 높음 )
   • 힙의 가장 뒤의 노드를 root로 옮김 ( 우선순위가 항상 깨짐 )
   • 깨진 우선순위를 맞추기 위해, root부터 아래로 재정렬 진행

소스코드

// Max Heap 구현 소스코드

#define MAX_IDX 100
#define ERR -987654321 // 에러코드

int heap[MAX_IDX + 2];
int top = 0;

void insert(int x) {
    heap[++top] = x;
    int i = top;

    while (i != 1 && x > heap[i / 2]) {
        int a = heap[i / 2];
        heap[i / 2] = x, heap[i] = a;
        i /= 2;
    }
    return;
}

int pop() {
    if (top == 0) {
        return 0;
    }

    int retval = heap[1];
    heap[1] = heap[top--];

    int i = 1, tp = 2;
    while (tp < top) {
        tp += (heap[tp] < heap[tp + 1]);
        if (heap[i] >= heap[tp]) {
            break;
        }

        int a = heap[tp];
        heap[tp] = heap[i], heap[i] = a;

        i = tp, tp *= 2;
    }
    if (tp == top && heap[i] < heap[tp]) {
        int a = heap[tp];
        heap[tp] = heap[i], heap[i] = a;
    }

    return retval;
}

int main() {
    return 0;
}