힙(Heap)

힙(Heap) 특징

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

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

 3. 힙은 반 정렬 상태를 유지한다. 

 4. 힙 트리는 중복 값을 허용한다.

우선순위 큐 

 1. 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 나가는 구조 

 2. CPU 작업 스케쥴링, 시뮬레이션 시스템에서 사용

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

힙 종류 

 1. 최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리 

 2. 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리 

힙 구현 특징

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

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

예제 - 최대 힙

- 최대 힙 -

< 참고자료 >

 

[도서] 자료구조  - 정광식 지음-

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

 

<Data structures> chapter 7,  힙(Heap) end