🧠 Heap 구조란? 쉽게 이해하는 자료구조의 핵심!

자료구조를 공부한다면 반드시 알아야 할 Heap 구조!
오늘은 Heap의 개념부터 종류, 구현, 활용까지 완벽 정리해드릴게요.
📚 코딩 테스트, 개발 실무, 운영체제 개념까지 두루두루 중요한 Heap! 함께 마스터해요.

 

 

---

📌 Heap이란 무엇인가요?

Heap은 완전 이진 트리(Complete Binary Tree) 형태로 구성된 우선순위 기반의 자료구조입니다.

• 완전 이진 트리란?
  트리의 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 채워진 형태.
• Heap의 핵심 특징
  • 항상 **루트 노드가 최대값(또는 최소값)**을 유지
  • 노드 간 우선순위에 따라 자동 정렬됨
  • 일반적으로 배열로 구현됨

---

🧭 Heap의 종류

종류 설명 루트 노드 값

🔺 Max Heap	부모 노드 ≥ 자식 노드	가장 큰 값
🔻 Min Heap	부모 노드 ≤ 자식 노드	가장 작은 값

✅ **우선순위 큐(Priority Queue)**를 구현할 때 주로 사용돼요!

---

🛠️ Heap 구조 시각화 (개념도 설명)

🧱 Max Heap 예시 (배열: [50, 30, 20, 15, 10, 8, 16])

            50
          /    \
        30      20
       /  \    /  \
     15   10  8   16

• 부모가 자식보다 크다는 규칙을 만족
• 삽입/삭제 시에도 이 규칙을 유지해야 함

---

💡 Heap의 주요 연산

연산 설명 시간 복잡도

삽입 (Insert)	새로운 값을 넣고 재정렬	O(log n)
삭제 (Delete)	루트 노드 제거 후 재정렬	O(log n)
조회 (Peek)	루트 노드 확인	O(1)

⚙️ 삽입 시에는 아래에서 위로 "heapify up",
삭제 시에는 위에서 아래로 "heapify down"이 발생해요.

---

💻 코드 예시 (Python)

import heapq

# Min Heap 기본 예제
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 8)

print(heapq.heappop(min_heap))  # 3 (최솟값 반환)

🔁 Python의 heapq는 기본적으로 Min Heap 방식이에요.
Max Heap이 필요하다면 음수 값을 넣는 방식으로 구현해요!

---

🔍 Heap은 어디에 쓰이나요?

• ✅ 우선순위 큐(Priority Queue) 구현
• ✅ 다익스트라 알고리즘 (최단 경로 탐색)
• ✅ 힙 정렬(Heap Sort) — O(n log n)
• ✅ 운영체제의 스케줄러 (우선순위 기반 태스크 실행)
• ✅ 메모리 관리 (힙 메모리 영역과 개념적 차이 있음!)

---

🤔 Stack과 Heap의 차이?

구분 Stack Heap

메모리 구조	후입선출 (LIFO)	동적 할당 영역
할당 방식	컴파일 타임	런타임
관리 주체	시스템	개발자 or GC
사용 목적	함수 호출, 지역 변수	객체 저장, 동적 자료구조

여기서 말하는 Heap 자료구조와 메모리의 Heap은 동일한 이름이지만 용도가 다릅니다!
혼동 주의! ⚠️

---

🎯 요약

• Heap은 우선순위가 중요한 자료를 다룰 때 유용한 완전 이진 트리입니다.
• Min Heap, Max Heap으로 나뉘며, 삽입/삭제 모두 O(log n)
• Python, C++, Java 등에서 내장 라이브러리로 지원됨
• 다양한 알고리즘의 핵심 도구