[자료구조] 힙 (Heap)

강승구·2023년 2월 2일

우선순위 큐 (Priority Queue)

컴퓨터 내부에서 동일한 자원을 요구하는 여러 프로그램이 있는 경우에는 우선순위를 부여해서 관리한다. 대부분의 운영체제에는 작업들의 우선순위를 부여할 수 있는 기능이 있는데 예를 들면 CPU나 다른 자원을 무겁게 사용하면서 며칠동안 수행해야할 작업이 있다면 다른 작업들의 동작을 방해할 수 있으므로 우선순위를 낮추어놓고 작업할 수 있다.
이런방식을 통해 다른 작업이 자원을 필요로 할 때 양보했다가 한가한 시간에 주로 해당 작업을 수행할 수 있다.
우선순위 큐는 위와 같은 상황에서 우선순위를 다루는 목적으로 사용되는 자료구조이다.

힙 (Heap)

우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하다.
이 중에서 힙으로 구현하는 것이 가장 효율적이다.

힙은 완전 이진 트리 구조를 사용해 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어졌다. 그리고 이진트리에서는 중복된 값을 허용하지 않지만 힙에서는 중복된 값을 허용한다.

힙은 아래의 조건들을 만족해야한다.

완전 이진 트리의 구조를 가져야한다.

모든 노드는 값을 갖는다.

최대힙의 경우 부모 노드는 자식 노드 값보다 크거나 같아야하고 최소힙의 경우 부모 노드는 자식노드 값보다 작거나 같아야한다.

최대힙과 최소힙

최대힙은 부모노드가 자식노드보다 큰 구조를 가지고 최소힙은 부모노드가 자식노드보다 작은 구조를 갖는다.

삽입

힙은 완전이진트리를 활용한 자료구조이기 때문에 삽입을 할 때 현재 노드 중 가장 마지막 노드에 우선 연결이 된다.

새로운 데이터(8)을 힙에 삽입
자식 노드와 부모 노드의 크기를 비교하여 최대힙의 조건에 맞도록 swap

삭제

힙에서 Data 의 삭제는 항상 루트 노드를 삭제를 한다.
최대힙의 경우엔 최대값이 삭제가 되는 것 이고 최소힙의 경우엔 최소값이 삭제가 된다.

루트 노드 삭제
가장 마지막 자식 노드를 루트로 옮긴다.
루트노드로 이동을 한 후 최대힙 조건을 갖춰야 하므로 계속해서 자식 노드와 비교를 해가면서 필요시 Swap을 한다. 이 과정을 Heapify라고 한다.

힙의 장단점

장점

데이터를 큐나 배열에 데이터를 넣고 최대값이나 최소값을 찾으려면 최악의 경우 일일히 하나씩 데이터를 검사해야 하기때문에 $O(n)$ 의 시간복잡도를 갖는다. 하지만, 힙을 사용하면 $O(logn)$ 으로 시간복잡도가 현격하게 줄어든다.

단점

Heap은 느슨한 정렬상태(반정렬상태)이다. 완벽히 정렬되지 않고 가장 큰 수나 가장 작은 수만을 찾기 위함이다.
다른 자료구조(배열, 스택 등)을 힙으로 바꾸는 과정(Heapify)에서 시간이 소요된다.

힙을 사용하는 경우

배열에 데이터를 넣고 최대값이나 최소값을 찾으려면 최악의 경우 일일히 하나씩 데이터를 검사해야 하기때문에 $O(n)$ 의 시간복잡도를 갖는다.
하지만 힙을 사용하면 $O(logn)$ 으로 시간복잡도가 현격하게 줄어들기 때문에 최대나 최소값을 찾아야하는 경우에 힙을 사용한다.

구현

직접 구현

// 삽입
void insert(vector<int>& maxHeap, int curNode) { // data가 삽입 된 Node로 curNode 입력
	if (curNode == 1) {
		return;
	}
	else { // if this is not root node ( compare with parent node )
		while (curNode / 2) {
			int parentNode = curNode / 2;

			if (maxHeap[parentNode] < maxHeap[curNode]) {
				int temp = maxHeap[parentNode];
				maxHeap[parentNode] = maxHeap[curNode];
				maxHeap[curNode] = temp;
			}

			curNode /= 2;
		}
	}
}

// 삭제
void remove(vector<int>& maxHeap, int heapSize) {
	maxHeap[1] = maxHeap[heapSize]; // 마지막 Node 를 Root Node 로
	maxHeap[heapSize] = 0; // 위에서 마지막 Node 를 옮겼으므로 이를 0으로 초기화
	heapSize--; // 마지막 노드를 삭제 하였으므로 Size--

	int curNode = 1; // 삭제 후 Node 재정비를 시작하는 Node 번호
	int changeNode = 0; // 
	int leftChild, rightChild;

	while (2 * curNode <= heapSize) {
		leftChild = maxHeap[2 * curNode];
		rightChild = 2 * curNode + 1 <= heapSize ? maxHeap[2 * curNode + 1] : 0;

		if (rightChild) {
			if (leftChild > maxHeap[curNode] && rightChild > maxHeap[curNode])
				changeNode = leftChild > rightChild ? 2 * curNode : 2 * curNode + 1;
			else if (leftChild > maxHeap[curNode])
				changeNode = 2 * curNode;
			else if (rightChild > maxHeap[curNode])
				changeNode = 2 * curNode + 1;
		}
		else // leftChild
			if (leftChild > maxHeap[curNode])
				changeNode = 2 * curNode;

		if (changeNode) {
			int temp = maxHeap[curNode];
			maxHeap[curNode] = maxHeap[changeNode];
			maxHeap[changeNode] = temp;

			curNode = changeNode;
			changeNode = 0;
		}
		else break;
	}
}

STL

#include<iostream>
#include<queue>
#include <algorithm>

using namespace std;

int main(){
    //최대힙
    priority_queue<int> pq_max;
    //최소힙
    priority_queue<int, vector<int>, greater<int>> pq_min;
    
    //원소 삽입
    pq_max.push(1);
    pq_max.push(2);
    pq_max.push(3);
    
    pq_min.push(1);
    pq_min.push(2);
    pq_min.push(3);
    
    //크기 출력
    cout << pq_max.size();
    cout << pq_min.size();
    
    //원소 삭제
    pq_max.pop();
    pq_min.pop();
    
    //비어있는지 확인
    cout << pq_max.empty();
    cout << pq_min.empty();
    
    //swap
    priority_queue<int> pq;
    pq.push(1);
    pq.push(1);
    
    pq_max.swap(pq);
    
    //원소 출력
    for(int i=0; i<pq_max.size(); i++){
        cout << pq_max.top();
        pq_max.pop();
    }
    
    cout << "\n";
    
    
    for(int i=0; i<pq_min.size(); i++){
        cout << pq_min.top();
        pq_min.pop();
    }
    
    cout << "\n";
    
    for(int i=0; i<pq.size(); i++){
        cout << pq.top();
        pq.pop();
    }
}