[자료구조] 힙 (Heap)

힙 (Heap) 란?

• 특수한 트리 기반 데이터 구조
• 힙은 우선순위 큐를 구현하기 위한 완전 이진 트리 형태의 자료구조
• 최대 힙 (Max Heap)과 최소 힙(Min Heap) 총 2가지가 존재한다.

최대 힙 (Max Heap)

• 부모의 노드가 항상 자식의 노드보다 큰 구조

1. 한쪽 노드만 계속 진행되서는 안된다.
2. 왼쪽과 오른쪽 하위 트리에도 같은 작업을 수행해야한다.
3. 부모의 값보다 자식의 값이 크면 안된다.

최소 힙(Min Heap)

• 부모의 노드가 항상 자식의 노드보다 작은 구조

1. 한쪽 노드만 계속 진행되서는 안된다.
2. 왼쪽과 오른쪽 하위 트리에도 같은 작업을 수행해야한다.
3. 부모의 값보다 자식의 값이 작으면 안된다.

장단점

장점

• 최대값 또는 최소값을 빠르게 찾고 삽입할 수 있음.
• 우선순위 큐나 작업 스케줄링에서 활용하기 좋음.

단점

• 중간 요소에 접근하기 어렵고, 삽입/삭제 시 균형을 맞추기 위한 추가 작업 필요.
• 메모리 사용이 비효율적일 수 있음.

구현

#include <iostream>
#include <vector>
#include <algorithm>

class MaxHeap {
private:
	std::vector<int> heap;

	// 부모-자식 관계를 유지하며 힙을 재정렬 (heapify-down)
	void heapifyDown(int index) {
		int left = 2 * index + 1;
		int right = 2 * index + 2;
		int largest = index;

		// 왼쪽 자식이 더 크면 largest를 왼쪽 자식 인덱스로 갱신
		if (left < heap.size() && heap[left] > heap[largest]) {
			largest = left;
		}

		// 오른쪽 자식이 더 크면 largest를 오른쪽 자식 인덱스로 갱신
		if (right < heap.size() && heap[right] > heap[largest]) {
			largest = right;
		}

		// largest가 변경되었으면 swap하고, 재귀적으로 heapify
		if (largest != index) {
			std::swap(heap[index], heap[largest]);
			heapifyDown(largest);
		}
	}

	// 힙을 위로 재정렬 (heapify-up)
	void heapifyUp(int index) {
		while (index > 0 && heap[(index - 1) / 2] < heap[index]) {
			std::swap(heap[index], heap[(index - 1) / 2]);
			index = (index - 1) / 2;
		}
	}

public:
	// 삽입 연산
	void insert(int value) {
		heap.push_back(value);   // 새로운 값 삽입
		heapifyUp(heap.size() - 1);  // 새로운 값이 힙 속성을 만족하도록 위로 올리기
	}

	// 루트 삭제 연산 (최대값 삭제)
	void removeMax() {
		if (heap.empty()) return;

		// 루트와 마지막 값을 교환
		heap[0] = heap.back();
		heap.pop_back();

		// 루트부터 아래로 heapify-down
		heapifyDown(0);
	}

	// 루트 값을 반환 (최대값)
	int getMax() {
		if (!heap.empty()) {
			return heap[0];
		}
		throw std::out_of_range("Heap is empty");
	}

	// 힙을 출력
	void printHeap() {
		for (int val : heap) {
			std::cout << val << " ";
		}
		std::cout << std::endl;
	}

	bool isEmpty() {
		return heap.empty();
	}
};

int main() {
	MaxHeap maxHeap;

	// 삽입
	maxHeap.insert(10);
	maxHeap.insert(20);
	maxHeap.insert(15);
	maxHeap.insert(30);
	maxHeap.insert(40);

	std::cout << "Max Heap: ";
	maxHeap.printHeap(); // 40 30 15 10 20

	// 최대값 얻기
	std::cout << "Max Value: " << maxHeap.getMax() << std::endl; // 40

	// 최대값 제거
	maxHeap.removeMax();
	std::cout << "Max Heap after removing max: ";
	maxHeap.printHeap(); // 30 20 15 10

	return 0;
}

 

참고자료

https://www.geeksforgeeks.org/introduction-to-heap/