• 우선순위 큐: 우선 순위의 개념을 큐에 도입한 자료 구조

  데이터들이 우선 순위를 가지고 있고 우선 순위가 높은 데이터가 먼저 나간다.

완전이진트리(Complete Binary Tree)

한 binary tree가 height로 H를 갖고 있다고 할 때,

이 트리의 노드는 0부터 H까지의 depth를 갖는다.

depth가 d인 부분에서는, 가능한 노드들의 최대 개수는 2^d이다.

만약 꽉 찬 트리가 height로 h를 가질 때,

이 트리는 2^0 + 2^1 + 2^2 + … + 2^h = 2^h+1 -1 노드를 갖는다.

완전이진트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며,

마지막 레벨의 노드는 가능한 한 가장 왼쪽에 있다.

Heap이란?

• 완전 이진 트리의 일종으로 우선 순위 큐를 위하여 만들어진 자료구조
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조

1. Max heap

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

2. Min heap

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

• 힙을 저장하는 표준적인 자료구조는 배열이다.
• 구현의 편리성을 위해 배열의 첫 번째 인덱스인 0은 사용되지 않는다.