Heap, Priority Queue (우선순위 큐)

1. Heap

• Heap : 무더기, 더미를 의미함
• 컴퓨터 기억 장소에서 일부분이 프로그램에 할당 되었다가 회수되는 작용이 되풀이되는 영역
• Heap의 기억장소는 대부분 Pointer 변수를 통해 동적으로 할당받고 돌려줌
• 아래 메모리 구조 그림을 참고

Heap은 사용자가 동적 할당 하는 공간, (출처: https://lxxyeon.tistory.com/70)

---

 2. 자료구조 Heap

• 자료구조로 쓰이는 Heap: 데이터에서 최댓값, 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리
• 완전 이진 트리: 자식노드가 왼쪽부터 꽉 채워지는 트리
• 부모 노드 index = 자식 노드 index // 2
• Left 자식 노드 index = 부모 노드 index * 2
• Right 자식 노드 index = (부모 노드 index * 2) + 1
• 배열로 구현할 때 index 1부터 시작하는게 편함

---

3. Heap 사용 이유

• 배열에서 max, min 찾을 때: O(n) 소요
• Heap에서 max, min 찾을 때: O(logN) 소요
  
  • 파이썬 기본 내장 함수 max, min의 시간 복잡도는 O(n)임
• 우선순위 큐 등과 같이 max, min을 빠르게 찾아야 하는 알고리즘에 활용하기 좋다!

---

4. Heap의 동작

• 데이터 삽입: Heap은 완전 이진 트리이기 때문에 삽입할 노드가 기본적으로 왼쪽 최하단부터 채워짐