우선순위 큐

• 순서대로 기다리고 있는 자료들을 저장하는 자료구조라는 점에서 큐와 비슷
• 가장 먼저 입력된 자료가 가장 먼저 꺼내지는 것이 아니라, 우선순위가 가장 높은 자료가 가장 먼저 꺼내짐
• 힙 트리 사용

힙

• 가장 큰 원소를 찾는 데 최적화된 형태의 이진 트리
• 가장 큰 원소(max-heap), 가장 작은 원소(min-heap)
• 힙을 사용하면 새 원소를 추가하는 연산과 가장 큰 원소를 꺼내는 연산을 모두 O(logN)

힙의 가장 중요한 규칙

• 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소 이상 : 힙의 대소 관계 규칙
• 대소 관계 규칙은 이진 검색 트리와는 달리 부모 자식 관계에만 적용되며, 왼쪽 자식과 오른쪽 자식이 갖는 원소의 크기는 제한하지 않음
• 트리에서 가장 큰 원소는 항상 트리의 루트에 들어감

힙의 모양 규칙

• 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 함
• 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 함 (트리의 레벨 : 깊이가 같은 노드) -> 이 규칙을 만족할 때 힙의 높이는 O(logN)임

###배열을 이용한 힙의 구현

• 텅 빈 힙에 원소를 산입하면 맨 윈 레벨의 왼쪽 끝부터 노드들이 순서대로 추가
• 따라서 일차원 배열 A[]의 각 원소와 힘의 노드들을 일대일 대응 가능
• A[i]에 대응되는 노드의 왼쪽 자손은 A[2*i+1]
• A[i]에 대응되는 노드의 오른쪽 자손은 A[2*i+2]
• A[i]에 대응되는 노드의 부모는 A[(i-1)/2] (결과는 내림)

새 원소의 삽입

• 새로운 노드는 항상 heap[]의 맨 끝에 추가됨
• 마지막에 추가한 새 원소를 자신의 부모 노드가 가진 원소와 비교
• 부모 노드가 가진 원소가 작다면 두 원소의 위치를 바꿈
• 새 원소가 더 크거나 같은 원소를 가진 부모 노드를 만나거나 루트에 도달할 때까지 반복

최대 원소 꺼내기

• 최소 원소 찾는 것은 배열의 첫 원소를 확인하면 되므로 매우 간단
• 문제는 최대 원소를 힙에서 꺼내는 일
• 힙의 마지막에 있는 노드를 루트에 덮어씀
• 대소관계를 만족시키기 위해 두 자식 노드가 가징 원소 중 더 큰 원소와 루트와 바꿈
• 트리 바닥 혹은 두 자손이 자기 자신 이해 원소를 갖고있을 때까지 반복

다른 연산들

1. 힙정렬
   • 힙에서 원소들을 꺼낼 때 항상 정렬된 순서로 반환
   • 힙에서 원소를 하나 꺼내면 힙을 담은 배열의 맨 뒤쪽에 한 칸이 비게 되므로, 최대 원소를 여기에 옮기면 추가 메모리를 사용하지 않고 정렬을 구현 가능