📚 Reference

📜 Chapter

Binary Tree

‣

‣

‣

Dijkstra algorithm

‣

Heap

• Heap
• 힙
• 최댓값 또는 최솟값을 찾아내는 연산을 쉽게 하기 위해 고안된 구조로, 각 노드의 키 값이 자식의 키 값보다 작지 않거나(최대 힙) 그 자식의 키 값보다 크지 않은(최소힙) 완전 이진 트리이다.
• 우선순위가 가장 높은 값을 Root 노드로 만든다.
• 마지막에 값을 붙이면서 가장 우선순위가 높은 최대 값을 맨 꼭대기로 올린다.
• 우선순위 큐(Priority Queue) 이다.
• 활용: 정렬(Heap sort)
• stable
• 힙(Heap)은 완전 이진 트리(Complete Binary Tree)를 기반으로 하며, 보통 이진 힙(Binary Heap) 구조를 사용한다.
• 힙은 우선순위 큐(Priority Queue) 등의 데이터 구조를 구현하는 데 많이 활용된다.
• Heap(힙)은 완전 이진 트리 기반의 우선순위 큐 자료구조로, Min Heap과 Max Heap이 있다.
  • Min Heap: 부모 노드가 자식보다 작음 (최소값이 루트)
  • Max Heap: 부모 노드가 자식보다 큼 (최대값이 루트)

Heap - 시간 복잡도