이 두 가지는 매우 비슷해 보이며 거의 동일한 구조를 가지고 있습니다. 차이점은 무엇입니까? 각 작업에 대한 시간 복잡성은 무엇입니까?

답변

Heap은 상위 레벨의 요소가 하위 레벨의 요소보다 크거나 (최대 힙의 경우) 작게 (최소 힙의 경우) 보장하는 반면 BST는 순서 ( “왼쪽”에서 “오른쪽”으로)를 보장합니다. . 정렬 된 요소를 원하는 경우 BST를 사용하세요. by Dante는 괴짜가 아닙니다

힙은 findMin / findMax (O ( 1)), BST는 모든 발견에 적합하지만 (O (logN)). 두 구조 모두에 대해 Insert는 O (logN)입니다. findMin / findMax 만 신경 쓰는 경우 (예 : 우선 순위 관련) 힙을 사용하십시오. 모든 정렬은 BST로 진행됩니다.

by xysun

댓글

  • BST가 findMin & findMax stackoverflow에서 더 낫다고 생각합니다. .com / a / 27074221 / 764592
  • 이것은 단지 통신 인 것 같습니다 오해에. 이진 트리는 Yeo가 가리키는 최소값과 최대 값을 찾기 위해 쉽게 수정할 수 있습니다. 이것은 실제로 힙의 제한 입니다. 유일한 효율적인 찾기는 최소 또는 최대입니다. 힙의 진정한 장점은 제가 설명했듯이 O (1) 평균 삽입 입니다. stackoverflow.com/a/29548834/895245
  • 이 동영상 에 따르면 큰 값이 낮은 값의 하위 항목이 아닌 한 낮은 수준에서 더 큰 값을 가질 수 있습니다.
  • 힙은 루트에서 리프로 정렬되고 BST는 왼쪽에서 오른쪽으로 정렬됩니다.
  • 일정한 시간에 중앙값을 찾고 로그 시간의 중앙값을 제거하려면 어떻게해야합니까? 어떤 데이터 구조로 가야합니까? MinHeap 구현이 작동합니까? 제안 해주세요.

답변

요약 

 Type BST (*) Heap Insert average log(n) 1 Insert worst log(n) log(n) or n (***) Find any worst log(n) n Find max worst 1 (**) 1 Create worst n log(n) n Delete worst log(n) log(n)

이 테이블의 모든 평균 시간은 삽입을 제외하고 최악의 시간과 동일합니다.

  • * :이 답변의 모든 곳에서 BST == Balanced BST, unbalanced는 점근 적으로 짜증이 나기 때문입니다.
  • ** :이 답변에 설명 된 사소한 수정 사용
  • *** : 포인터 트리 힙의 경우 log(n), n 동적 배열 힙용

BST보다 바이너리 힙의 장점

바이너리 힙보다 BST의 장점

  • 임의 요소 검색은 O(log(n)). 이 는 BST의 킬러 기능입니다.

    힙의 경우 일반적으로, O(1) 인 가장 큰 요소는 예외입니다.

BST에 비해 힙의 “거짓”이점

  • 힙은 최대 값을 찾기위한 O(1), BST O(log(n))입니다.

    가장 큰 요소를 추적하기 위해 BST를 수정하고 해당 요소가 변경 될 수있을 때마다 업데이트하는 것이 사소하기 때문에 일반적인 오해입니다. 더 큰 스왑을 삽입 할 때 제거시 두 번째로 큰 요소를 찾습니다. https://stackoverflow.com/questions/7878622/can-we-use-binary-search-tree-to-simulate-heap-operation ( Yeo가 언급 ).

    사실 이것은 BST에 비해 힙의 제한 입니다. 유일한 효율적인 검색은 가장 큰 요소에 대한 검색입니다.

평균 바이너리 힙 삽입은 O(1)

출처 :

직관적 인 인수 :

  • 하단 트리 수준은 최상위 수준보다 기하 급수적으로 더 많은 요소를 포함하므로 새 요소는 거의 하단에 위치합니다.
  • 힙 삽입 하단에서 시작 , BST는 상단부터 시작해야 함

