[DATA STRUCTURE] 11. 힙 (Heap)

힙(Heap)은 특정한 규칙에 따라 정렬된 완전 이진 트리(Complete Binary Tree)의 형태를 가지는 자료 구조다.

힙은 주로 최댓값이나 최솟값을 빠르게 찾기 위한 목적으로 사용되며,

부모 노드의 키 값은 항상 자식 노드의 키 값보다 크거나 같은 "최대 힙 속성"과

부모 노드의 키 값은 항상 자식 노드의 키 값보다 작거나 같은 "최소 힙 속성" 즉 2가지 속성을 갖고 있다.

 

#pragma once
#include <algorithm>
#include <vector>

class MaxHeap {
private:

	std::vector<int> vec;

	int parent(int i) {

		return i / 2;
	}

	int left(int i) {

		return 2 * i;
	}

	int right(int i) {

		return 2 * i + 1;
	}

	void heapify_up(int i) {

		if (i > 1 && vec[i] > vec[parent(i)]) {

			std::swap(vec[i], vec[parent(i)]);
			heapify_up(parent(i));
		}
	}

	void heapify_down(int i) {

		int largest = i;

		if (left(i) < vec.size() && vec[left(i)] > vec[largest]) {
			
			largest = left(i);
		}

		if (right(i) < vec.size() && vec[right(i)] > vec[largest]) {

			largest = right(i);
		}

		if (largest != i) {

			std::swap(vec[i], vec[largest]);
			heapify_down(largest);
		}
	}

public:

	MaxHeap() : vec(1) {}

	void push(int value) {

		vec.push_back(value);
		heapify_up(vec.size() - 1);
	}

	void pop() {

		vec[1] = vec.back();
		vec.pop_back();
		heapify_down(1);
	}

	int top() const {

		return vec[1];
	}

	int size() {

		return vec.size() - 1;
	}

	bool empty() {

		return vec.size() == 1;
	}

	void print() {

		for (auto n : vec) {

			std::cout << n << ", ";
		}

		std::cout << std::endl;
	}
};

 

 

특징

 

1. 힙 속성 : 최대 힙은 각 노드의 값이 자식 노드들의 값보다 크거나 같고,

최소 합은 각 노드의 값이 자식 노드들의 값보다 작거나 같은 특성이 있다.

2. 노드 간 관계 : 부모-자식 사이의 크기 관계만 있고, 왼쪽 자식-오른쪽 자식 사이의 크기 관계는 없음

3. 힙의 응용 분야 : 힙 정렬, 우선순위 큐, 다익스트라 알고리즘(Dijkstra's algorithm) 등에서 활용

4. 완전 이진 트리 구조 : 완전 이진 트리의 형태를 가지고 있으므로 배열을 사용하여 간단하게 구현할 수 있게 해주며,

메모리를 효율적으로 사용할 수 있다.

5. 빠른 삽입과 삭제 연산 : 새로운 원소의 추가나 최댓값(혹은 최솟값)의 삭제는 힙의 높이에 비례하여

시간이 소요되므로 O(log n)의 시간 복잡도를 가진다.

 

 

장점

 

1. 빠른 우선순위 처리 : 가장 작은 값에 빠르게 접근할 수 있어 다양한 문제에서 유용하게 사용된다.

2. 효율적인 삽입 및 삭제 연산 : 힙은 삽입과 삭제 연산이 빠르며, 특히 삽입 시에는 배열의 마지막에 추가하는 방식으로

구현할 수 있어서 효율적이다.

3. 힙 정렬 : 힙은 힙 정렬(Heap Sort) 알고리즘에서 사용되며 빠른 정렬을 제공한다.

 

 

단점

 

1. 탐색 속도가 느림 : 힙은 최댓값 또는 최솟값에 빠르게 접근할 수 있지만, 특정 값을 찾는 데는 느린 성능을 보인다.

이는 이진 탐색 트리(BST)와는 다른 특성을 가진다.

2. 정렬된 데이터 삽입 시 성능 하락 : 이미 정렬된 데이터를 힙에 삽입할 때는 성능 하락이 동반될 수 있다.

이는 삽입 시에 힙 속성을 유지하기 위해 불필요한 스왑 작업이 발생할 수 있기 때문이다.

 

 

힙과 이진 탐색 트리의 비교

 

조건	힙(Heap)	이진 탐색 트리(BST)
트리의 형태	완전 이진 트리	이진 트리
원소 중복 여부	중복 가능	중복되지 않음
원소의 정렬 여부	정렬되지 않음	정렬됨 (중위 탐색)
빠른 원소 탐색	미지원 (순차 탐색, O(n))	지원 (이진 탐색, O(log n))
원소의 삽입 또는 삭제	O(log n)	O(log n) / O(n)
최댓값 / 최솟값 참조	O(1)	O(log n) / O(n)