PHP 구현 힙 정렬

경험
일했습니다. 제가 이 회사에 취직할 때 기술면에서 타격을 받았습니다. 제 데이터 구조 등 기초가 너무 형편없기 때문입니다. 원래 디자이너가 되고 싶었지만...그래도 PHP가 그럭저럭 써준 덕분에 인턴을 할 수 있게 됐지만 그래도 밑천을 좀 보태기로 마음먹었다. 사실 저도 예전에 확실히 기초의 중요성을 느꼈고, 좀 더 깊은 것들은 다 밑바닥에 있어서 잘 배우지 않으면 전혀 진행할 수 없습니다.제가 예전에 PHP로 웹소켓을 만들었을 때, 데이터 패킷, 데이터 프레임 등의 개념이 있어서 헷갈려서 데이터 처리도 못하고 나중에 보완해야 했습니다.그래서 데이터 구조, 알고리즘, 네트워크 등 기초 지식을 다시 배워보려고 하는데, 저처럼 방향을 틀지 마세요, 심지어 이해하기에 이미 늦었습니다.

오늘은 더미 서열을 묻는 질문인데 그때 질문을 받았을 때 완전 이분목 개념도 까먹었어요.그래도 다행히 데이터 구조 기초가 조금 남아있고, 자료도 좀 보고 이해가 되서 PHP를 이용해서 이분목 더미 순위를 적어보고, 이분목, 더미 등의 데이터 구조도 복습하고 싶습니다

쌓다
힙(heap)은 컴퓨터 과학에서 특수한 데이터 구조의 총칭으로 일반적으로 나무 배열로 볼 수 있습니다.

스택 {k1,k2,ki,…,kn} (ki <=k2i,ki <=k2i+1)|(ki >= kk2i,ki >= k2i+1), (i = 1,2,3,4...n/2)

힙에 대하여:

힙에 있는 노드의 값은 항상 상위 노드의 값보다 크거나 작지 않습니다.
더미는 항상 완전한 이분목(아래)입니다.
뿌리 노드에서 가장 큰 더미를 최대 더미 또는 큰 뿌리 더미라고 하고, 뿌리 노드에서 가장 작은 더미를 최소 더미 또는 작은 뿌리 더미라고 합니다

완전이분목
더미 서열이라고 하면 완전 이분목을 빼놓을 수 없고, 이런 기본 개념들이 인터넷에 널려 있고, 저는 가장 간단한 것을 땄습니다.

완전 2차 트리: 마지막 레이어를 제외하고 각 레이어의 노드 수는 최대값에 도달했으며 마지막 레이어에는 오른쪽의 몇 개의 노드만 누락되었습니다.

나는 다음과 같은 두 가지 특징이 있기 때문이라고 스스로 결론 내렸다.

마지막 층에만 빈 노드가 있고 오른쪽에는 빈 노드가 있습니다. 즉, 잎 노드는 가장 큰 두 층에만 나타납니다(저장 방법의 규칙성).
i>1이면 tree의 양친은 tree[idiv 2](부자 노드의 규칙성)이다.
그래서 서열을 매기기에 매우 편리합니다

힙 정렬
더미의 순서는 오름차순을 위해 큰 탑 더미를 사용하고 내림차순을 위해 작은 탑 더미를 사용합니다.

이 예는 내림차순을 찾는 작은 헤드스택을 사용하여 분석됩니다.

힙 정렬 단계는 다음과 같습니다.

1, 우리는 데이터를 (49, 38, 65, 97, 76, 1)3, 27, 50) 배열 $a 만들기rr;

2. 배열 $arr로 작은 탑 더미를 만듭니다(주요 단계, 있을 것입니다.코드 주석에서 설명하면, 아래 그림은 하나의 배열을 사용한다.작은 탑 더미를 만드는 과정;

3.더미의 뿌리(가장 작은 원소)를 마지막 잎과 교환하고,더미 길이를 1로 줄이고 두 번째 단계로 넘어갑니다.

4,더미에 노치가 하나만 있을 때까지 2-3단계를 반복하여 정렬을 완료한다.。

힙 정렬을 위한 PHP 구현

// 배열이므로 첨자가 0부터이므로 첨자가 n개 노드로 표시되는 왼쪽 하위 노드는 2n+1, 오른쪽 하위 노드는 2n+2입니다.
// 초기화 값, 초기 힙 설정
$arr=array(49,38,65,97,76,13,27,50)
$arrSize=count($arr);

// 마지막 정렬은 더 이상 값을 교환할 필요가 없기 때문에 첫 번째 정렬을 추출합니다.
buildHeap($arr,$arrSize)

for($i=$arrSize-1;$i>0;$i--){
swap($arr,$i,0)
$arrSize--;
buildHeap($arr,$arrSize)
}

// 배열로 최소 힙 만들기
function buildHeap(&$arr,$arrSize){
//처음 첨자 $index를 계산하여 그림과 같이 숫자 "97"이 있는 위치를 각 하위 트리의 부모 노드와 비교한다.하위 노드, 최소값을 상위 노드에 저장합니다.중
//$index에서 하나의 나무를 순환 비교하여 최소 더미를 형성한다.
for($index=intval($arrSize/2)-1; $index>=0; $index--){
// 만약 왼쪽 노드가 있다면, 그 첨자를 최소값 $min에 저장한다.
if($index*2+1<$arrSize){
$min=$index*2+1;
// 만약 우자 노드가 있다면, 좌우 노드의 크기를 비교하고, 우자 노드가 더 작다면, 그 노드의 아래를 표시한다.입력 최소값 $min
if($index*2+2<$arrSize){
if($arr[$index*2+2]<$arr[$min]){
$min=$index*2+2;
}
}
//자 노드 중 작은 노드와 부모 노드를 비교하고, 만약 자 노드가 작은 경우, 부모 노드와 위치를 교환하고, 동시에 갱신합니다.작음
if($arr[$min]<$arr[$index]){
swap($arr, $min, $index)
}
}
}
}

// 이 함수는 다음 배열 $arr에서 $one과 $another로 표시된 데이터를 교환하는 데 사용됩니다.
function swap(&$arr,$one,$another){
$tmp=$arr[$one];
$arr[$one]=$arr[$another];
$arr[$another]=$tmp;
}

다음은 정렬의 최종 결과입니다