사용자 도구

사이트 도구


ps:우선순위큐

우선순위 큐

  • 기본적인 내용은 Priority Queue 참고
  • insert, find-min, extract-min을 빠르게 처리하는 자료 구조이다. 다양한 구현법이 존재하지만, 대표적인 것은 binary heap이다. 여러 언어의 기본 라이브러리에서 제공하는 것도 바이너리 힙이다.
  • 위키 페이지에 보면 그 외에도, bimodal heap, pairing heap, 등등 여러 방법이 언급되고 있는데, 그나마 다른데에서 들어봤을 만한 것은 Fibonacci heap 정도이고, 나머지는 굳이 알 필요성을 못느꼈다.
  • 기본적인 바이너리 힙은, insert와 extract-min을 O(logn)에 처리하고, heapify를 O(n)에 처리하는데, 사실 이것은 Order Statistic Tree로도 가능하다. 그러나 상수값의 차이로 heap을 쓰는 것이 빠르다.
  • 아래에는 우선순위큐를 사용한 몇가지 테크닉을 설명할건데, 이것들은 속도가 좀 느리기는 하지만 Order Statistic Tree로도 모두 가능하긴 하다. cpp라면 multiset을 그냥 쓰면 되니까 따로 코딩면에서 더 편할수도 있다. 다만 python에서는 어차피 Order Statistic Tree도 따로 구현해주어야 한다.
    • 이 내용은 공통적으로 적용되는 내용이라 아래에서 다시 언급하지 않겠다.

임의 원소 삭제를 지원하는 힙

  • 라이브러리에서 제공되는 binary힙은 임의 원소의 삭제나 수정 기능이 없다. 하지만 이러한 연산이 필요한 경우가 종종 있다.
    • 사실 삭제만 제공되면 수정은 {수정 전의 값 삭제} + {수정 후의 값 삽입}으로 처리가 가능하다.
  • 그냥 이러한 기능을 지원하는 힙을 새로 구현하는 방법도 있다. 구현이 그렇게 어려운 것도 아니지만 좀 귀찮다. http://www.secmem.org/blog/2020/08/16/heap/ 참고
  • 보다 쉬운 방법은, 실제로 원소를 삭제하는 대신 원소에 마크만 해두고, 마크해둔 원소가 탑에 올라오면 그때 삭제를 하는 것이다. 새로 힙을 구현할 필요 없이 라이브러리에 이미 구현되어있는 힙을 사용할수 있다.
  • 마크를 하는 데에는 몇가지 구현 방법이 있다. 위의 파이썬 공식문서에서는 힙에 들어가는 노드에 값과 마크를 같이 저장하고, 값을 노드로 매핑하는 딕셔너리를 따로 유지해서, 노드에 바로 마크를 수정하는 방법을 설명한다. 그러나 이 방법은 메모리 측면이나 속도 측면 모두에서 덜 효과적이다.
  • 그것보다는 지워진 원소들을 다른 곳에 따로 저장해서 갖고 있는 방법이 있다. 단순하게 내가 생각했던 방법은 그냥 지워진 원소를 저장하는 셋을 만들어두고, 셋에 포함되어 있는 값이 힙의 top에 올라오면, 그 값을 heap과 셋에서 둘다 지우는 방법이었다. 그러나 이경우에 중복된 값이 여러개 있을수도 있으니까, 셋 대신 카운터를 쓰는 것으로 방법을 수정했다.
  • 인터넷에서 찾은 다른 방법은 지워진 원소들을 또다른 힙에 저장하는 것이다. 원래 힙의 top과 지워진 원소를 저장하는 힙의 top가 동일하면 양쪽에서 모두 pop을 해주는 것. 지워진 원소들을 힙에 저장하느냐 dict에 저장하느냐의 문제인데, 시간복잡도만으로는 dict가 더 빠르지만 이중 우선순위 큐 의 제출 결과로는 heap쪽이 더 빨랐다.

Double-ended priority queue

  • extract-min 과 extract-max를 동시에 지원하는 우선순위큐이다. Double-ended priority queue 참조
  • 가장 효율적인 것은 Min-max heap을 구현해서 사용하는 것이라고 생각되지만, 그러면 라이브러리에 제공되는 힙을 사용하지 못하고 전부 처음부터 짜야 한다.
  • 대신 Double-ended priority queue에서 소개된 방법들처럼 일반적인 PQ를 잘 조합해서 양방향 PQ로 사용하는 것도 가능하다.
  • 그중에서도 가장 간단하게 구현할 수 있는 방법은 삭제가 지원되는 힙을, max heap과 min heap으로 두개를 만들어 놓고서, 원소를 삽입할때에는 두 힙에 모두 삽입하고, 최댓값을 추출하고 싶으면 max heap에서 최댓값을 추출한 뒤 min heap에서는 그 값을 삭제, 최솟값을 추출할때는 그 반대로 작업하는 방법이 있다.

관련 문제

Running Median

  • 원소가 계속 삽입 삭제될때, 중앙값을 빠르게 업데이트하는 방법. 바꿔 말하면 중간값 우선순위큐를 구현하는 방법이다.
  • min heap과 max heap 두개의 힙을 만들어서 max heap의 원소들은 모두 min heap의 원소들보다 작고, 두 힙의 원소의 갯수 차이가 1이라가 되도록 유지하면, max heap의 top이 항상 median으로 유지된다는 내용이다.
  • 이 기법을 조금 더 변형하면 고정된 k에 대해서 k-th 원소를 추출할수 있는 힙을 만들수도 있겠다.

관련 문제

가장 큰 수 k개 찾기

  • 리스트에서 가장 큰 수 k개를 찾는 작업을 우선순위큐를 사용해서 효율적으로 수행하는 방법이다.
  • 1. 정렬 방법
    • 그냥 전체를 정렬하고 앞에서부터 k개를 끊으면 정렬에 O(nlogn)이 걸리고, k개의 원소를 찾는데에 O(k). 총 O(nlogn)
  • 2. 최대힙
    • 전체를 최대힙에 넣고 k번의 pop을 처리하면, 힙을 만드는데에 O(n) + k번의 pop에 O(klogn). 총 O(n+klogn)
  • 3. 최소힙
    • k개의 원소만을 갖고 최소힙을 만든다. 그 다음에, 남은 n-k개의 원소들에 대해서 힙에 추가하고, 힙에서 가장 작은 원소를 꺼내는 것을 반복한다. 마지막까지 힙에 남은 k개의 원소가 가장 큰 k개의 수이다. 순서대로 pop하면 순서에 맞춰서 꺼낼 수 있다. 처음 힙을 만드는 데에 O(k) + 나머지 n-k개의 원소를 처리하는데에 O((n-k)*logk). 마지막에 힙에 남은 원소를 꺼내는 것은 O(klogk). 총 O(nlogk)

토론

댓글을 입력하세요:
X Q W O Z
 
ps/우선순위큐.txt · 마지막으로 수정됨: 2021/05/24 09:34 저자 teferi