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

PHP 힙 정렬 알고리즘에 대한 자세한 설명

墨辰丷원래의: 2018-05-18 14:08:321601검색

이 글은 주로 PHP에서 구현된 힙 정렬 알고리즘을 소개하고, PHP 힙 정렬의 원리, 구현 단계, 관련 운영 기법을 예제 형식으로 분석해 놓은 것입니다. 필요하신 분들은 참고하시기 바랍니다.

자세한 내용은 다음과 같습니다.

힙(heap) 컴퓨터 과학에서 특별한 유형의 데이터 구조를 총칭하는 이름으로, 일반적으로 트리로 볼 수 있는 배열 객체입니다.

힙 {k1,k2,ki,…,kn} (ki 92646479c21958fd10d5771b44be50df= k2i,ki >= k2i+1), (i = 1 ,2,3,4...n/2)

힙 정보:

힙에 있는 노드의 값은 항상 상위 노드의 값보다 크거나 작지 않습니다. 힙은 항상 완전한 트리입니다. 이진 트리(아래).
가장 큰 루트 노드가 있는 힙을 최대 힙 또는 큰 루트 힙이라고 하며, 가장 작은 루트 노드가 있는 힙을 최소 힙 또는 작은 루트 힙이라고 합니다.

완전 이진 트리

힙 정렬에 관해서는 이러한 기본 개념이 인터넷 어디에나 있다는 것을 언급해야 합니다. 가장 간단한 것을 선택했습니다. .

완전 이진 트리: 마지막 레벨을 제외하고 각 레벨의 노드 수가 최대값에 도달합니다. 마지막 레벨에서는 오른쪽에 있는 몇 개의 노드만 누락됩니다.

저는 개인적으로 다음 두 가지 특성 때문이라고 결론 내렸습니다.

1. 마지막 레이어에만 빈 노드가 허용되고 빈 노드는 오른쪽에 있습니다. 즉, 리프 노드는 두 레이어에만 나타날 수 있습니다. 가장 큰 레이어(저장 방법의 규칙성);

2. i>1인 경우 트리의 부모는 tree[i p 2]입니다(상위 노드 값의 규칙성).

정렬이 매우 편리합니다.

힙 정렬

힙 정렬은 오름차순에는 큰 상단 힙을 사용하고 내림차순에는 작은 상단 힙을 사용합니다.

이 예에서는 작은 상위 힙을 내림차순으로 사용하여 분석합니다.

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

1. 데이터(49, 38, 65, 97, 76, 13, 27, 50)에서 $arr 배열을 만듭니다.

2. 작은 최상위 힙 생성(주요 단계는 코드 주석에서 설명합니다. 아래 그림은 배열을 사용하여 작은 최상위 힙을 만드는 과정입니다.)
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;
}

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

PHP 힙 정렬 알고리즘에 대한 자세한 설명

관련 기사