Heap Sort 힙 정렬 알고리즘 및 JavaScript 코드 구현에 대한 자세한 그래픽 설명_기본 지식

1. 이진 트리에 대해 이야기해야 합니다
힙을 이해하려면 먼저 이진 트리를 이해해야 합니다. 컴퓨터 과학에서 이진 트리는 각 노드에 최대 2개의 하위 트리가 있는 트리 구조입니다. 일반적으로 하위 트리를 "왼쪽 하위 트리" 및 "오른쪽 하위 트리"라고 합니다. 이진 트리는 이진 검색 트리와 이진 힙을 구현하는 데 자주 사용됩니다.
이진 트리의 각 노드에는 최대 2개의 하위 트리가 있습니다(2보다 큰 차수를 갖는 노드는 없습니다). 이진 트리의 하위 트리는 왼쪽 하위 트리와 오른쪽 하위 트리로 나뉘며 순서는 바뀔 수 없습니다. 이진 트리의 i번째 수준에는 최대 2i - 1개의 노드가 있습니다. 깊이 k를 갖는 이진 트리는 임의의 이진 트리 T에 대해 최대 2k - 1개의 노드를 갖습니다. 2차는 n2이고 n0 = n2 + 1입니다.
트리와 이진 트리의 세 가지 주요 차이점:
트리의 노드 수는 1 이상이어야 하며 이진 트리의 노드 수는 0이 될 수 있습니다
트리의 노드 최대 차수에는 제한이 없지만 이진 트리의 노드 최대 차수는 2입니다.
트리의 노드는 왼쪽과 오른쪽으로 구분되지 않지만 이진 트리의 노드는 왼쪽과 오른쪽으로 구분됩니다
이진 트리는 완전 이진 트리와 완전 이진 트리로 구분됩니다
완전 이진 트리: 깊이가 k이고 2k - 1개의 노드를 갖는 트리를 완전 이진 트리라고 합니다

(깊이 3의 완전 이진 트리)
완전 이진 트리: 깊이 k와 n 노드가 있는 이진 트리입니다. 각 노드가 깊이 k인 전체 이진 트리에서 1부터 n까지의 노드에 해당하는 경우에만 이를 완전 이진 트리라고 합니다

(깊이 3의 완전 이진 트리)
2. 힙이란 무엇인가요?
힙(이진 힙)은 완전한 이진 트리로 간주될 수 있습니다. 완전한 이진 트리의 "탁월한" 속성은 가장 낮은 수준을 제외한 모든 수준이 가득 차서 힙이 배열을 사용하여 표현(일반)할 수 있다는 것입니다. 이진 트리는 일반적으로 기본 컨테이너로 연결된 목록으로 표시되며 각 노드는 배열의 요소에 해당합니다.
아래와 같이 힙과 배열의 관계입니다

(힙과 배열의 상호관계)
노드의 주어진 첨자 i에 대해 이 노드의 상위 노드와 하위 노드의 첨자는 쉽게 계산될 수 있습니다.
Parent(i) = Floor(i/2), i의 부모 노드 첨자
Left(i) = 2i, i의 왼쪽 첨자
Right(i) = 2i + 1, i의 오른쪽 자식 노드 첨자

바이너리 힙은 일반적으로 최대 힙과 최소 힙의 두 가지 유형으로 나뉩니다.
최대 힙:
최대 힙의 최대 요소 값은 루트 노드(힙 상단)에 나타납니다.
힙에 있는 각 상위 노드의 요소 값은 해당 하위 노드(존재하는 경우)보다 크거나 같습니다.

(최대 힙)
최소 힙:
최소 힙에서 가장 작은 요소 값이 루트 노드(힙의 상단)에 나타납니다.
힙에 있는 각 상위 노드의 요소 값은 해당 하위 노드(존재하는 경우)보다 작거나 같습니다.

