힙 분류는 두 가지 프로세스로 나뉩니다.
1. 더미를 만듭니다.
힙은 본질적으로 완전히 이진 트리이며 다음을 충족해야합니다. 트리의 잎이 아닌 노드의 키워드는 노드의 키워드보다 크지 않습니다 (또는 그 이상).
힙은 큰 뿌리 힙과 작은 뿌리 힙으로 나뉩니다. 오름차순 순서는 큰 루트 힙을 정렬하는 데 사용되며 내림차순 순서는 작은 뿌리 힙을 정렬하는 데 사용됩니다.
큰 루트 힙 인 경우 값이 가장 큰 노드는 함수를 조정하여 힙 루트에 조정됩니다.
2. 꼬리에 힙 뿌리를 저장하고 나머지 시퀀스의 조정 함수를 호출하십시오. 조정이 완료되면 Tail -1 (-1, -2, ..., -i)에 최대 팔로어를 저장 한 다음 나머지 시퀀스를 조정하고 정렬이 완료 될 때까지 프로세스를 반복하십시오.
코드 사본은 다음과 같습니다.
// 함수를 조정합니다
기능 Headadjust (Elements, Pos, Len) {
// 현재 노드 값을 저장합니다
var swap = 요소 [pos];
// 현재 노드의 왼쪽에있는 자식 노드 찾기
var child = pos * 2 + 1;
// 자녀가 없을 때까지 재귀
while (child <len) {
// 현재 노드에 오른쪽에 하위 노드가 있고 오른쪽 하위 노드가 더 크면 오른쪽 하위 노드를 사용하십시오.
// 현재 노드와 비교하십시오
if (child + 1 <len && elements [child] <elements [child + 1]) {
자녀 += 1;
}
// 현재 노드를 가장 큰 하위 노드와 비교하면 값이 적은 경우 값 교환을 수행하고 Exchange 후 현재 노드를 찾습니다.
// 자식 노드에서
if (요소 [pos] <요소 [child]) {
요소 [pos] = 요소 [child];
pos = child;
child = pos * 2 + 1;
}
또 다른{
부서지다;
}
요소 [pos] = 스왑;
}
}
// 힙을 만듭니다
함수 buildheap (요소) {
// 하위 노드로 마지막 노드에서 시작하여 노드를 하위 노드와 비교하고,
//이 노드와 가장 큰 숫자를 교환 한 후 동일한 교환 프로세스가 전면 노드로 수행됩니다.
// 큰 상단 힙이 만들어 질 때까지 (오름차순 순서는 상단이 크고, 하강 순서는 작은 상단입니다)
for (var i = elements.length/2; i> = 0; i-) {
HeadAdjust (요소, I, 요소);
}
}
함수 정렬 (요소) {
// 힙을 만듭니다
buildheap (요소);
// 시퀀스 끝에서 조정합니다
for (var i = elements.length-1; i> 0; i-) {
// 파일의 상단은 항상 가장 큰 요소이므로 더미의 상단과 꼬리 요소가 교환됩니다.
// 최대 요소는 마지막에 저장되며 후속 조정에 참여하지 않습니다.
var swap = 요소 [i];
요소 [i] = 요소 [0];
요소 [0] = 스왑;
// 조정하고 힙 상단에 최대 요소를 조정합니다.
Headadjust (요소, 0, i);
}
}
var 요소 = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
Console.log ( '이전 :' + 요소);
정렬 (요소);
Console.log ( '후 :' + 요소);
능률:
시간 복잡성 : 최고 : O (nlog2n), 최악 : O (nlog2n), 평균 : O (nlog2n).
공간 복잡성 : O (1).
안정성 : 불안정