집 > 기사 > 백엔드 개발 > PHP 힙 정렬에 대한 자세한 설명

PHP 힙 정렬에 대한 자세한 설명

小云云원래의: 2018-03-29 11:35:261992검색

힙 정렬(Heapsort)은 스택 트리(힙)의 데이터 구조를 이용하여 설계된 정렬 알고리즘을 말합니다. 선택 정렬의 한 종류입니다. 배열의 특성을 사용하여 지정된 인덱스에서 요소를 빠르게 찾을 수 있습니다. 힙은 큰 루트 힙과 작은 루트 힙으로 나누어지며 이는 완전한 이진 트리입니다. 큰 루트 힙의 요구 사항은 각 노드의 값이 해당 상위 노드의 값, 즉 A[PARENT[i]] >= A[i]보다 크지 않아야 한다는 것입니다. 배열의 비내림차순 정렬에서는 큰 루트 힙의 요구 사항에 따라 최대값이 힙의 맨 위에 있어야 하기 때문에 큰 루트 힙을 사용해야 합니다.

힙의 정의

완전한 이진 트리에서 부모 노드가 항상 자식 노드보다 크거나 같으면(작거나 같으면) 큰 상단 힙(작은 상단 힙)입니다.

힙 배열 저장 방법

완전 이진 트리는 순차 저장에 적합하므로 배열도 완전 이진 트리로 간주할 수 있습니다.

노드 번호 매기기: 트리의 루트부터 시작하여 상위 수준에서 하위 수준으로, 각 수준의 왼쪽에서 오른쪽으로 순차적으로 모든 노드에 번호를 매겨 전체 이진 트리 구조를 반영하는 선형 시퀀스를 얻습니다.

PHP 힙 정렬에 대한 자세한 설명

번호 부여 기능:

노드의 수에서 부모, 좌우 자식, 형제 등의 수를 파생할 수 있습니다. 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단계를 반복하면 전체 정렬 프로세스가 완료됩니다.

필터링 알고리즘

PHP 힙 정렬에 대한 자세한 설명 //가장 이해하기 어려운 부분

목표: 모든 하위 트리가 힙인 완전한 이진 트리. 이는 이 이진 트리와 노드의 유일한 차이점은 힙 구조를 만족하지 않는다는 것입니다. //매우 중요, 매우 중요, 매우 중요

아래와 같이:

clip_PHP 힙 정렬에 대한 자세한 설명002 방법: 먼저 루트를 왼쪽 및 오른쪽 하위 트리의 루트 노드와 비교하고 가장 큰 요소를 루트로 교환합니다. node ; 그런 다음 파괴된 경로를 따라 리프 노드까지 조정하면 새로운 힙이 생성됩니다.

clip_PHP 힙 정렬에 대한 자세한 설명003 응용 프로그램: 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 힙 정렬에 대한 자세한 설명

힙 배열 저장 방법

힙 정렬 아이디어(가장 큰 힙을 예로 들어)

스크리닝 알고리즘의 목표는 모든 하위 트리가 힙인 완전한 이진 트리이기 때문에 스크리닝 알고리즘의 정확성은 리프가 아닌 마지막 노드에서 보장됩니다.

관련 기사