(최소 힙)
3.힙 정렬 원리
힙 정렬은 최대 힙의 상단에서 최대 개수를 꺼내고, 계속해서 남은 힙을 최대 힙으로 조정하고, 다시 힙 상단의 최대 개수를 꺼내는 과정입니다. 남은 숫자는 단 하나뿐이다. 힙에서 다음 작업을 정의합니다.
Max-Heapify: 하위 노드가 항상 상위 노드보다 작도록 힙의 끝 하위 노드를 조정합니다.
최대 힙 생성(Build-Max-Heap): 힙의 모든 데이터를 재정렬하여 최대 힙으로 만듭니다.
힙 정렬: 첫 번째 데이터의 루트 노드를 제거하고 최대 힙 조정의 재귀 연산을 수행합니다
다음 논의를 계속하기 전에 주목해야 할 한 가지는 배열이 모두 0 기반이라는 것입니다. 즉, 힙 데이터 구조 모델이 변경된다는 의미입니다.

(0 기반)
이에 따라 여러 계산 공식도 그에 따라 조정되어야 합니다.
Parent(i) = Floor((i-1)/2), i의 상위 노드 첨자
Left(i) = 2i + 1, i의 왼쪽 자식 노드의 첨자
Right(i) = 2(i + 1), i의 오른쪽 자식 노드 첨자
최대 힙 조정(MAX-HEAPIFY) 함수는 최대 힙의 속성을 유지하는 것이며 최대 힙을 생성하는 핵심 서브루틴입니다. 함수 프로세스는 그림과 같습니다.

(최대-힙파이)
한 번의 조정 후에도 힙이 여전히 힙 속성을 위반하므로 전체 힙이 힙 속성을 충족하도록 하려면 재귀 테스트가 필요합니다. 이는 JavaScript로 다음과 같이 표현할 수 있습니다.

/**
 * 从 index 开始检查并保持最大堆性质
 *
 * @array
 *
 * @index 检查的起始下标
 *
 * @heapSize 堆大小
 *
 **/
function maxHeapify(array, index, heapSize) {
 var iMax = index,
   iLeft = 2 * index + 1,
   iRight = 2 * (index + 1);

 if (iLeft < heapSize && array[index] < array[iLeft]) {
  iMax = iLeft;
 }

 if (iRight < heapSize && array[iMax] < array[iRight]) {
  iMax = iRight;
 }

 if (iMax != index) {
  swap(array, iMax, index);
  maxHeapify(array, iMax, heapSize); // 递归调整
 }
}

function swap(array, i, j) {
 var temp = array[i];
 array[i] = array[j];
 array[j] = temp;
}

일반적으로 재귀는 분할 정복 방식에서 주로 사용되지만 여기서는 분할 정복이 필요하지 않습니다. 더욱이 재귀 호출에는 스택을 밀어넣거나 지우는 작업이 필요하며 이는 반복에 비해 약간의 성능 단점이 있습니다. 물론 20/80 규칙에 따르면 이는 무시될 수 있습니다. 하지만 재귀를 사용하는 것이 불편하다고 생각되면 다음과 같이 반복을 사용할 수도 있습니다.

/**
 * 从 index 开始检查并保持最大堆性质
 *
 * @array
 *
 * @index 检查的起始下标
 *
 * @heapSize 堆大小
 *
 **/
function maxHeapify(array, index, heapSize) {
 var iMax, iLeft, iRight;
 while (true) {
  iMax = index;
  iLeft = 2 * index + 1;
  iRight = 2 * (index + 1);
  if (iLeft < heapSize && array[index] < array[iLeft]) {
   iMax = iLeft;
  }

  if (iRight < heapSize && array[iMax] < array[iRight]) {
   iMax = iRight;
  }

  if (iMax != index) {
   swap(array, iMax, index);
   index = iMax;
  } else {
   break;
  }
 }
}

function swap(array, i, j) {
 var temp = array[i];
 array[i] = array[j];
 array[j] = temp;
}

최대 힙을 생성하는 기능(Build-Max-Heap)은 배열을 최대 힙으로 변환하는 것입니다. 이 함수는 배열과 힙 크기라는 두 가지 매개변수를 허용합니다. Build-Max-Heap은 아래쪽에서 Max-Heapify를 호출합니다. top 배열을 변환하고 최대 힙을 생성합니다. Max-Heapify는 첨자 i가 있는 노드 뒤의 노드가 최대 힙 속성을 충족하는지 확인하기 때문에 Max-Heapify를 호출하는 상향식 호출은 변환 프로세스 중에 이 속성을 유지할 수 있습니다. 최대 힙의 요소 수가 n이면 Build-Max-Heap은 Parent(n)에서 시작하여 Max-Heapify를 위쪽으로 호출합니다. 진행과정은 다음과 같습니다.

