이 기사에서는 특정 참조 값을 갖는 JS 구현을 주로 소개합니다. 이제 모든 사람과 공유합니다. 필요한 친구가 참조할 수 있습니다.
힙은 완전한 이진 트리입니다. .
완전 이진 트리: 이진 트리에서는 마지막 레이어를 제외하고 다른 레이어의 노드 수가 최대에 도달하고 마지막 레이어의 모든 노드가 왼쪽에 집중됩니다(노드가 누락될 수 있음). 왼쪽의 노드가 가득 찬 경우에만 오른쪽).
빅탑 힙: 루트 노드는 최대값이며, 각 노드의 값은 하위 노드의 값보다 크거나 같습니다.
작은 상단 힙: 루트 노드는 최소값이고, 각 노드의 값은 하위 노드의 값보다 작거나 같습니다.
힙 저장소: 힙은 배열로 구현되며 이는 이진 트리의 레벨 순서 순회와 동일합니다. 아래와 같이:
노드 i의 경우 하위 노드는 2i+1 및 2i+2입니다.
이제 위의 이진 트리를 오름차순으로 정렬해야 하며 이는 세 단계로 나뉩니다.
초기 이진 트리를 큰 최상위 힙(힙파이)으로 변환합니다. 루트 노드가 최대값이 될 때 마지막 노드와 교환합니다.
마지막 노드를 제외하고 나머지 노드로 구성된 새로운 힙을 큰 상위 힙으로 변환합니다. 이때 루트 노드는 하위 최대값이 되며 마지막 노드와 교환됩니다.
힙의 요소 수가 1(또는 해당 배열의 길이가 1)이 될 때까지 2단계를 반복하고 정렬이 완료됩니다.
이 프로세스는 아래에 자세히 설명되어 있습니다.
대형 최상위 힙을 초기화하고 먼저 리프가 아닌 마지막 노드를 선택합니다(상위 노드와 하위 노드 간의 크기 관계만 조정하면 됩니다). , 리프 노드 사이의 크기 관계는 조정할 필요가 없습니다. 배열이 arr이라고 가정하면 리프가 아닌 첫 번째 노드의 첨자는 다음과 같습니다. i = Math.floor(arr.length/2 - 1) = 1, 그림의 점선 상자에 표시된 대로 숫자 4입니다. , 세 개의 숫자를 찾으십시오. 최대 값은 상위 노드와 교환됩니다.
그런 다음 아래 첨자 i는 1씩 감소합니다(즉, 첫 번째 리프가 아닌 노드부터 시작하여 모든 리프가 아닌 노드를 오른쪽에서 왼쪽으로, 아래에서 위로 순회). 이후의 모든 조정은 동일합니다. 즉, 상위 노드와 하위 노드 사이에서 최대값을 찾아 교환합니다.
이 단계에서 숫자 6과 1이 바뀌고 나면 숫자 [1,5,4]로 구성된 힙의 순서가 잘못되어 한 단계 조정이 필요합니다. 따라서 리프가 아닌 노드를 조정할 때마다 하위 힙 순서에 영향을 미치는지 관찰해야 한다는 점에 유의하는 것이 중요합니다!
이 조정 후에는 루트 노드가 최대값이 되어 큰 최상위 힙을 형성하고 루트 노드가 마지막 노드와 교환됩니다.
현재 마지막 노드 6(즉, 최대값)을 제외하고 나머지 노드 [4,5,3,1]의 새로운 힙을 형성하고 이를 큰 상위 힙으로 변환합니다(참고: 이번에는 루트 노드 이외의 다른 노드는 모두 큰 상위 힙의 특성을 충족하므로 루트 노드 4부터 조정을 시작할 수 있습니다. 즉, 4가 있어야 할 위치를 찾을 수 있습니다.
다음으로 힙의 요소 수가 1이 될 때까지 2단계를 반복합니다. 힙의 요소 수 은 1 이고 정렬이 완료되었습니다.
// 交换两个节点
function swap(A, i, j) {
let temp = A[i];
A[i] = A[j];
A[j] = temp;
}
// 将 i 结点以下的堆整理为大顶堆，注意这一步实现的基础实际上是：
// 假设 结点 i 以下的子堆已经是一个大顶堆，adjustheap 函数实现的
// 功能是实际上是：找到 结点 i 在包括结点 i 的堆中的正确位置。后面
// 将写一个 for 循环，从第一个非叶子结点开始，对每一个非叶子结点
// 都执行 adjustheap 操作，所以就满足了结点 i 以下的子堆已经是一大
//顶堆
function adjustHeap(A, i, length) {
let temp = A[i]; // 当前父节点
// j<length function>=0; i--) {
adjustHeap(A, i, A.length);
}
// 排序，每一次for循环找出一个当前最大值，数组长度减一
for(let i = Math.floor(A.length-1); i>0; i--) {
swap(A, 0, i); // 根节点与最后一个节点交换
adjustHeap(A, 0, i); // 从根节点开始调整，并且最后一个结点已经为当
// 前最大值，不需要再参与比较，所以第三个参数
// 为 i，即比较到最后一个结点前一个即可
}
}
let Arr = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
heapSort(Arr);
alert(Arr);</length>프로그램 참고 사항: 노드 i 아래의 힙을 큰 상위 힙으로 구성합니다. 실제로 이 단계의 기본은 다음과 같습니다. 노드 i 아래의 하위 힙이 이미 큰 상위 힙이라고 가정하고 adjustHeap 함수 구현을 수행합니다. 실제로 함수는 노드 i를 포함하는 힙에서 노드 i의 올바른 위치를 찾는 것입니다. 나중에 첫 번째 힙을 수행할 때 heapSort에 for 루프가 작성됩니다. 첫 번째 리프가 아닌 노드부터 시작하여 각 리프가 아닌 노드에서 adjustHeap 작업이 수행되므로 각 adjustHeap에서 노드는 하위- i 아래의 힙은 이미 큰 최상위 힙입니다.
복잡도 분석: adjustHeap 함수는 힙의 레이어당 하나의 노드만 통과합니다. 왜냐하면 n 노드가 있는 완전한 이진 트리의 깊이는 [log2n]+1이므로 adjustHeap의 복잡도는 O(logn)이고 외부 루프의 총 횟수는 f(n)이므로 최종 복잡도는 O(nlogn)입니다.
위 내용은 JS는 힙 정렬을 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
