[C++] 힙 개념과 구현 방법

Heap 이란?

자료구조 중 하나로, 동적으로 데이터를 관리하는 데 사용되며 '최댓값' 혹은 '최솟값'을 빠르게 찾아낼 수 있는 자료구조이다. 형태는 이진 트리의 형태를 가지며 주로 우선순위 큐, 힙 정렬 등의 알고리즘에서 사용된다. 여기서 이진 트리란 하나의 부모 노드는 최대 2개의 자식 노드를 가진 형태를 말한다.

이진 트리

 

Heap 구현 방법 ( 최소힙 )

• 이진 트리의 가장 마지막 노드 다음에 값을 삽입한다.
• 부모 노드와 값을 비교하여 부모 노드보다 작은 값이라면 부모 노드와 값을 Swap 해준다.
• 스왑을 해줬다면 해당 노드에서도 부모 노드가 있는지 체크해서 다시 Swap을 해준다.
• 이와 같은 작업을 계속해서 반복해준다.

---

Heap 구현 코드

#include<iostream>
#include<stdexcept>

template <typename T>
class Heap {
private:
	T* heapArray;
	size_t capacity;
	size_t size;

	// 부모 노드 인덱스 위치
	size_t parent(size_t i) const {
		return (i - 1) / 2;
	}

	// 왼쪽 자식 노드 인덱스 위치
	size_t leftChild(size_t i) const {
		return (i * 2) + 1;
	}

	// 오른쪽 자식 노드 인덱스 위치
	size_t rightChild(size_t i) const {
		return (i * 2) + 2;
	}

	// 노드 삭제 시 힙 구조를 유지하기 위한 메서드
	void heapifyDown(size_t i) {
		size_t smallest = i;
		size_t left = leftChild(i);
		size_t right = rightChild(i);

		if (left < size && heapArray[left] < heapArray[smallest]) {
			smallest = left;
		}

		if (right < size && heapArray[right] < heapArray[smallest]) {
			smallest = right;
		}

		if (smallest != i) {
			std::swap(heapArray[i], heapArray[smallest]);
			heapifyDown(smallest);
		}
	}

	// 노드 삽입 시 힙 구조를 유지하기 위한 메서드
	void heapifyUp(size_t i) {
		while (i > 0 && heapArray[parent(i)] > heapArray[i]) {
			std::swap(heapArray[i], heapArray[parent(i)]);
			i = parent(i);
		}
	}

public:
	// 생성자
	Heap(size_t capacity) : capacity(capacity), size(0) {
		heapArray = new T[capacity];
	}

	// 소멸자
	~Heap() {
		delete[] heapArray;
	}

	// 힙에 노드 삽입
	void push(T element) {
		if (size == capacity) {
			throw std::overflow_error("Heap is full!!");
		}
		heapArray[size] = element;
		size++;
		heapifyUp(size - 1);
	}

	// 최소값 반환 후 삭제
	T pop() {
		if (size == 0) {
			throw std::underflow_error("Heap is empty!!");
		}
		T min = heapArray[0];
		heapArray[0] = heapArray[size - 1];
		size--;
		heapifyDown(0);

		return min;
	}

	// 현재 힙의 크기 반환
	size_t getSize() const {
		return size;
	}

	// 힙이 비어있는지 여부 반환
	bool empty() const {
		return size == 0;
	}

	// 연산자 오버로딩: 배열에 직접 접근하는 연산자
	T& operator[](size_t index) {
		if (index >= size) {
			throw std::out_of_range("Index out of range");
		}
		return heapArray[index];
	}

};

int main() {
	Heap<int> minHeap(10);

	try {
		minHeap.push(3);
		minHeap.push(1);
		minHeap.push(4);
		minHeap.push(1);
		minHeap.push(5);
		minHeap.push(9);
		minHeap.push(2);
	}
	catch (const std::overflow_error& e) {
		std::cerr << "exception : " << e.what() << std::endl;
	}
	catch (const std::underflow_error& e) {
		std::cerr << "exception : " << e.what() << std::endl;
	}

	// 힙의 배열에 있는 값들을 출력
	std::cout << "Values in minHeap: ";
	for (size_t i = 0; i < minHeap.getSize(); ++i) {
		std::cout << minHeap[i] << " ";
	}
	std::cout << std::endl;

	return 0;
}