읽고 나면 진짜 쉬워지는 자료 구조 - 7. 우선순위 큐와 힙

집합에서 우선순위가 지정된 항목을 탐색하는 자료구조: 우선순위 큐, 그리고 이 유용한 도구를 구현하는 가장 일반적인 자료구조인 힙(heap)

🔖 7.1 우선순위 큐

큐와 힙 비교

• 우선순위 큐는 항목 집합을 저장하며, 가장 높은 우선순위를 가진 항목을 효율적으로 탐색하고 제거할 수 있도록 설계된 자료구조임

• e.g. 네트워크 요청 처리 시, 각 패킷마다 명시적인 우선순위가 부여될 수 있음. 이 경우 우선순위 큐를 사용해 높은 우선순위의 요청을 먼저 처리할 수 있음.

• 우선순위 큐를 구현할 때, 정렬된 리스트를 사용하는 방식과 정렬되지 않은 리스트를 사용하는 방식이 있음. 그러나 두 방식 모두 효율성에서 단점이 있을 수 있음.

• 정렬된 리스트는 삽입 작업이 느림. 정렬되지 않은 리스트는 우선순위가 높은 항목을 찾는 작업이 느림.

• 이때 힙을 사용하면, 우선순위 큐의 효율성을 개선할 수 있음. 힙은 삽입과 삭제 작업 모두 log 시간 복잡도로 처리 가능하기 때문임. 특히, 최대 힙 또는 최소 힙은 우선순위 큐를 구현하는 데 효과적임.

🔖 7.2 최대 힙

최대 힙이란?

• 노드와 그 자식 간 특별한 순서를 유지하는 이진 트리의 변형. 최대 힙은 최대 힙 속성(max heap property)에 따라 원소를 저장함

• 최대 힙 속성이란? 트리의 모든 노드 값이 자신의 자식 노드 값보다 크거나 같음을 의미.

최대 힙을 사용하면

• 사용자가 가장 큰 원소를 효율적으로 사용 가능

• 가장 큰 원소를 효율적으로 제거 가능

• 임의의 원소를 효율적으로 추가 가능

힙에 원소 추가하기

• 새로 추가한 노드의 모든 조상 노드는 추가된 노드보다 더 우선순위가 높아야 한다.

• 힙에 새로운 원소를 추가하려면 트리의 가장 아래쪽 첫 번째로 비어있는 공간에 원소를 추가해야 한다.

힙에 가장 큰 원소 제거

• 예를 들어, 대기 중인 네트워크 요청 목록을 저장하고, 높은 우선순위의 요청을 처리

• 먼저 힙 속성을 깨뜨리고 다시 복원해야 함

🔖 7.3 우선순위 갱신하기

처리 방법

• 항목의 값을 증가시키는 경우, 최대 힙에서 항목을 위로 올려보내며 힙 속성을 복원해야 한다.

• 원소를 위로 올려보내거나 아래로 내려보내는 코드를 별도로 분할하면 최댓값을 추가하거나 제거할 때 똑같은 코드를 업데이트 하는데에 활용 가능

🔖 7.4 최소 힙

최소 힙이란?

• 가장 낮은 값의 항목을 쉽게 찾기 위한 힙

• 예를 들어, 우선순위에 따라 네트워크 패킷 정렬하는 대신, 도착한 시간순으로 정렬하고 먼저 도착한 패킷 처리

• 이론적으로는 값의 부호만 바꾸고 최대 힙 계속 사용 가능하나, 힙 속성에 작은 수정을 더해 문제를 완전히 해결

🔖 7.5 힙 정렬

힙 정렬이란?

• 힙 자료구조를 사용해 원소의 목록을 정렬하는 알고리즘

• 입력은 정렬되지 않은 배열이고, 출력은 동일한 원소를 포함하지만 내림차순으로 정렬된 배열

힙 정렬의 단계

• 모든 항목에서 최대 힙 구축

• 힙에서 모든 항목을 내림차순으로 추출하고 배열에 저장

시간 복잡도

• 삽입과 마찬가지로 최악의 경우 실행 시간이 Nlog₂(N)에 비례

• 각 추출에서 힙 속성을 복원하는데에 최대 log₂(N)이 소요

• 정렬된 목록을 얻으려면 모든 N개 항목을 추출해야 한다.