바이너리 힙에서 주어진 인덱스에서 값을 늘리는 것도 같은 이유로 O(1). 그러나 그렇게하려면 힙 작업에 대한 추가 인덱스를 최신 상태로 유지하는 것이 좋습니다. https://stackoverflow.com/questions/17009056/how-to-implement-ologn-decrease-key-operation-for-min-heap-based-priority-queu 예 Dijkstra를 위해. 추가 시간 비용없이 가능합니다.

실제 하드웨어에 대한 GCC C ++ 표준 라이브러리 삽입 벤치 마크

C ++ std::set ( 빨강-검정 나무 BST ) 및 ( 동적 배열 힙 ) 삽입하여 삽입 시간이 옳았는지 확인하면 다음과 같은 결과를 얻었습니다.

여기에 이미지 설명 입력

  • 벤치 마크 코드
  • 플롯 스크립트
  • 플롯 데이터
  • CPU가 장착 된 Lenovo ThinkPad P51 노트북의 Ubuntu 19.04, GCC 8.3.0에서 테스트 : Intel Core i7-7820HQ CPU (4 코어 / 8 스레드 , 2.90GHz 기본, 8MB 캐시), RAM : 2x Samsung M471A2K43BB1-CRC (2x 16GiB, 2400Mbps), SSD : Samsung MZVLB512HAJQ-000L7 (512GB, 3,000MB / s)

명확하게 :

gem5의 GCC C ++ 표준 라이브러리 삽입 벤치 마크

gem5 는 전체 시스템 시뮬레이터이므로 m5 dumpstats. 그래서 개별 삽입물의 타이밍을 추정하는 데 사용하려고했습니다.

여기에 이미지 설명 입력

해석 :

  • 힙은 여전히 일정하지만 이제 몇 줄이 있고 각 높은 줄이 더 희박하다는 것을 더 자세히 알 수 있습니다. .

    이것은 더 높고 더 높은 삽입에 대해 수행되는 메모리 액세스 대기 시간과 일치해야합니다.

  • TODO BST를 완전히 해석 할 수는 없습니다. 그렇게 대수적이고 다소 일정 해 보이지는 않습니다.

    더욱 자세히 살펴보면 몇 가지 뚜렷한 선을 볼 수 있지만 그 선이 무엇을 나타내는 지 확실하지 않습니다. 상단 하단을 삽입하기 때문에 더 얇아 지나요?

aarch64 iv에서이 Buildroot 설정 으로 벤치마킹 id = “635e322f0e”>

HPI CPU .

BST는 어레이에서 효율적으로 구현할 수 없습니다.

힙 작업은 단일 트리 분기 만 위로 또는 아래로 버블 링하면되므로 O(log(n)) 최악의 경우 스왑, O(1) 평균입니다.

BST의 균형을 유지하려면 트리 회전이 필요하며, 이는 다른 요소의 상단 요소를 변경할 수 있으며 전체 배열을 이동해야합니다 (O(n)).

힙은 배열에서 효율적으로 구현할 수 있습니다.

현재 색인에서 상위 및 하위 색인을 계산할 수 있습니다. 여기에 표시된 것처럼 .

BST와 같은 균형 조정 작업이 없습니다.

최소 삭제는 가장 걱정스러운 작업입니다. 하향식이어야합니다. 그러나 항상 여기에 설명 된대로 힙의 단일 분기를 “퍼콜 다운”하여 수행 할 수 있습니다. 힙이 항상 균형이 잘 잡혀 있기 때문에 O (log (n)) 최악의 경우가 발생합니다.

제거하는 모든 노드에 대해 단일 노드를 삽입하면 점근의 이점을 잃게됩니다. O (1) 힙이 제공하는 평균 삽입은 삭제가 지배적이며 BST를 사용할 수도 있습니다. 그러나 Dijkstra는 제거 할 때마다 노드를 여러 번 업데이트하므로 괜찮습니다.

동적 배열 힙 대 포인터 트리 힙

힙을 효율적으로 구현할 수 있습니다. 포인터 힙 위에 : https://stackoverflow.com/questions/19720438/is-it-possible-to-make-efficient-pointer-based-binary-heap-implementations

