힙과 우선순위 큐

힙(Heap)

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

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

힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다.(큰 값이 상위에 작은 값이 하위 레벨이 있다는 정도)

=>부모 노드의 키 값이 항상 자식 노드의 키 값보다 크다.

 

최대힙(Max heap) vs 최소 힙(Min heap)

최대 힙은 부모 노드의 key가 자식 노드의 키보다 크거나 같은 이진 트리,

최소 힙은 부모 노드이 key가 자식 노드의 키보다 작거나 같은 이진 트리이다.

 

힙의 구현

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

구현을 쉽게 하기 위해 배열의 첫번째 인덱스로 1을 사용한다.

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

힙의 삽입(Insert)

1. 힙에 새로운 원소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
2. 새로운 노드를 부모 노드들과 바꿔가면서 힙의 성질을 만족시킨다.

힙의 삭제(Delete)

1. 루트 노드를 삭제한다.
2. 루트 노드의 자리에 힙의 마지막 노드를 가져온다.
3. 힙을 재구성한다.

우선순위 큐(Priority Queue)

우선순위 큐란 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조를 뜻한다.

우선순위 큐는 힙을 이용해서 구현가능하다.