JavaScript로 설명하면 다음과 같습니다.

function buildMaxHeap(array, heapSize) {
 var i,
   iParent = Math.floor((heapSize - 1) / 2);
   
 for (i = iParent; i >= 0; i--) {
  maxHeapify(array, i, heapSize);
 }
}

Heap-Sort는 힙 정렬의 인터페이스 알고리즘입니다. 먼저 Build-Max-Heap을 호출하여 배열을 최대 힙으로 변환한 다음 힙의 위쪽 요소와 아래쪽 요소를 교환한 다음 아래쪽 요소를 올리고, 마지막으로 Max-Heapify를 호출하여 최대 힙 속성을 유지합니다. 힙의 최상위 요소는 힙에서 가장 큰 요소여야 하므로 한 번의 작업 후에는 힙에 존재하는 가장 큰 요소를 n-1번 반복한 후 힙에서 분리되어 배열됩니다. 전체 과정은 다음과 같습니다.

JavaScript로 설명하면 다음과 같습니다.

function heapSort(array, heapSize) {

 buildMaxHeap(array, heapSize);

 for (int i = heapSize - 1; i > 0; i--) {
  swap(array, 0, i);
  maxHeapify(array, 0, i);
 } 
}

4.JavaScript 언어 구현
마지막으로 위 내용을 다음과 같이 완전한 자바스크립트 코드로 구성합니다.

function heapSort(array) {

 function swap(array, i, j) {
  var temp = array[i];
  array[i] = array[j];
  array[j] = temp;
 }

 function maxHeapify(array, index, heapSize) {
  var iMax,
   iLeft,
   iRight;
  while (true) {
   iMax = index;
   iLeft = 2 * index + 1;
   iRight = 2 * (index + 1);

   if (iLeft < heapSize && array[index] < array[iLeft]) {
    iMax = iLeft;
   }

   if (iRight < heapSize && array[iMax] < array[iRight]) {
    iMax = iRight;
   }

   if (iMax != index) {
    swap(array, iMax, index);
    index = iMax;
   } else {
    break;
   }
  }
 }

 function buildMaxHeap(array) {
  var i,
   iParent = Math.floor(array.length / 2) - 1;

  for (i = iParent; i >= 0; i--) {
   maxHeapify(array, i, array.length);
  }
 }

 function sort(array) {
  buildMaxHeap(array);

  for (var i = array.length - 1; i > 0; i--) {
   swap(array, 0, i);
   maxHeapify(array, 0, i);
  }
  return array;
 }

 return sort(array);
}

5. 힙 정렬 알고리즘 적용

(1) 알고리즘 성능/복잡성
힙 정렬의 시간 복잡도는 매우 안정적이며(입력 데이터에 민감하지 않음을 알 수 있음), 최상의 경우와 최악의 경우가 O(n㏒n) 복잡도입니다.
그러나 공간 복잡도는 구현마다 다릅니다. 위에서 두 가지 일반적인 복잡성, 즉 O(n)과 O(1)에 대해 논의했습니다. 공간 절약의 원칙에 따라 O(1) 복잡도 방법을 권장합니다.

(2) 알고리즘 안정성
힙 정렬은 수많은 선별 및 이동 프로세스를 포함하며 불안정한 정렬 알고리즘입니다.

(3) 알고리즘 적용 시나리오
힙 정렬은 힙을 설정하고 조정하는 과정에서 상대적으로 큰 오버헤드를 발생시키므로 요소가 적은 경우에는 적합하지 않습니다. 그러나 요소가 많을 때는 여전히 좋은 선택입니다. 특히 "처음 n개의 가장 큰 수"와 같은 문제를 해결할 때 거의 선호되는 알고리즘입니다.