[자료구조] 힙(heap)

힙(heap)은 우선 순위 큐를 위하여 만들어진 자료구조이다.

여기서 우선순위 큐란 무엇일까?

보통 큐(queue)는 FIFO(선입선출) 구조로써 먼저 들어온 데이터가 먼저 나가는 형태의 자료구조이다.

우선순위 큐는 추가적으로 데이터에 우선순위를 부여하여 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.

우선순위 큐는 배열, 연결리스트, 힙으로 구현 가능한데 이 중 힙으로 구현하는 것이 가장 효율적이다.

 

힙(heap)이란?

- 완전 이진 트리의 일종이며 우선순위 큐를 위해 만들어진 자료구조이다.

- 데이터에서 최솟값(최댓값)을 빠르게 찾을 수 있다.

- 힙은 최소 힙(min heap)과 최대 힙(max heap) 두 종류이다.

최소 힙(min heap)과 최대 힙(max heap)

- 최소 힙(min heap)은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리, 최상위(루트) 노드는 전체 노드 중 최솟값을 가진다.

- 최대 힙(max heap)은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리, 최상위(루트) 노드는 전체 노드 중 최댓값을 가진다.

 

힙(heap)의 삽입

1. 새로운 요소가 들어오면 새로운 노드를 힙의 마지막 노드 다음에 삽입한다.

2. 새로운 노드를 부모 노드와 비교, 교환하여 힙을 완성한다.

 

힙(heap)의 삭제

1. 루트 노드를 삭제한다.

2. 삭제된 루트 노드에 힙의 마지막 노드를 가져온다.

3. 삽입된 노드를 자식 노드와 비교, 교환하여 힙을 완성한다.

 

힙(heap)의 삽입과 삭제

 

사진 출처

https://www.geeksforgeeks.org/heap-data-structure/

https://algs4.cs.princeton.edu/24pq/