[자료구조] 힙(Heap)

📖힙(Heap)이란?

힙은 완전이진트리(complete binary tree) 기반의 자료구조로, 트리에서 최댓값 또는 최솟값을 빠르게 찾을 수 있다. 우선순위 큐를 구현하는 데에 많이 사용된다.

• 최대 힙(max heap) : 각 노드의 값이 자식 노드의 값보다 크거나 같은 완전이진트리
• 최소 힙(min heap) : 각 노드의 값이 자식 노드의 값보다 작거나 같은 완전이진트리

최대 힙에서는 최댓값이 루트 노드, 최소 힙에서는 최솟값이 루트 노드가 되어 빠르게 값을 찾을 수 있다.

---

📖힙의 삽입과 삭제

힙은 완전이진트리 기반의 자료구조이므로 1차원 배열에 노드를 저장하면 낭비 되는 공간 없이 데이터를 저장할 수 있다.

• 부모 노드의 index : (자식 노드의 index) / 2
• 왼쪽 자식 노드의 index : 2 * (부모 노드의 index)
• 오른쪽 자식 노드의 index : 2 * (부모 노드의 index) + 1

📁힙의 삽입

힙은 새로운 노드가 삽입되어도 최대 힙 또는 최소 힙을 유지한다.

새로 삽입된 노드는 부모 노드와 값을 비교하면서 최대 힙 또는 최소 힙이 되는 것을 확인할 때까지 부모 노드와 자리를 바꾸며 위로 올라간다.

위의 그림은 최대 힙을 나타내고 있다. 새로운 노드가 삽입되는 경우, 일단 검은색으로 색칠되어있는 곳에 노드가 삽입된다.

새로운 노드로 5가 삽입되는 경우, 왼쪽 그림과 같이 삽입 후 부모 노드인 2보다 값이 크므로 자리를 바꾼다.

새로운 노드로 21이 삽입되는 경우, 먼저 삽입 후 부모 노드인 2보다 값이 크므로 자리를 바꾼다. 자리를 바꾼 후의 부모 노드인 20보다 값이 크므로 다시 자리를 바꾼다.

C++로 구현해보면 다음과 같다.

void push_heap(int num) { //num을 최대 힙에 삽입
	int currentNode = ++heapSize; //새로운 노드를 삽입할 index
    
    /*
    새로운 노드를 삽입할 index가 1이 되거나 
    부모 노드의 값이 새로운 노드의 값보다 크거나 같을 때까지 반복
    */
    while (currentNode != 1 && heap[currentNode / 2] < num) {
    	heap[currentNode] = heap[currentNode / 2]; //부모 노드와 자리 바꾸기
        currentNode /= 2;
    }
    
    heap[currentNode] = num; //새로운 노드를 알맞은 index에 저장
}

📁힙의 삭제

힙은 루트 노드의 값이 최댓값 또는 최솟값이므로 힙에서의 삭제는 루트 노드의 삭제를 의미한다. 삽입과 마찬가지로 힙은 루트 노드가 삭제되어도 최대 힙 또는 최소 힙을 유지한다. 최대 힙의 삭제 과정은 다음과 같다.

1. 루트 노드 삭제 후, 마지막 위치의 노드를 루트 노드의 위치로 가져오고 노드 수를 1 감소시킨다.
2. 현재 노드를 루트 노드로 한다.
3. 현재 노드의 값이 두 자식 노드 중 값이 큰 노드보다도 클 경우 최대 힙으로 간주하고 종료한다.
4. 두 자식 노드 중 값이 큰 자식 노드와 현재 노드를 교환하고, 교환한 자식 노드를 현재 노드로 간주하여 3으로 가서 과정을 반복한다.

위의 그림은 최대 힙을 나타내고 있다. 삭제를 2번 진행하면 다음과 같은 과정이 나타난다.

21을 삭제하면 마지막 위치에 있던 2가 루트 노드로 온다. 자식 노드인 15, 20 중 큰 값인 20과 자리를 교환하면 최대 힙이 된다.

이후, 20을 삭제하면 마지막 위치에 있던 10이 루트 노드로 온다. 자식 노드인 15, 2 중 큰 값인 15와 자리를 교환한다. 이때, 교환 후 자식 노드인 14보다도 값이 작으므로 다시 한 번 자리를 교환하면 최대 힙이 된다.

C++로 구현해보면 다음과 같다.

void pop_heap() { //루트 노드의 삭제
	int lastE = heap[heapSize--]; //마지막 위치의 노드 값
	int currentNode = 1;
    int child = 2; //현재 노드의 자식 노드
    
    //자식 노드가 존재하지 않을 때까지 반복
    while (child <= heapSize) {
    	//두 자식 노드 중 값이 큰 노드를 child로 세팅
    	if (child < heapSize && heap[child] < heap[child + 1]) child++;
        
        //자식 노드와 값 비교, 자식 노드보다 값 크면 while문 중단
        if (lastE >= heap[child]) break; 
        
        heap[currentNode] = heap[child]; //자식 노드와 자리 교환
        currentNode = child; //교환한 자식 노드를 현재 노드로 세팅
        child *= 2;
    }
}

참고 : C++ 자료구조론 2nd edition