힙 정렬(Heapsort)은 스택 트리(힙)의 데이터 구조를 이용하여 설계된 정렬 알고리즘을 말합니다. 선택 정렬의 한 종류입니다. 배열의 특성을 사용하여 지정된 인덱스에서 요소를 빠르게 찾을 수 있습니다. 힙은 큰 루트 힙과 작은 루트 힙으로 나누어지며 이는 완전한 이진 트리입니다. 큰 루트 힙의 요구 사항은 각 노드의 값이 해당 상위 노드의 값, 즉 A[PARENT[i]] >= A[i]보다 크지 않아야 한다는 것입니다. 배열의 비내림차순 정렬에서는 큰 루트 힙의 요구 사항에 따라 최대값이 힙의 맨 위에 있어야 하기 때문에 큰 루트 힙을 사용해야 합니다.
힙의 정의
완전한 이진 트리에서 부모 노드가 항상 자식 노드보다 크거나 같으면(작거나 같으면) 큰 상단 힙(작은 상단 힙)입니다.
완전 이진 트리는 순차 저장에 적합하므로 배열도 완전 이진 트리로 간주할 수 있습니다.
노드 번호 매기기: 트리의 루트부터 시작하여 상위 수준에서 하위 수준으로, 각 수준의 왼쪽에서 오른쪽으로 순차적으로 모든 노드에 번호를 매겨 전체 이진 트리 구조를 반영하는 선형 시퀀스를 얻습니다.
번호 부여 기능:
노드의 수에서 부모, 좌우 자식, 형제 등의 수를 파생할 수 있습니다. i로 번호가 매겨진 노드가 ki(1≤i≤n)라고 가정하면 다음과 같습니다.
①i>1이면 ki의 부모 번호는 i/2입니다. i=1이면 Ki는 루트 노드입니다. 부모는 없습니다. .
②이면 Ki의 왼쪽 자식의 수는 2i이고, 그렇지 않으면 Ki에는 왼쪽 자식이 없습니다. 즉, Ki는 리프여야 합니다. 따라서 완전한 이진 트리에서 i>n/2로 표시된 노드는 리프 노드여야 합니다.
③ 2i+1≤n이면 Ki의 오른쪽 자식 수는 2i+1이고, 그렇지 않으면 Ki에는 오른쪽 자식이 없습니다.
참고: ki(0≤i≤n)가 배열 첨자를 충족하는 경우 가능한 왼쪽 및 오른쪽 자식은 각각 2i+1 및 2i+2입니다.
힙의 상단이 가장 큰 키워드를 기록하는 기능을 사용하여 매 라운드마다 힙의 최상위 요소를 가져와서 정렬된 영역은 선택 정렬의 각 라운드와 유사하며 정렬된 영역에 최대값이 배치되며 힙 정렬은 선택 정렬의 개선이라고 볼 수 있습니다.
정렬할 키워드의 초기 시퀀스(R0, R1, R2...Rn)를 순서가 지정되지 않은 초기 영역인 큰 최상위 힙으로 구성합니다.
힙 R[의 최상위 요소를 구성합니다. 0] 마지막 요소 R[n]과 교환하면 새로운 무질서한 영역(R0, R1, R2,...Rn-1)과 새로운 정렬된 영역(Rn)을 얻게 됩니다. 교환 후 새 힙 상단 R[0]은 힙의 속성을 위반할 수 있으므로 현재 정렬되지 않은 영역(R0, R1, R2,...Rn-1)을 새 힙에 맞게 조정해야 합니다.
정렬된 영역의 요소 수가 n-1이 될 때까지 2단계와 3단계를 반복하면 전체 정렬 프로세스가 완료됩니다.
//가장 이해하기 어려운 부분
목표: 모든 하위 트리가 힙인 완전한 이진 트리. 이는 이 이진 트리와 노드의 유일한 차이점은 힙 구조를 만족하지 않는다는 것입니다. //매우 중요, 매우 중요, 매우 중요
아래와 같이:
방법: 먼저 루트를 왼쪽 및 오른쪽 하위 트리의 루트 노드와 비교하고 가장 큰 요소를 루트로 교환합니다. node ; 그런 다음 파괴된 경로를 따라 리프 노드까지 조정하면 새로운 힙이 생성됩니다.
응용 프로그램: 1. 위에서 언급한 힙 정렬 아이디어에서 2~3단계에서 정렬되지 않은 영역을 힙으로 조정할 때 사용됩니다.
2. 힙 초기화
리프가 아닌 마지막 노드 i(i=n/2, n은 노드 수)부터 시작하여 i를 루트 노드로 하는 이진 트리는 다음과 같습니다. 필터링을 통해 힙으로 조정되었습니다. 첫 번째 사진을 예로 들면 번호 순서는 8, 7, 6...1입니다.
php实现堆排序: <?php //堆排序,对简单排序的改进 function swap(array &$arr,$a,$b) { $temp=$arr[$a]; $arr[$a]=$arr[$b]; $arr[$b]=$temp; } //调整$arr[$start]的关键字,$arr[$start]、$arr[$start+1]、、、$arr[$end]成为一个大根堆(根节点最大的完全二叉树) //注意:这里节点s的左右孩子是 2*s +1 和 2*s+2(数组开始下标为0时) function HeapAdjust(array &$arr $start $end) { $temp= $arr[$start]; //沿关键字较大的孩子节点向下筛选 //左右孩子计算 (这里数组的开始下标为0) //左边孩子 2*$start+1,右边孩子 2*$start+2 for ($j=2*$start+1; $j <=$end; $j=2*$j+1) { if ($j !=$end &&$arr[$j] <$arr[$j+1]) { $j++; //转化为右边孩子 } if ($temp >=$arr[$j]) { break; //已经满足大根堆 } //将根节点设置为子节点的较大值 $arr[$start]=$arr[$j]; //继续往下 $start=$j; } $arr[$start] =$temp; } function HeapSort(array &$arr) { $count=count($arr); //先将数据结构造成大根堆 (由于是完全二叉树,所以这里用floor($count/2-1),下标小于或等于这个数的节点都是有孩子的节点) for ($i=floor($count /2)-1; $i >=0 ; $i--) { HeapAdjust($arr,$i,$count); } for ($i=$count-1; $i >=0 ; $i--) { //将堆顶元素与最后一个元素交换,获取到最大元素(交换后的最后一个元素),将最大元素放到数组末尾 swap($arr,0,$i); //经过交换,将最后一个元素(最大元素)脱离大根堆,并将未经排序的新数($arr[0...$i-1])重新调整为大根堆 HeapAdjust($arr,0,$i-1); } } $arr=array(4,1,5,9); HeapSort($arr); v
관련 권장 사항:
PHP 힙 정렬 구현 코드위 내용은 PHP 힙 정렬에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!