지금 알고리즘 클래스에서 힙에 대해 배우고 실제로 최대 힙이 어떻게 헤드 포인터에 최대 값을 저장하는 연결 목록보다 나은지 이해할 수 없습니다.maxheap과 max at head를 저장하는 링크드 목록의 차이점은 무엇입니까?
노드가 두 개 미만의 하위 노드를 갖는 점은 무엇입니까? 링크 된 목록과 같은 노드를 하나만 가질 수없는 이유는 무엇입니까? 기본적으로 힙 (heap)은 연결된 목록에서 수행 할 수없는 작업은 무엇입니까? 나는 근본적인 무언가를 놓치고있는 것처럼 느낀다.
최대 바이너리 힙은 O(n) 시간에 생성 될 수 있으며 각 추출 - 최대 값은 O(lg n) 시간이 걸릴 것입니다. 단일 링크리스트를 만들면 데이터를 정렬해야하는데, 이는 O(n * lg n) 시간이 걸린다는 것을 의미하지만, 추출 - 최대는 일정 시간 동안 O(1)이 될 것입니다. build-heap 다음에 nextract-max es가 나오면 바로 표준 힙 코드 알고리즘입니다. 기존 데이터 구조에 삽입 값을 필요로 할 때
O(lg n) 시간이 걸리는 반면, 링크 된 목록에 항목을 삽입 할 때는 적절한 위치 인
O(n) 시간을 찾아야합니다.
O(n)은 O(lg n)보다 상당히 느립니다. 예를 들어, 정렬 된 연결 목록에 100 만 개의 기존 항목이있는 경우 항목 하나를 삽입 할 때 연결 항목 목록에 삽입하는 데 1000 배의 시간이 걸릴 수 있습니다. 그러나 백만 항목의 힙에 항목을 삽입하는 것은 수천 개의 항목을 힙에 삽입하는 것보다 2 배 정도 빠릅니다.
둘 다 Priority queue 추상 데이터 유형의 구현입니다. 차이점은 성능에 있습니다. 항목을 삽입하거나 제거하는 데 걸리는 시간입니다.
우선 순위 큐를 단순한 순서없는 연결 목록으로 구현할 수 있습니다. 항목을 추가 할 때마다 목록의 새로운 머리글로 만듭니다. 누군가가 최대 항목을 요청하면 가장 큰 항목을 찾아 목록에서 제거한 다음 반환합니다. 따라서 삽입은 매우 빠르며 최대 항목을 얻으려면 매번 목록을 전체 검사해야합니다.
정렬 된 목록을 유지 관리 할 수도 있습니다. 이 경우 새 항목을 삽입 할 위치를 찾기 위해 순차적으로 목록을 검색해야하기 때문에 항목을 삽입하는 것이 비용이 많이 듭니다. 그러나 최대 항목을 얻는 것은 매우 빠릅니다. 목록 맨 앞에 있습니다.
그러나 백만 개의 항목이있는 목록이 있다고 가정 해보십시오. 첫 번째 경우 최대 항목을 찾으려면 전체 목록을 검색해야합니다. 두 번째 경우에는 항목을 삽입 할 때 평균적으로 목록의 절반을 검색해야합니다.
최대 힙은 다른 한편으로는 절충안입니다. 정렬되지 않은 목록만큼 빨리 삽입되지는 않으며 정렬 된 목록만큼 빨리 제거되지 않습니다. 그러나 은 많은 경우보다 더 빠르며 은 많은 경우 삽입시 정렬 된 목록보다 빠릅니다.
Insert Delete-Max
Unordered list O(1) O(n)
Sorted list O(n) O(1)
Binary max heap O(log n) O(log n)
당신의 우선 순위 큐가 1,000,000 항목이 있음을 다시 상상 : 나는 아래
은 우선 순위 큐의 세 가지 유형의 두 가지 기본 작업의 점근 적 복잡성을 나열합니다.항목을 추가 한 다음 최대 값을 제거하려고합니다. 정렬되지 않은 목록은 항목을 삽입하는 데 단 한 번의 빠른 작업이 필요하며 최대 1,000,000 개의 항목을 검색해야합니다.
정렬 된 목록은 항목을 삽입하는 데 평균 50 만 건의 작업이 소요되지만 최대 항목은 매우 빠르게 제거 할 수 있습니다.
로그 (1000000)은 약 20입니다. 최대 힙에는 항목을 삽입 할 때 최대 20 개의 작업이 필요하며 항목을 제거하는 데는 최대 20 개의 작업이 필요합니다.
우선 순위 큐를 유지해야하는 경우 링크 된 목록보다 최대 힙이 훨씬 효율적임을 분명히해야합니다.
데이터가 이미 정렬되어 있고 순서대로 처리해야하는 경우에는 물론 힙이 필요하지 않습니다. 연결된 목록이 필요하지 않습니다. 배열은 갈 길입니다. 그러나 추가 및 제거가 혼합 된 경우 힙을 유지하면 성능이 훨씬 향상됩니다.
매우 작은 대기열 (예 : 10 개 항목)을 유지하더라도 연결된 목록과 최대 힙 간의 성능 차이가 매우 뚜렷합니다. 응용 프로그램의 성능이 우선 순위 큐 구현의 속도에 좌우되는 경우 힙 데이터 구조를 이해하는 데 시간을 할애 할 가치가 있습니다.
자세한 내용은 Priority queues 및 Heaps의 블로그 항목 및 구현에 대해 설명하는 후속 기사를 참조하십시오.