[Data Structure] Heap(힙) 자료구조 | 우선순위 큐(Priority Queue) | Heapify

Heap

Data Structure 세 번째 스터디 : Heap

Heap이란?

• 완전 이진 트리(complete Binary Tree)의 일종, 우선순위 큐(데이터가 우선순위를 가지고 있으며, 우선순위가 높을수록 먼저 빠져나가는 큐)를 위해서 만들어진 자료 구조
• 우선순위 큐는 Array, Linked List, Heap으로 구현이 가능한데, 이중 힙(Heap)으로 구현하는 것이 가장 효율적

자료구조삭제되는 요소

스택(Stack)	가장 최근에 들어온 데이터(LIFO)
큐(Queue)	가장 먼저 들어온 데이터(FIFO)
우선순위큐(Priority Queue)	가장 우선순위가 높은 데이터

우선순위 큐의 이용 사례

• 시뮬레이션 시스템
• 네트워크 트래픽 제어
• 운영 체제에서 작업 스케쥴링
• 수치 해석적인 계산

Heap의 기본

• 완전 이진 트리이며, 중복된 값을 허용
• 삽입/삭제 시간복잡도: O(logN)
• 최대값 찾기 시간복잡도: O(1)
• 일종의 반정렬 상태 (느슨한 정렬)
• 최대힙(Max Heap): 각 노드의 값이 자식 노드의 값보다 항상 크거나 같음
• 최소힙(Min Heap): 각 노드의 값이 자식 노드의 값보다 항상 작거나 같음
• 배열을 이용하여 구현 시
  • 인덱스를 통해 Random Access가 가능
  • 인덱스는 1부터 시작
  • 왼쪽 자식 Index: (부모 Index) × 2
  • 오른쪽 자식 Index: (부모 Index) × 2 + 1
  • 부모 Index: (자식 Index) ÷ 2

Heap 삽입 (아래에서 삽입)

1. 새로운 노드 발생
2. 새로운 노드를 힙의 마지막 노드에 이어서 삽입
3. 새로운 노드를 부모 노드들과 교환하며 힙의 성질 만족하기

Heap 삭제 (위에서 삭제)

1. 최대 힙에서 최대값은 루트! 따라서 루트노드 삭제
2. 빈 루트 자리에 힙의 마지막 노드 가져오기
3. 값을 다시 내려보내며 힙을 재구성 (자식 노드 중 더 큰 값과 교환)

Heapify ?

• 2 개의 서브 트리가 최대(최소) 힙 일 때, 루트를 포함하는 전체가 Heap이 되도록 위치를 조정하는 과정
• 루트에서 작은 값이 흘러내려가는 방식으로 처리
  1. 루트가 자식보다 작은가?
  2. 루트가 두 개의 자식 노드보다 작으면, 둘 중 큰 노드를 루트와 교체
  3. 교체할 노드가 없을 때까지 1번과 2번을 반복

참고문헌

• https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Data%20Structure/%5BData%20Structure%5D%20Heap.md
• https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html