우선순위 큐와 힙

우선순위 큐와 힙

힙

• 힙 순서 속성(Heap Order Property)를 만족하는 완전 이진 트리
• 힙을 이용해 우선순위 큐를 구현할 수 있음

힙 삽입

• 힙의 최고 깊이, 최 우측에 새 노드 추가, 완전 이진 트리를 만족 시켜야 함
• 삽입한 노드를 부모 노드와 비교 후 부모 노드보다 우선순위가 높으면 부모 노드와 교환 (반복)

힙 제거

• 루트 노드가 우선순위가 가장 높기 때문에 루트 노드를 제거
• 최하위 최우측 노드를 루트에 넣고 자식과 우선순위 비교하면서 내려가기(반복)

힙 구현

• 보통 트리를 구현하는 링크드 리스트는 트리 최하위 최우측을 바로 알아내기가 어려움
• 배열을 이용, 자식 노드로의 링크는 인덱스값 * 2로 구현