정의 :
우선 순위 큐 정규 큐나 스택 데이터 구조처럼 추상 데이터 타입이지만, 여기서 별도로 각 요소에 "우선 순위"연관된했다 . 우선 순위 대기열에서 우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 게재됩니다. 두 요소의 우선 순위가 같으면 큐의 순서에 따라 제공됩니다.이진 힙의 다목적
구현 :
이 우선 순위 큐, 정렬되지 않은 배열, 정렬 된 배열 및 진 힙 데이터 구조 3 개 구현 전략이를 구현합니다.
은 즉, 이진 힙 구현 전략 배열 키,
또는
각 키이진 노드를 이용하여 표현 될 수 두 아이를 갖는 .
질문 :
외에도 우선 순위 큐 구현에서, 진 힙 데이터 구조를 사용하는 다른 응용 프로그램들이 있습니까?
바이너리 힙을 사용하여 O (logn) 시간에서 (최대 또는 최소) 요소를 추출 할 수 있습니다. 이 속성은 많은 알고리즘에서보다 나은 런타임을 얻기 위해 악용 될 수 있습니다.
예를 들어 한 번 k-merge 정렬 알고리즘을 사용하여 k-merge 정렬의 정렬 단계의 효율성을 높일 수 있습니다. 간단히 말해서, k- 서브 어레이의 바이너리 힙을 만들었고 정렬은 병합 정렬의 일반적인 정렬 단계보다 나은 선형 시간으로 이루어질 수 있습니다.
또한 Dijkstra의 알고리즘 인 Prim의 알고리즘을 사용하여 런타임을 줄입니다. 힙 정렬 :
또한 here
일정 시간 동안 이진 힙에서 요소를 추출 할 수 없습니다. * delete-min *은 O (log n) 연산입니다. 또한, OP는 우선 순위 큐를 구현하는 것 이외의 바이너리 힙의 사용을 요청했습니다. 모든 세 가지 예제 (병합 정렬, Dijkstra 알고리즘, Prim 알고리즘)는 우선 순위 대기열을 기반으로합니다. 바이너리 힙은 단지 편리한 구현이다. –
답을 바로 잡았습니다. 그것을 지적 해 주셔서 감사합니다. 나는 바이너리 힙의 사용법을 나열하려고 노력하고있다. 나는 그 구현에 대해서 이야기하지 않았다. 우선 순위 큐로 바이너리 힙을 사용하지 않는 상황이 있다면, 가장 좋은 의견을 남길 수 있습니다. 나는 기꺼이 배울 것입니다. – CODError
"추출 (최대 또는 최소) 요소"- 이것은 우선 순위 대기열의 정의이므로 사실상 질문에 대답하지 않았습니다. @ JimMischel이 지적했습니다. \t "우선 순위 대기열로 바이너리 힙을 사용하지 않는 경우 어떤 상황이 있다면"- 당신은 그것을 거꾸로 가지고 있습니다. 힙을 사용하지 않고 우선 순위 큐를 구현하는 몇 가지 방법이 있습니다 ... OP는 정렬 된 정렬되지 않은 배열을 언급하며 다른 여러 가지가 있습니다. 질문은 바이너리 힙이 다른 것에 대해 좋은지 여부입니다. 실제 대답은 내 대답을 참조하십시오. 편집 : 아마도 당신은 거꾸로, 그냥 가난하게 표현 된 생각하지 않았다. –
진 힙 한 다른 유용한 (주요) 응용 프로그램이 좀 걸릴 수 있습니다. HeapSort는 QuickSort보다 높은 오버 헤드를 가지고 있지만 최악의 경우는 O (n log n) 대 QuickSort의 O (n * n)입니다. QuickSort는 간격이 충분히 짧으면 HeapSort로 전환하여 O (n log n)의 최악의 경우를 얻도록 개선 될 수 있습니다. 이것은 IntroSort라고하며 STL 및 C++ 표준 라이브러리에서 사용되는 것입니다. https://en.wikipedia.org/wiki/Introsort
참조 힙 정렬을 참조하십시오. –
아닙니다. 심지어 힙소 (heapsort) 라 할지라도 우선 순위 대기열을 채우고 순서대로 꺼내는 것입니다. 이진 힙 *은 우선 순위 큐입니다.가장 중요한 질문은 우선 순위 대기열의 응용 프로그램과 이진 힙으로 가장 잘 구현되고 다른 우선 순위 대기열 구현을 사용해야하는 응용 프로그램이 무엇인지에 있습니다. –
1. 복사 한 출처에 적절한 저작자 표시를하십시오. http://stackoverflow.com/help/referencing을 참조하십시오. 2. 바이너리 힙의 모든 응용 프로그램 목록을 요청하는 것은 너무 광범위합니다. 3. 어떤 연구를 해왔습니까? 데이터 구조 교과서에서 힙을 사용하여 수행 한 작업을 확인 했습니까? –