동적 배열 구현이 더 공간 효율적입니다. 각 힙 요소에 struct에 대한 포인터 만 포함되어 있다고 가정합니다.

  • 트리 구현은 각 요소에 대해 부모, 왼쪽 아이와 오른쪽 아이. 따라서 메모리 사용량은 항상 4n입니다 (트리 포인터 3 개 + struct 포인터 1 개).

    트리 BST도 마찬가지입니다. 추가 균형 정보가 필요합니다. 검은 색-적색.

  • 동적 배열 구현은 두 배가 된 직후에 2n 크기가 될 수 있습니다. 따라서 평균적으로 1.5n가됩니다.

반면 트리 힙은 최악의 경우 삽입이 더 좋습니다. 백업 동적 배열을 크기를 두 배로 복사하면 최악의 경우 O(n)가 걸리지 만 트리 힙은 각 노드에 대해 새로운 작은 할당 만 수행하기 때문입니다.

그래도 백업은 배열 배가는 O(1) 상각되므로 최대 지연 시간을 고려합니다. 여기에서 언급 .

철학

  • BST는 상위 항목과 모든 하위 항목간에 전역 속성을 유지합니다 (왼쪽은 작게, 오른쪽은 크게).

    BST의 최상위 노드는 중간 요소입니다. , 유지하려면 글로벌 지식이 필요합니다 (작고 큰 요소가 몇 개 있는지 아는 것).

    이 글로벌 속성은 유지 관리 (log n 삽입) 비용이 더 많이 들지만 더 강력한 검색 (log n 검색)을 제공합니다. .

  • 힙은 부모와 직계 자식 사이에 로컬 속성을 유지합니다 (부모> 자식).

    힙의 가장 중요한 부분은 큰 요소입니다. 유지하기 위해 지역 지식 만 필요합니다 (부모를 아는 것).

BST 대 힙 대 해시 맵 비교 :

  • BST : 다음 중 하나가 합리적 일 수 있습니다.

  • heap : 단순한 정렬 기계입니다. 가장 작은 / 가장 큰 요소 만 빠르게 확인할 수 있기 때문에 효율적인 정렬되지 않은 집합이 될 수 없습니다.

  • 해시 맵 : 효율적인 정렬 시스템이 아닌 정렬되지 않은 집합 만 가능합니다. 해싱이 순서를 뒤섞기 때문입니다.

이중 연결 목록

이중 연결 목록은 첫 번째 항목이 가장 우선 순위가 높은 힙의 하위 집합으로 볼 수 있으므로 여기에서도 비교해 보겠습니다.

  • 삽입 :
    • 위치 :
      • 이중 연결 목록 : 삽입 된 항목은 해당 요소에 대한 포인터 만 있으므로 첫 번째 또는 마지막이어야합니다.
      • 바이너리 힙 : 삽입 된 항목 모든 위치에서 끝날 수 있습니다. 연결 목록보다 덜 제한적입니다.
    • 시간 :
      • 이중 연결 목록 : O(1) 항목에 대한 포인터가 있고 업데이트가 정말 간단하기 때문에 최악의 경우
      • 바이너리 힙 : O(1) 평균, 따라서 연결 목록보다 나쁩니다. 더 일반적인 삽입 위치가 있습니다.
  • 검색 : O(n) 모두

사용 사례는 힙의 키가 현재 타임 스탬프 인 경우입니다.이 경우 새 항목은 항상 목록의 시작 부분으로 이동합니다. 따라서 정확한 타임 스탬프를 모두 잊어 버리고 목록의 위치를 우선 순위로 유지할 수 있습니다.

이는 LRU 캐시를 구현하는 데 사용할 수 있습니다. . Dijkstra와 같은 힙 애플리케이션 과 마찬가지로, 신속하게 업데이트 할 노드를 찾기 위해 키에서 목록의 해당 노드까지 추가 해시 맵을 유지해야합니다. .

다양한 Balanced BST의 비교

