힙은 자료구조의 일종으로 우선순위큐를 위한 자료구조입니다.

우선순위 큐 : 우선순위의 개념을 큐에 도입한 자료구조입니다. 데이터들이 우선순위를 가지고있으며, 우선순위가 높은 데이터가 큐에서 먼저 빠져나갑니다.
우선순위큐는 주로 시뮬레이션 시스템, 스케쥴링, 수치해석 등에 사용됩니다.
배열, 연결 리스트, 힙으로 구현할 수 있는데 힙으로 구현하는게 가장 효율적입니다.
우선순위큐의 삽입, 삭제 시간복잡도는 O(logN)입니다.

힙

Tree형식이며, 배열을 기반으로 한 완전이진트리입니다.
최대값 및 최소값을 찾아내는 연산을 빠르게하기 위해 고안된 완전이진트리입니다.
배열의 트리값을 삽입할때, 0번째는 건너뛰고 1번째부터 루트노드가 시작됩니다. 이렇게하면 고유번호와 index를 일치할 수 있으니 혼동이 줄어듭니다.
중복된 값을 허용합니다. 이진탐색트리는 중복값을 허용하지 않죠.
힙의 종류로는 최소힙, 최대힙이 존재합니다.
- 최대힙 : 각 노드의 값이 자식노드 값보다 크거나 같은 완전 이진트리를 말합니다.
- 최소힙 : 최대힙 반대입니닷
- 최대힙에서는 루트노드에 있는 값이 제일 크므로, 최대값을 찾는데 소요되는 연산의 시간복잡도는 O(1)입니다.
- 완전 이진트리이므로 배열을 이용해 관리할 수 있으며, 인덱스를 통해 랜덤액세스 역시 가능합니다.
- index번호는 i번째 노드에 대해 왼쪽 자식은 i2, 오른쪽 자식은 i2+1이 됩니다.

힙 구현

배열을 통해 힙을 구현합니다(일반적으로).

배열의 첫번째 인덱스는 사용하지 않고 1부터 시작합니다.

< 부모노드와 자식 노드의 관계>

< 힙의 삽입 >