1. 이진 나무에 대해 이야기해야합니다
힙을 이해하려면 먼저 이진 트리를 이해해야합니다. 컴퓨터 과학에서 이진 트리는 노드 당 최대 두 개의 하위 트리가있는 트리 구조입니다. 일반적으로 하위 트리를 "왼쪽 하위 트리"및 "오른쪽 하위 트리"라고합니다. 이진 트리는 종종 이진 검색 트리와 이진 힙을 구현하는 데 사용됩니다.
이진 트리의 각 노드는 최대 두 개의 하위 트리 (2도보다 큰 노드)를 가지고 있습니다. 이진 트리의 하위 트리는 왼쪽과 오른쪽으로 나눌 수 있으며 순서를 되돌릴 수 없습니다. 이진 트리의 I -th 층은 최대 2i -1 노드를 갖습니다. 깊이가있는 이진 트리는 최대 2k -1 노드입니다. 이진 트리 T의 경우, 터미널 노드의 수가 N0이고 2 도의 노드 수는 N2, N0 = N2 + 1 인 경우.
나무와 이진 트리 사이에는 세 가지 주요 차이점이 있습니다.
트리의 노드 수는 1 이상이고 이진 트리의 노드 수는 0 일 수 있습니다.
트리의 최대 노드도에는 제한이없고 이진 트리의 최대 노드는 2입니다.
트리 노드에는 왼쪽과 오른쪽 사이에 차이가 없지만 이진 트리의 노드에는 왼쪽과 오른쪽 사이에 차이가 없습니다.
이진 나무는 완전한 이진 나무와 가득한 이진 나무로 나뉩니다.
전체 바이너리 트리 : 깊이가있는 나무와 2k -1 노드가있는 트리를 전체 바이너리 트리라고합니다.
(깊이가있는 전체 바이너리 트리 3)
완전한 이진 트리 : 깊이 k 인 노드가있는 이진 트리. 각 노드가 깊이 k를 갖는 전체 바이너리 트리에서 순서 번호 1 내지 n의 노드에 해당하는 경우에만 완전한 이진 트리라고합니다.
(깊이가있는 전체 바이너리 트리 3)
2. 힙은 무엇입니까?
힙 (이진 힙)은 완전한 이진 트리로 간주 될 수 있습니다. 완전한 바이너리 트리의 "우수한"속성은 하단 층을 제외하고 각 층이 가득 차서 힙을 배열로 표현할 수있게한다는 것입니다 (일반 일반 바이너리 트리는 일반적으로 링크 된 목록으로 표시됩니다). 각 노드는 배열의 요소에 해당합니다.
다음 그림은 힙과 어레이의 관계를 보여줍니다.
(힙과 어레이의 관계)
노드의 지정된 첨자 i의 경우,이 노드의 상위 노드 및 하위 노드의 첨자에 대해 쉽게 계산할 수 있습니다.
부모 (i) = 바닥 (i/2), I의 상위 노드 첨자
왼쪽 (i) = 2i, 왼쪽 자식 노드 첨자 i
오른쪽 (i) = 2i + 1, 오른쪽 하위 노드 첨자 i
이진 힙에는 일반적으로 두 가지 유형의 이진 힙이 있습니다 : 가장 큰 힙과 가장 작은 힙.
최대 힙 :
최대 힙의 최대 요소 값은 루트 노드 (더미 상단)에 나타납니다.
힙 내 각 상위 노드의 요소 값은 자식 노드보다 크거나 동일합니다 (존재하는 경우)
(최대 힙)
최소 힙 :
최소 힙의 최소 요소 값은 루트 노드 (힙 상단)에 나타납니다.
힙 내 각 상위 노드의 요소 값은 하위 노드보다 작거나 동일합니다 (존재하는 경우)
(최소 스택)
3. 힙 분류의 원리
힙 분류는 최대 힙 상단에서 최대 수를 꺼내고 나머지 힙을 최대 힙으로 계속 조정하고 힙 상단에서 다시 최대 수를 꺼내는 것입니다. 이 프로세스는 나머지 숫자가 하나만있을 때까지 계속됩니다. 힙에서 다음 작업을 정의하십시오.
Max-Heapify : 힙의 끝 노드를 조정하여 자식 노드가 항상 상위 노드보다 작습니다.
최대 힙 생성 (빌드-맥스-히피) : 힙의 모든 데이터를 최대 힙으로 만들어
힙-소트 : 첫 번째 데이터의 루트 노드를 제거하고 최대 힙 조정의 재귀 작업을 수행합니다.
다음 논의를 계속하기 전에 주목해야 할 한 가지 문제는 다음과 같습니다. 배열은 모두 0 기반이므로 힙 데이터 구조 모델이 변경 될 것입니다.
(제로 기반)
이에 따라 여러 계산 공식을 조정해야합니다.
부모 (i) = 바닥 ((i-1)/2), I의 부모 노드 첨자
왼쪽 (i) = 2i + 1, 왼쪽 자식 노드 첨자 i의
오른쪽 (i) = 2 (i + 1), i의 오른쪽 자식 노드 첨자
Max 힙 조정 (MaxHeapify)의 기능은 가장 큰 힙의 특성을 유지하는 것이며 가장 큰 힙을 만드는 핵심 서브 루틴입니다. 작동 프로세스는 그림에 표시됩니다.
(Max-Heapify)
한 번의 조정 후 힙은 여전히 힙 특성을 위반하기 때문에 전체 힙이 힙 특성을 충족시키기 위해 재귀 테스트가 필요합니다. JavaScript로 다음과 같이 표현할 수 있습니다.
/** * 인덱스에서 확인하고 최대 힙 속성을 유지하고 유지 관리 * * @Array * * @Index 체크의 시작 색인 * * @eapsize 힙 크기 * **/function maxHeapify (배열, 인덱스, heapsize) {var imax = index, ileft = 2 * index + 1, iright = 2 * (색인 + 1); if (ileft <heapsize && array [index] <array [ileft]) {imax = ileft; } if (iright <heapsize && array [imax] <배열 [iright]) {imax = iright; } if (imax! = index) {Swap (Array, Imax, Index); MaxHeapify (배열, IMAX, 힙 화); // 재귀 조정}} 함수 스왑 (배열, i, j) {var temp = 배열 [i]; 배열 [i] = 배열 [j]; 배열 [j] = temp;}일반적으로, 재귀는 주로 분열 및 치료 방법에 사용되며, 여기서는 분열 및 치료가 필요하지 않습니다. 또한 재귀 통화에는 스택 프레스/청소가 필요하며, 이는 반복에 비해 성능에 약간의 불이익이 있습니다. 물론 이것은 20/80 규칙에 따라 무시할 수 있습니다. 그러나 재귀를 사용하는 것이 불편하다고 생각되면 다음과 같은 반복을 사용할 수도 있습니다.
/** * 색인에서 확인하고 최대 힙 속성을 유지하고 유지 관리 * * @array * * @index check * * @eapsize 힙 크기 * **/function maxHeapify (배열, 인덱스, 인용) {var imax, ileft, iright; while (true) {imax = index; Ileft = 2 * index + 1; iright = 2 * (색인 + 1); if (ileft <heapsize && array [index] <array [ileft]) {imax = ileft; } if (iright <heapsize && array [imax] <배열 [iright]) {imax = iright; } if (imax! = index) {Swap (Array, Imax, Index); 색인 = IMAX; } else {break; }}} 함수 스왑 (Array, I, J) {var temp = 배열 [i]; 배열 [i] = 배열 [j]; 배열 [j] = temp;}최대 힙을 만드는 목적 (Build-Max-Heap)은 배열을 최대 힙으로 변환하여 배열과 힙 크기의 두 매개 변수를 수용하는 것입니다. Build-Max-Heap은 배열을 변환하고 최대 힙을 구축하기 위해 Max-Heapify를 호출합니다. Max-Heapify는 구독 후 노드가 가장 큰 힙의 속성을 충족하도록 보장 할 수 있기 때문에 Max-Heapify의 상향식 호출은 변환 프로세스 중에이 속성을 유지할 수 있습니다. 최대 힙 번호 요소가 N 인 경우, Build-Max-Heap은 부모 (n)의 순서대로 max-heapify를 호출합니다. 프로세스는 다음과 같습니다.
설명은 JavaScript의 다음과 같습니다.
함수 buildMaxHeap (배열, 힙 화) {var i, iparent = math.floor ((Heapsize -1) / 2); for (i = iparent; i> = 0; i-) {maxHeapify (배열, i, heapsize); }}Heap-Sort는 힙 분류를위한 인터페이스 알고리즘입니다. 힙-소트는 먼저 Build-Max-Heap을 호출하여 배열을 최대 힙으로 변환 한 다음 힙의 상단 및 하단 요소를 교환 한 다음 바닥을 상승시킨 다음 Max-Heapify를 호출하여 최대 힙 속성을 유지합니다. 힙의 최상위 요소는 힙에서 가장 큰 요소 여야하므로, 한 번의 작업 후에, 힙에 존재하는 가장 큰 요소는 힙으로부터 힙으로부터 분리되고, 반복 된 N-1 번 후에 배열이 배열된다. 전체 프로세스는 다음과 같습니다.
설명은 JavaScript의 다음과 같습니다.
함수 heapSort (배열, 힙 화) {buildMaxHeap (배열, 힙 화); for (int i = heapsize-1; i> 0; i-) {스왑 (Array, 0, i); MaxHeapify (배열, 0, i); }}4. JavaScript 언어 구현
마지막으로 위의 위를 다음과 같이 완전한 JavaScript 코드로 구성하십시오.
함수 Heapsort (Array) {함수 스왑 (Array, I, J) {var temp = 배열 [i]; 배열 [i] = 배열 [j]; 배열 [j] = 온도; } 함수 maxHeApify (배열, 인덱스, heapSize) {var imax, ilft, iright; while (true) {imax = index; Ileft = 2 * index + 1; iright = 2 * (색인 + 1); if (ileft <heapsize && array [index] <array [ileft]) {imax = ileft; } if (iright <heapsize && array [imax] <배열 [iright]) {imax = iright; } if (imax! = index) {Swap (Array, Imax, Index); 색인 = IMAX; } else {break; }}} 함수 buildMaxHeap (Array) {var i, iparent = math.floor (array.length / 2) -1; for (i = iparent; i> = 0; i-) {maxHeapify (Array, i, array.length); }} 함수 정렬 (배열) {buildMaxHeap (배열); for (var i = array.length-1; i> 0; i-) {Swap (Array, 0, i); MaxHeapify (배열, 0, i); } 반환 배열; } return sort (배열);}5. 힙 분류 알고리즘의 적용
(1) 알고리즘 성능/복잡성
힙 정렬의 시간 복잡성은 매우 안정적이며 (입력 데이터에 민감하지 않다는 것을 알 수 있으며) O (NN) 복잡성이므로 가장 좋은 경우는 최악의 경우와 동일합니다.
그러나 공간 복잡성은 구현에 따라 다릅니다. 상기는 두 가지 일반적인 복잡성에 대해 설명합니다 : O (n)과 O (1). 공간을 절약하는 원칙에 따라 O (1) 복잡성 방법을 권장합니다.
(2) 알고리즘 안정성
힙 분류에는 많은 필터링 및 이동 프로세스가 있으며 불안정한 정렬 알고리즘에 속합니다.
(3) 알고리즘 적용 가능한 시나리오
힙 분류는 힙을 구축하고 힙을 조정하는 과정에서 비교적 큰 오버 헤드가 발생하며 요소가 거의 없을 때 적용 할 수 없습니다. 그러나 많은 요소가있을 때 여전히 좋은 선택입니다. 특히 "Top N Large의 수"와 같은 문제를 해결할 때는 거의 선호되는 알고리즘입니다.