점근 삽입 및 찾기 지금까지 보았던 “균형 BST”로 일반적으로 분류되는 모든 데이터 구조의 시간은 동일하고 서로 다른 BBST는 서로 다른 장단점이 있습니다. 아직 완전히 연구하지는 않았지만 요약하는 것이 좋습니다. 이러한 절충점은 다음과 같습니다.

  • 빨강-검정 나무 . 2019 년 현재 가장 일반적으로 사용되는 BBST 인 것으로 보입니다. GCC 8.3.0 C ++ 구현
  • AVL 트리 에서 사용되는 것입니다. BST보다 약간 더 균형 잡힌 것처럼 보이므로 약간 더 비싼 찾기 비용으로 찾기 지연 시간이 더 나을 수 있습니다.Wiki는 다음과 같이 요약합니다. “둘 다 동일한 작업 집합을 지원하고 기본 작업에 [동일한] 시간이 걸리기 때문에 AVL 트리는 종종 빨강-검정 트리와 비교됩니다. 조회 집약적 인 애플리케이션의 경우 AVL 트리가 빨강-검정 트리보다 빠릅니다. 그들은 더 엄격하게 균형을 이룹니다. 빨강-검정 나무와 유사하게 AVL 나무는 높이 균형이 잡혀 있습니다. 일반적으로 두 가지 모두 mu < 1 / 2; 즉, 형제 노드는 매우 다른 수의 하위 항목을 가질 수 있습니다. “
  • WAVL . 원본 문서 는 재조정 및 회전 작업에 대한 경계 측면에서 해당 버전의 장점을 언급합니다.

참조

CS에 대한 유사한 질문 : 무엇 ‘ 이진 검색 트리와 이진 힙의 차이점은 무엇입니까?

댓글

  • 좋은 답변 . 힙의 일반적인 응용 프로그램은 중앙값, k min, 상위 k 요소입니다. 이러한 가장 일반적인 작업의 경우 min을 제거한 다음 삽입합니다 (일반적으로 순수 삽입 작업이 거의없는 작은 힙이 있음). 따라서 실제로는 이러한 알고리즘의 경우 BST를 능가하지 않습니다.
  • 예외 답변 !!! deque를 기본 힙 구조로 사용하면 크기 조정 시간을 크게 줄일 수 있지만 청크에 대한 포인터 배열을 (더 작은) 재 할당해야하므로 최악의 경우가 여전히 O (n)입니다.

답변

바이너리 검색 트리 및 바이너리 힙 은 트리 기반 데이터 구조입니다.

힙은 노드가 자식보다 우선 순위를 갖도록 요구합니다. 최대 힙에서 각 노드의 하위는 자체보다 작아야합니다. 이는 최소 힙의 반대입니다.

바이너리 최대 힙

바이너리 검색 트리 (BST)는 형제 노드간에 특정 순서 (선주문, 순서, 후 주문)를 따릅니다. 트리는 반드시 정렬 :

바이너리 검색 트리

BST는 평균 $ O (\ log n) $ 삽입, 삭제 및 검색.
바이너리 힙은 평균 $ O (1) $ findMin / findMax 및 $ O (\ log n) $ 삽입 및 삭제

댓글

  • @FrankW Extraction is $ O (\ log n) $, no?

Answer

데이터 구조를 사용하여 관심 수준을 구분해야합니다.

  1. 이 q의 추상 데이터 구조 (저장된 개체, 해당 작업) 사용이 다릅니다. 하나는 우선 순위 큐를 구현하고 다른 하나는 세트를 구현합니다. 우선 순위 큐는 임의의 요소를 찾는 데 관심이 없으며 우선 순위가 가장 큰 요소 만 찾습니다.

  2. 구조의 구체적인 구현 . 첫눈에 둘 다 (이진) 나무이지만 구조적 특성이 다릅니다. 키의 상대적인 순서와 가능한 전역 구조가 모두 다릅니다. (다소 부정확합니다. BST 키는 왼쪽에서 오른쪽으로 정렬되고 힙에서는 하향식으로 정렬됩니다.) IPlant가 올바르게 설명하므로 힙도 “완전”해야합니다. .

  3. 낮은 수준 구현 에는 마지막 차이가 있습니다. (불균형) 이진 검색 트리에는 포인터를 사용하는 표준 구현이 있습니다. 반대로 바이너리 힙은 배열을 사용하여 효율적으로 구현합니다 (정확히 제한된 구조로 인해).

Answer

이전 답변 위에 힙에는 힙 구조 속성이 있어야합니다. ; 트리는 가득 차 있어야하며 항상 가득 차있을 수없는 맨 아래 레이어는 간격없이 맨 왼쪽에서 맨 오른쪽까지 채워야합니다.

답글 남기기

이메일 주소를 발행하지 않을 것입니다. 필수 항목은 *(으)로 표시합니다