최대 힙 대 균형 BST를 사용하여 우선 순위 큐 구현
균형 잡힌 BST 및 최대 힙은 모두에서 삽입 및 삭제를 수행 O(logn)합니다. 그러나 최대 힙에서 최대 값을 찾는 O(1)것은 O(logn)균형 잡힌 BST입니다.
최대 힙에서 최대 값을 제거하면 O(logn)삭제 작업이기 때문에 걸립니다 .
균형 BST에서 최대 요소 삭제 = 최대 값 찾기 + 삭제; 그것은 logn + logn과 같습니다 O(logn). 따라서 균형 잡힌 BST에서 최대 값을 삭제해도 O(logn).
나는 max heap의 이러한 응용 프로그램이 우선 순위 대기열 이며 주요 목적은 모든 대기열에서 빼기 작업에 대한 최대 값을 제거하는 것임을 읽었습니다 . 최대 요소 삭제가 O(logn)최대 힙 및 균형 BST 모두에 해당하는 경우 다음과 같은 질문이 있습니다.
전체 검색 가능한 균형 BST를 사용하는 것보다 구현하기 쉽기 때문에 우선 순위 대기열에서 최대 힙의 목적은 무엇입니까?
균형 요소 계산이 없기 때문에 최대 힙을 불균형 이진 트리라고 부를 수 있습니까?
균형 잡힌 모든 BST는 우선 순위 대기열로 사용할 수 있으며
O(logn)최대 힙 검색이O(n)올바른 경우 에도 검색 할 수 있습니까?
최악의 경우 항상 복잡성이 계산됩니다. 어떤 도움이라도 대단히 감사합니다.
답변
전체 검색 가능한 균형 BST를 사용하는 것보다 구현하기 쉽기 때문에 우선 순위 대기열에서 최대 힙의 목적은 무엇입니까?
힙의 장점은 다음과 같습니다.
정렬되지 않은 배열을 입력 받아, 힙 여전히 구축 될 수 O (n)의 시간 동안, BST 필요한 O (nlogn) 시간 .
초기 입력이 배열 인 경우 동일한 배열이 힙 역할을 할 수 있으므로 추가 메모리가 필요하지 않습니다. 배열의 제자리에있는 데이터를 사용하여 BST를 만드는 방법을 생각할 수는 있지만 (기본 유형의 경우) 상당히 이상하고 더 많은 처리 오버 헤드를 제공합니다. BST는 일반적으로 처음부터 생성되어 생성 된 데이터를 노드에 복사합니다.
흥미로운 사실 : 정렬 된 배열도 힙이므로 입력이 정렬 된 것으로 알려진 경우 힙을 빌드하기 위해 수행 할 작업이 없습니다.
힙은 상호 참조 를 저장할 필요없이 배열로 저장할 수 있지만 BST는 일반적으로 왼쪽 및 오른쪽 참조가있는 노드로 구성됩니다. 이는 최소한 두 가지 결과를 가져옵니다.
- BST에 사용되는 메모리는 힙보다 약 3 배 더 큽니다.
- 여러 작업이 힙과 BST 모두에 대해 동일한 시간 복잡도를 갖지만 BST를 조정하는 오버 헤드가 훨씬 더 크기 때문에 이러한 작업에 소요되는 실제 시간이 BST 사례에서 더 큰 (상수) 요소입니다.
균형 요소 계산이 없기 때문에 최대 힙을 불균형 이진 트리라고 부를 수 있습니까?
힙은 사실 완전한 이진 트리 이므로 항상 균형이 잡혀 있습니다. 잎은 항상 마지막 또는 마지막 수준에 배치됩니다. 자체 균형 BST (예 : AVL, 빨강-검정, ...)는 높은 수준의 균형을 이길 수 없습니다. 여기서는 잎이 세 단계 이상에서 발생하는 경우가 많습니다.
균형 잡힌 모든 BST를 우선 순위 대기열로 사용할 수 있으며 O (logn)에서도 검색 할 수 있지만 최대 힙 검색이 O (n) 정확합니까?
그래 이건 사실이야. 따라서 응용 프로그램에 검색 기능이 필요한 경우 BST가 더 우수합니다.
전체 검색 가능한 균형 BST를 사용하는 것보다 구현하기 쉽기 때문에 우선 순위 대기열에서 최대 힙의 목적은 무엇입니까?
아니. 최대 힙은 O (1) 시간에 최대한 빨리 다음 (우선 순위를 존중하는) 요소를 반환하도록 신중하게 계측되었으므로 더 적합합니다. 이것이 가능한 가장 간단한 우선 순위 대기열에서 원하는 것입니다.
균형 요소 계산이 없기 때문에 최대 힙을 불균형 이진 트리라고 부를 수 있습니까?
아니. 균형도 있습니다. 간단히 말해서, 힙의 균형은 위로 또는 아래로 시프트 작업 (순서가 잘못된 요소 교체)에 의해 수행됩니다.
균형 잡힌 모든 BST를 우선 순위 대기열로 사용할 수 있으며 O (logn)에서도 검색 할 수 있지만 최대 힙 검색이 O (n) 정확합니까?
네! 뿐만 아니라 연결된 목록을 사용하거나 배열 할 수 있습니다. O 표기법 측면에서 더 비싸고 연습에서는 훨씬 느립니다.