우선순위 큐와 힙

관련된 문제(https://sungsikyang92.tistory.com/242)

우선순위 큐와 힙

우선순위 큐는 Queue 자료구조와 같다고 생각 할 수 있지만, 다르다. 우선순위 큐는 FIFO가 아니라, 우선순위가 가장 높은 자료가 먼저 꺼내진다. 이에 heap이라는 트리로 우선순위 큐를 구현한다. heap은 가장 큰 원소를 찾는 데 최적화된 형태의 이진트리로, 힙을 사용하면 새 원소를 추가하는 연산과 가장 큰 원소를 꺼내는 연산을 모두 O(lgN) 시간에 수행할 수 있다.

힙

힙은 특정한 규칙을 만족하도록 구성된 이진 트리이다. 가장 중요한 규칙은 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소 이상이라는 것이다. 이것을 힙의 대소 관계 규칙이라고 한다. 힙에서 대소 관계 규칙은 이진 검색 트리와는 달리 부모 자식 관계에만 적용되며, 왼쪽 자식과 오른쪽 자식이 갖는 원소의 크기는 제한하지 않는다. 또한 힙은 트리의 높이를 항상 일정하게 유지하기 위해 트리의 구조에 제약을 둔다.

1. 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다.
2. 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 한다.

힙은 엄격한 모양 규칙을 요구한다

위의 이미지를 보면 알 수 있듯이,

• A[i]에 대응되는 노드의 왼쪽 자손은 A[2 * i + 1]에 대응된다.
• A[i]에 대응되는 노드의 오른쪽 자손은 A[2 * i + 2]에 대응된다.
• A[i]에 대응되는 노드의 부모는 A[(i-1)/2]에 대응된다.

새 원소 삽입

힙에서는 이진 검색 트리와 다르게 모양 규칙이 어느 서브트리로 들어가야 할지를 결정해 준다.

모양 규칙에 의해 새 노드는 항상 heap[]의 맨 끝에 추가된다. 그리고 마지막에 추가한 새 원소를 자신의 부모 노드가 가진 원소와 비교하고, 부모 노드가 가진 원소가 작다면 두 원소의 위치를 바꾼다. 새 원소가 더 크거나 같은 원소를 가진 부모 노드를 만나거나, 루트에 도달할 때까지 반복한다. 삽입의 시간 복잡도는 트리의 높이인 O(lgN)이 된다.

최대 원소 꺼내기

힙 배열의 첫 원소를 확인하면 된다. 힙의 모양 구조에 의해 힙의 마지막 노드를 일단 지우고 시작한다. 그리고 그 마지막 노드의 원소를 루트에 덮어 씌운다. 그렇게 되면 우선 힙의 모양 규칙은 위배되지 않는다. 그 후, 대소 관계 조건을 만족시키기 위해, 부모와 자식간의 대소비교를 해주며 원소를 맞바꿔준다. while문이 한 번 실행될 때마다 트리의 아래 레벨로 내려가기 때문에, 시간 복잡도는 O(lgN)이 된다.

출처 - 프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 구종만 저