[그래프/트리] 힙[Heap]

우선순위 큐란?

 

우선순위 개념을 큐에 도입한 자료구조이다.

데이터들은 우선순위를 가지고 있고, 순위가 높은 순부터 나간다.

 

스택[FILO]과 큐[FIFO]와는 다르다

 

우선순위 큐는 힙으로 구현이 가능하다.

 

 

 

힙이란?

힙은 두 가지로 설명할 수 있다.

 

1) 최대 힙

'부모 노드의 키 값 >= 자식 노드의 키 값'인 완전 이진 트리

 

 

 

2) 최소 힙

'부모 노드의 키 값 <= 자식 노드의 키 값'인 완전 이진 트리

 

 

 

- 부모 노드와 자식 노드의 관계

 

왼쪽 자식 인덱스 :  부모 인덱스 * 2 

오른쪽 자식 인덱스 : 부모 인덱스 * 2 + 1

부모 인덱스 : 자식 인덱스 / 2 

 

 

 

 

 

- 힙 삽입

 

힙에 새로운 요소가 들어오면,

 

1. 힙의 마지막 노드에 이어서 삽입한다.

2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.

 

최대 힙

 

 

 

- 힙 삭제

 

1. 최대 힙에서 최대 값은 루트 노드이다. 따라서 루트 노드를 삭제한다.

2. 삭제된 루트 노드에, 힙의 마지막 노드를 가져와 삽입한다.

3. 힙을 재구성한다.

 

최대 힙

 

 

 

 

 

이 게시글은 아래 링크를 참고했습니다.

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

[자료구조] 힙(heap)이란 - Heee's Development Blog