[algorithm] 힙 대 이진 검색 트리 (BST)

요약

          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 == 균형이 잡힌 BST
• **:이 답변에 설명 된 사소한 수정 사용
• ***: log(n)포인터 트리 힙, n동적 배열 힙

BST에 비해 이진 힙의 장점

• 이진 힙으로의 평균 삽입 시간 O(1)은 BST입니다 O(log(n)). 이것이 힙의 킬러 기능입니다.

  피보나치 힙O(1) 과 같은 상각 (더 강한)에 도달하는 다른 힙도 있지만 Brodal 큐 와 같은 최악의 경우도 있습니다.

• 이진 힙은 동적 배열 또는 포인터 기반 트리 (BST 만 포인터 기반 트리) 위에 효율적으로 구현 될 수 있습니다 . 따라서 힙의 경우 가끔 크기 조정 대기 시간을 줄 수있는 경우보다 공간 효율적인 배열 구현을 선택할 수 있습니다.

• 이진 힙 생성 이다 O(n)최악의 경우 , O(n log(n))BST합니다.

이진 힙에 비해 BST의 장점

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

  힙의 O(n)경우 가장 큰 요소 인를 제외하고 일반적으로입니다 O(1).

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

• 힙은 O(1)max, BST를 찾는 것 O(log(n))입니다.

  가장 큰 요소를 추적하기 위해 BST를 수정하고 해당 요소가 변경 될 수있을 때마다 업데이트하는 것이 쉽지 않기 때문에 이것은 일반적인 오해입니다. 바이너리 검색 트리를 사용하여 힙 작업을 시뮬레이션 할 수 있습니까? (한 여진에 의해 ).

  실제로 이것은 BST와 비교할 때 힙 의 한계 입니다. 유일한 효율적인 검색은 가장 큰 요소에 대한 것입니다.

평균 이진 힙 삽입은 O(1)

출처 :

• 논문 : http://i.stanford.edu/pub/cstr/reports/cs/tr/74/460/CS-TR-74-460.pdf
• WSU 슬라이드 : http://www.eecs.wsu.edu/~holder/courses/CptS223/spr09/slides/heaps.pdf

직관적 인 주장 :

• 최하위 트리 레벨은 최상위 레벨보다 기하 급수적으로 더 많은 요소를 가지므로 새로운 요소는 거의 최하단에 갈 것입니다
• 힙 삽입 은 하단 에서 시작하고 BST는 상단에서 시작해야합니다.

이진 힙에서 주어진 인덱스에서 값을 증가시키는 것도 O(1)같은 이유입니다. 그러나 그렇게하려면 힙 작업에 대한 추가 인덱스를 최신 상태로 유지하고 싶을 것 입니다. 최소 힙 기반 우선 순위 대기열에 대해 O (로그온) 감소 키 작업을 구현하는 방법은 무엇입니까? 예를 들어 Dijkstra. 추가 비용없이 가능합니다.

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

삽입 시간에 대해 올바른지 확인하기 위해 C ++ std::set( Red-black tree BST ) 및 std::priority_queue( dynamic array heap ) 삽입을 벤치마킹했으며 이것이 내가 얻은 것입니다.

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

그래서 분명히 :

• 힙 삽입 시간은 기본적으로 일정합니다.

  동적 배열 크기 조정 지점을 명확하게 볼 수 있습니다. 모든 시스템 노이즈에서 무엇이든 볼 수 있도록 10k 삽입마다 평균을 계산하기 때문에 이러한 피크는 실제로 그림보다 약 10k 배 더 큽니다!

  확대 된 그래프는 본질적으로 어레이 크기 조정 포인트 만 제외하고 거의 모든 인서트가 25 나노초 미만임을 나타냅니다.

• BST는 로그입니다. 모든 인서트는 평균 힙 인서트보다 훨씬 느립니다.

• BST 대 hashmap 자세한 분석 : C ++의 std :: map 안에 어떤 데이터 구조가 있습니까?

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

gem5 는 전체 시스템 시뮬레이터이므로로 정확한 무한 시계를 제공합니다 m5 dumpstats. 그래서 개별 인서트의 타이밍을 추정하는 데 사용하려고했습니다.

해석:

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

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

• TODO 나는 BST가 대수적이고 다소 일정하게 보이지 않기 때문에 BST를 완전히 해석 할 수는 없습니다.

  그러나이 세부 사항을 통해 몇 가지 뚜렷한 선을 볼 수도 있지만 그 선이 무엇인지 잘 모르겠습니다. 상단을 삽입하므로 하단 선이 더 얇을 것으로 예상됩니까?

aarch64 HPI CPU 에서이 Buildroot 설정 으로 벤치마킹했습니다 .

어레이에서 BST를 효율적으로 구현할 수 없음

힙 작업은 단일 트리 분기 만 버블 업하거나 다운해야하므로 O(log(n))최악의 경우 스왑이 O(1)평균입니다.

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

어레이에서 힙을 효율적으로 구현할 수 있습니다

부모 및 자식 인덱스는 여기에 표시된 것처럼 현재 인덱스에서 계산할 수 있습니다 .

BST와 같은 밸런싱 작업이 없습니다.

