힙 Heap 자료구조

힙의 개념:

우선 순위 큐에 사용되는 자료구조이다. 트리로 작성된다.

힙이 제일 좋은거 같다.

 

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

대표적으로 최대힙과 최소힙이 존재한다.

 

- 최대 힙: 부모 노드의 key값이 자식 노드보다 크다. 

- 최소 힙: 부모 노드의 key값이 자식 노드보다 작다.

힙의 구조: 

일반적으로 배열로 구현이 된다. 

첫번째 인덱스인 0은 사용이 되지 않으며 1이 root 노드로 사용된다.

이용사례:

- 시뮬레이션 시스템

- 네트워크 트래픽 제어 (다익스트라, 병목 제어)

- 운영 체제에서의 작업 스케쥴링 (동적 힙 구조 응용)