[자료구조] 힙(Heap), 최대 힙 (C++)

힙(heap)

힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 수행하기 위해 고안된 완전이진트리를 기본으로 한 자료구조이다.

힙은 다음과 같은 힙 속성을 만족한다.

 

• A가 B의 부모 노드이면, A의 키 값과 B의 키 값 사이에는 대소관계가 성립한다.

 

힙에는 두가지 종류가 있는데, 부모노드의 키 값이 자식노드의 키 값보다 항상 큰 힙을 '최대 힙', 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙을 '최소 힙'이라고 한다.

키 값의 대소관계는 오직 부모노드와 자신노드 사이에만 성립하며 형제 노드간에는 대소관계가 정해지지 않는다.

각 노드의 자식노드 최대 개수는 힙의 종류에 따라 다르나 일반적으로 자식노드의 개수가 최대 2개인 이진 힙을 사용한다.

 

힙에서는 가장 높은(또는 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징이 있는데, 이를 응용하여 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.

힙의 시간 복잡도는 O(nlogn)이다.

최대 힙

 

최대 힙

루트 노드가 가장 큰 값이 되고 부모노드의 값이 항상 자식 노드의 값보다 큰 것이 최대 힙이다.

오늘 포스팅에서는 최대 힙을 다룰 것이다.

최소 힙

최소 힙

루트 노드가 가장 작은 값이고, 부모노드의 값이 항상 자식노드의 값보다 작은 것이 최소 힙이다.

최대 힙의 삽입

최대 힙은 부모노드의 값이 자식노드의 값보다 항상 크게 오도록 한다.
최대 힙의 삽입 과정은 다음과 같다

1. 트리의 가장 마지막 노드 다음에 현재 삽입할 데이터를 넣는다.

2. 부모노드와 비교하면서 부모노드보다 큰 값이면 부모노드와 자리를 바꾼다.

3. 부모노드가 없거나 부모노드보다 작을 때까지 2번의 과정을 반복한다.

 

[33 28 6 51 23 ] 의 5개 짜리 배열을 힙에 삽입한다고 가정하면,

처음에 33이 들어가서 루트노드로 삽입된다. 그리고 28이 삽입되면 33의 자식노드로 들어간다. 그 후에 부모노드인 33과 비교하는 2번 과정을 거치는데, 28이 33보다 작기 때문에 변경되지 않는다. 그 후 6번 노드도 28과 같은 방식으로 33의 자식 노드로 삽입되고, 51이 삽입되면 33의 오른쪽 자식노드로 삽입된 후, 부모노드인 28과 비교하여 더 큰 값이기 때문에 28과 Swap한다. 그리고 또 다시 부모노드인 33과 비교하여 더 큰 값이므로 51과 33을 Swap하여 루트 노드는 51이 된다. 그리고 23이 33의 자식 노드로 들어가고 33보다 작은 값이므로 최대 힙의 삽입 과정이 종료된다.

최대 힙의 삭제

최대 힙의 삭제 과정은 다음과 같다.

1. 삭제할 최댓값을 저장한다.
2. 가장 마지막 노드와 루트 노드를 Swap 한다.
3. 현재 노드에서 자식 노드와 비교 하여 자식 노드보다 작으면 Swap한다.
4. 제대로 된 위치를 찾을 때까지 3번 과정을 반복한다.
5. 저장해둔 최댓값을 return 하고 힙의 크기를 1 감소시킨다.

 

앞서 삽입한 5개의 최대 힙에서 삭제 과정을 예시로 들면 아래와 같다.

1. 삭제할 최댓값은 루트 노드인 51이므로 51을 저장한다.
2. 51과 마지막 노드인 23을 Swap하여 루트노드는 23이 된다.
3. 루트노드가 된 23과 자식 노드인 33과 6중 더 큰 값인 33과 비교하여 33이 더 크므로 Swap한다.
4. 23과 28을 비교하여 28이 더 크므로 Swap 한다.
5. 23이 제 위치를 찾았기 때문에 3번 과정의 반복을 종료한다.
6. 최댓값인 51을 return하고 힙의 크기를 1 감소시킨다.

소스 코드 예제

삽입

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

삭제

    int heap_pop() {
    if (heap_count <= 0) return 0;
    // 최댓값인 첫번째 원소 저장
    int result = heap[1];

    //첫번째 원소를 가장 마지막 원소와 바꾸고 heap의 크기 1 감소
    swap(heap[1], heap[heap_count]);
    heap_count--;

    // 첫번째 원소로 올라온 원소를 알맞은 위치로 보냄
    int parent = 1;
    int child = parent * 2;
    if (child + 1 <= heap_count) { // 형제 노드 크기 비교
        child = heap[child] > heap[child + 1] ? child : child + 1;
    }
    while (child <= heap_count && heap[child] > heap[parent]) {
        swap(heap[parent], heap[child]);
        parent = child;
        child *= 2;
        if (child + 1 <= heap_count) {
            child = heap[child] > heap[child + 1] ? child : child + 1;
        }
    }
    return result;
}