삭제 작업은 하향식이므로 가장 걱정되는 작업입니다. 그러나 여기에 설명 된대로 항상 힙의 단일 분기를 “통과”하여 수행 할 수 있습니다 . 힙은 항상 균형이 잘 잡히므로 O (log (n)) 최악의 경우가 발생합니다.

제거 할 때마다 단일 노드를 삽입하는 경우 힙이 삭제 한대로 제공하는 점근 적 O (1) 평균 삽입의 이점을 잃어 BST를 사용할 수도 있습니다. 그러나 Dijkstra는 제거 할 때마다 노드를 여러 번 업데이트하므로 괜찮습니다.

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

포인터 힙 위에 힙을 효율적으로 구현할 수 있습니다. 포인터 기반 이진 힙을 효율적으로 구현할 수 있습니까?

동적 배열 구현은보다 공간 효율적입니다. 각 힙 요소에 다음에 대한 포인터 만 포함되어 있다고 가정하십시오 struct.

• 트리 구현은 각 요소에 대해 부모, 왼쪽 자식 및 오른쪽 자식의 세 가지 포인터를 저장해야합니다. 따라서 메모리 사용량은 항상 4n(3 트리 포인터 + 1 struct포인터)입니다.

  트리 BST는 블랙-레드-니스와 같은 추가 밸런싱 정보도 필요합니다.

• 동적 배열 구현은 2n배가 된 직후 의 크기 일 수 있습니다 . 따라서 평균적으로는입니다 1.5n.

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

그럼에도 불구하고 배킹 어레이 배가는 O(1)상각되므로 최대 대기 시간 고려 사항이 적용됩니다. 여기에 언급했습니다 .

철학

• BST는 부모와 모든 자손 사이의 전역 속성을 유지합니다 (왼쪽이 작고 오른쪽이 더 큼).

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

  이 전역 속성은 유지 관리하는 데 비용이 많이 들지만 (log n insert) 더 강력한 검색 (log n search)을 제공합니다.

• 힙은 부모와 직계 자녀 (부모> 자녀) 사이의 지역 재산을 유지합니다.

  힙의 최상위 노드는 큰 요소이며, 유지하기 위해 로컬 지식 만 있으면됩니다 (부모를 알고 있음).

BST 대 힙 대 해시 맵 비교 :

• BST : 다음 중 하나 일 수 있습니다.

  • 비 순차 세트 (요소가 이전에 삽입되었는지 여부를 결정하는 구조) 그러나 해시 맵은 O (1) 상각 삽입으로 인해 더 나은 경향이 있습니다.
  • 선별기. 그러나 힙이 일반적으로 더 낫기 때문에 힙 정렬 이 트리 정렬 보다 훨씬 널리 알려져 있습니다.

• 힙 : 그냥 정렬 기계입니다. 가장 작거나 큰 요소 만 빠르게 확인할 수 있기 때문에 효율적으로 정렬되지 않은 집합이 될 수 없습니다.

• 해시 맵 : 해싱이 모든 순서를 혼합하기 때문에 효율적인 정렬 기계가 아닌 정렬되지 않은 세트 만 될 수 있습니다.

이중 연결 목록

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

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

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

이것은 LRU 캐시 를 구현하는 데 사용될 수 있습니다 . 마찬가지로 익스트라 같은 힙 애플리케이션에 신속하게 업데이트 할 노드 찾기 위해 목록의 해당 노드로 키에서 추가 해시 맵을 유지하기를 원할 것입니다.

다른 균형 BST의 비교

지금까지 본 “균형 BST”로 분류되는 모든 데이터 구조에 대한 점근 적 삽입 및 찾기 시간은 동일하지만 BBST마다 서로 다른 절충점이 있습니다. 나는 이것을 완전히 연구하지는 않았지만 여기에 다음과 같은 절충점을 요약하는 것이 좋습니다.

• 레드 블랙 트리 . 2019 년 현재 가장 일반적으로 사용되는 BBST 인 것처럼 보입니다 (예 : GCC 8.3.0 C ++ 구현에서 사용되는 것임).
• AVL 트리 . BST보다 약간 균형이 잡힌 것으로 보이므로 약간 더 비싼 찾기 비용으로 찾기 지연 시간이 더 나을 수 있습니다. Wiki 요약 : “AVL 트리는 종종 동일한 작업 집합을 지원하고 기본 작업에 [동일한] 시간이 걸리기 때문에 종종 레드-블랙 트리와 비교됩니다. 조회 집약적 인 애플리케이션의 경우 AVL 트리는 레드-블랙 트리보다 빠릅니다. 빨강-검정색 나무와 유사하게 AVL 나무는 높이가 균형을 이룹니다. 일반적으로 mu <1/2의 무게 균형이나 균형이 맞지 않습니다. 즉, 형제 노드는 엄청나게 클 수 있습니다. 다른 수의 자손. “
• WAVL . 원래의 논문은 재조정 및 회전 작업에 대한 경계의 측면에서 해당 버전의 장점을 언급하고있다.

또한보십시오

CS에 대한 비슷한 질문 : /cs/27860/whats-the-difference-between-a-binary-search-tree-and-a-binary-heap

---

답변