[자료구조] 힙(heap)

<목표>

* heap에 대한 이해

* 배열, c++을 이용하여 heap을 구현

 

<힙 이란>

* 완전 이진 트리의 일종으로 우선순위 큐를 구현하기 위해 만들어진 자료구조

* 여러 개의 값들 중에서 최댓값이나  최솟값을 빠르게 찾아낼 수 있다.

* 힙은 반정렬 상태를 유지

  -. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있는 정도(혹은 그 반대)

* 힙 트리에서는 중복된 값을 허용한다.

 

<힙의 종류>

* 최대 힙, 최소 힙

  -. 부모 노드의 키 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리 key(부모노드) >= key(자식노드)

  -. 최소 힙은 그 반대

* 도식화

최대 힙과 최소 힙

 

<힙의 구현>

* 힙을 저장하는 표준적인 자료구조는 배열 이다.

* 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다.

* 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.

* 힙에서의 부모 노드와 자식 노드의 관계

  -. 왼쪽 자식의 인덱스 = 부모의 인덱스 * 2

  -. 오른쪽 자식의 인덱스 = 부모의 인덱스 * 2 + 1

  -. 부모의 인덱스 = 자식의 인덱스 / 2

* 도식화

부모노드와 자식노드 관계

오늘은 여기까지