[자료구조] 힙, Heap

힙구조는 우선순위 큐를 위하여 만들어진 자료구조라고 한다.

 

자료구조 '힙(heap)' 이란?

 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.

 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

 힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다.

 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도

 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진트리를 말한다.

 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)

 

힙의 종류

최대힙 (max heap)

   - 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

   - key(부모노드) >= key(자식노드)

 

최소힙 (min heap)

   - 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

   - key(부모노드) <= key(자식노드)

 

힙의 구현

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

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

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

 

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

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

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

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

 

 

 

[REFERENCE]

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

https://www.youtube.com/watch?v=jfwjyJvbbBI