data-structures - 이진 - 이항 힙



피보나치 힙 또는 Brodal 대기열이 실제로 어디서나 사용됩니까? (1)

필자가 아는 한 실제로 피보나치 힙이나 Brodal 큐를 사용하는 주요 응용 프로그램은 없습니다.

피보나치 힙은 처음에는 Dijkstra의 최단 경로 알고리즘을 점근 적으로 속도를 높이기 위해 이론적 인 필요성보다는 실용적인 필요성을 충족 시키도록 설계되었습니다. Brodal 대기열 (및 관련 기능적 데이터 구조)은 피보나치 힙의 시간 경계를 상각 된 보증이 아닌 최악의 경우의 보증과 일치시키는 것이 가능한지에 대한 오랜 질문에 대한 이론적 보증을 충족시키기 위해 유사하게 설계되었습니다 . 이러한 의미에서 데이터 구조는 실제 필요를 충족시키기 위해 개발 된 것이 아니라 알고리즘 효율성의 한계에 대한 이론적 이해를 촉진하는 데 도움이됩니다. 필자가 아는 한, 현재 피보나치 힙보다 Brodal 큐를 사용하는 것이 더 나은 현재 알고리즘은 없습니다.

다른 답변에서 지적했듯이 피보나치 힙 또는 Brodal 큐에 숨어있는 상수 요소는 매우 높습니다. 그들은 많은 복잡한 링크 된 목록에 연결된 많은 포인터를 필요로하므로 표준 바이너리 힙과 비교할 때 절대적으로 끔찍한 참조 지역을 가지고 있습니다. 이는 엄청나게 많은 수의 감소 키 연산을 필요로하는 알고리즘을 가지고 있지 않으면 실제로 캐싱 효과가 주어지면 실제로 성능이 저하 될 수 있음을 의미합니다. 이 문제가 발생하는 몇 가지 사례가 있습니다 (예를 들어, 링크 된 답변은 그 중 일부에 관한 것입니다). 그러나 일반적인 사용 사례보다는 고도로 전문화 된 상황으로 취급하십시오. 거대한 그래프 작업을하는 경우, 현재의 문제에 근사 알고리즘을 사용하는 것과 같은 더 효율적인 방법이나 기본 데이터의 특정 속성을 사용하는 알고리즘과 같은 다른 기법을 사용하여 효율성을 향상시키는 것이 일반적입니다.

희망이 도움이!

피보나치 힙은 실제로 어디서나 사용됩니까? 나는 주변을 둘러 보았고 관련 질문에 대한 답변을 찾았지만 (아래 참조) 실제로 질문에 답하는 것은 아무것도 없습니다.

  1. Boost C ++와 같은 표준 라이브러리를 포함하여 피보나치 힙이 잘 구현되어 있습니다. 이 라이브러리가 피보나치 힙을 포함하고 있다는 사실은 그들이 어딘가에 유용해야한다는 것을 암시합니다.
  2. 실제로 피보나치 힙이 더 빨리 수행되기 위해서는 특정 조건이 충족되어야합니다. "실제로 피보나치 힙을 사용하려면 reduce_keys가 매우 빈번한 응용 프로그램에서 사용해야합니다 ." " 비싼 비교 : Fib Heaps는 데이터 구성에 필요한 비교 횟수를 최소화합니다 .b) 대부분의 작업은 updateKey / insert / delete입니다. 피보나치 힙이 실제로 빛나기 위해서는 다음 중 하나가 필요합니다. 다음 extractMin이 될 때까지 업데이트를 '그룹화'하십시오. '배치'가 클수록 더 효율적입니다. "
  3. "Brodal Queue"라고 불리는 데이터 구조가 있습니다. 필자는 이것이 적어도 피보나치 힙만큼이나 시간 복잡성을 갖는 것으로 보입니다. 다양한 종류의 힙에 대한 다양한 작업을위한 시간 복잡성을 비교 한 멋진 테이블이 있습니다.
  4. 피보나치 (Fibonacci) 또는 이항 힙 (heap)의 적용 여부에 대한 질문에 응답자는 이항 힙의 예제만을 제공했습니다.




fibonacci-heap