Heap 이란?

Heap 이란?

우선순위큐(Priority Queue)를 구현하기 위한 자료구조이다.

 

우선순위큐

- 특정 우선순위를 정해두고 그 기준으로 만든 큐를 의미한다.
(기존의 큐는 FIFO이지만, 우선순위를 가장 큰 값 또는 가장 작은 값으로 정해놓는 큐를 의미한다.)

우선순위큐는 이진트리(Binary Tree) 형태의 자료구조이다.

그림과 같이 이진트리형태는 왼쪽 위로 차있는 형태이다.

 

이진트리

Max Heap의 Binary Tree

- 부모 노드가 자식 노드보다 작은 값을 가지는 최소 힙(Min Heep)과, 부모 노드가 자식 노드보다 큰 값을 가지는 최대 힙(Max Heap)으로 나눌 수 있다.
- 각 노드는 최대 두 개의 자식 노드를 갖는다.
- 새로운 원소는 일반적으로 힙의 맨 끝에 추가되고, 이후 힙의 성질을 유지하기 위해 적절한 위치로 재배치 된다.
- 최소힙에서는 최소값을, 최대힙에서는 최대값을 추출하는 동작이 빠르다.
- Heap에 쓰이는 이진트리는 느슨한 정렬상태를 유지한다.

 

Heap의 배열 Index 계산법

Heap의 삽입과 삭제