26. Heap

Heap 이란?

힙은 완전 이진트리의 일종으로, 각 노드의 값이 해당 노드의 자식 노드의 값보다 우선순위가 높은 자료구조이다.

위와 같은 조건을 Max Heap, 자식 노드의 값보다 우선순위가 낮은 경우 Min Heap이라고 부른다.

 

힙은 주로 우선순위 큐를 구현하는 데 사용된다. 우선순위 큐는 데이터가 들어온 순서가 아닌 우선순위에 따라 데이터를 처리하는 자료구조이다. 예를 들어, 작업 스케쥴링에서 우선순위가 높은 작업을 먼저 처리하는 등의 용도로 사용된다.

---

트리의 배열 구현

우리는 지금까지 트리를 구현하기 위해 노드 구조체를 선언하고 포인터를 이용하여 자식을 연결하는 방식으로 트리를 구현해 왔다. 하지만 이번에는 배열을 이용하여 구현해 볼 것이다.

배열로 구현한다고 해서 무엇인가 있어보이지만 그런 거는 없다.

 

트리의 루트 노드는 배열에 1번 인덱스에 저장한다.

해당 노드의 왼쪽 자식은 자신의 인덱스 X 2, 오른쪽 자식은 자신의 인덱스 X 2 + 1에 저장한다.

예를 들어 루트의 자식은 2, 3이 되고, 3번의 자식은 6, 7 인덱스가 된다.

또한 0번 인덱스는 사용하지 않는다.

 

배열이 간단한데 사용하지 않는 이유는 무엇일까?

예를 들어 편향트리 즉 오른쪽 자식만 가진 트리가 있다고 해보자.

이 트리는 총 4개의 노드를 가지고 있다고 하면 1, 3, 7, 15에 저장이 된다.

즉, 4개의 노드를 가지고 있지만 15까지의 공간을 확보해 두어야 한다는 뜻이다.

공간적인 측면에서 비 효율적이므로 트리의 배열 표현을 잘 사용하지 않는다.

---

MAX Heap 삽입

아래는 힙에 데이터를 삽입하는 함수이다.

void push(int data){
    int i = heap_size++;
    
    while(i > 1 && data > heap[i/2]){
        heap[i] = heap[i/2];
        i = i/2;
    }
    heap[i] = data;
}

삽입하려는 곳이 루트라면 바로 삽입한다.

만약 루트가 아니라면 자신의 부모노드와 비교하여 자신이 더 작다면 현재 자리에 삽입한다.

부모노드와 비교하여 자신이 더 크다면 부모노드를 아래로 내리고 자신이 부모노드 자리로 올라간 뒤 바뀐 자리의 부모노드와 또 비교하는 과정을 반복하면서 자신의 자리를 찾아 삽입하게 된다.

---

MAX Heap 삭제

아래는 힙에서 데이터를 꺼내는 함수이다.

int pop(){
    int parent, child, temp, result;
    
    result = heap[1];
    temp = heap[heap_size--];
    parent = 1;
    child = 2;
    
    while(child <= heap_size){
        // 왼쪽 자식노드와 오른쪽 자식 노드 중 더 큰 자식을 선택
        if(child < heap_size && heap[child+1] > heap[child]) child++;
        // 마지막 노드가 자식 노드보다 크다면 종료
        if(temp >= heap[child]) break;
        // 부모와 자식 노드 교환
        heap[parent] = heap[child];
        // 한 레벨 아래로 이동
        parent = child;
        child *= 2;
    }
    heap[parent] = temp;
    return result;
}

삭제 한 뒤 마지막 노드의 적절한 위치를 찾아서 해당 자리에 삽입하는 코드이다.

여기서 삭제되는 노드는 힙 트리에서 루트 노드에 있는 노드가 삭제된다.