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

이 글에서는 주로 PHP에서 구현된 힙 정렬 알고리즘을 소개합니다. PHP 힙 정렬의 원리, 구현 단계 및 관련 운영 기술을 예제 형식으로 분석합니다. 도움이 필요한 친구가 참고할 수 있습니다.

이 글의 예제는 PHP에서 구현된 힙 정렬 알고리즘. 참고하실 수 있도록 자세한 내용을 공유합니다.

Experience

제가 근무했던 회사에서 면접을 볼 때 기술적인 측면에 압도되었습니다. 기본 데이터 구조와 기타 기본 사항이 정말 열악했지만 디자이너가 되고 싶었습니다. . . 다만, PHP를 잘 쓸 수 있기 때문에 인턴십을 하러 올 수도 있지만, 그래도 기초를 다지기로 결심합니다. 사실 예전부터 기초의 중요성을 느낀 적이 있는데, 좀 더 깊은 것들은 상대적으로 수준이 낮아서, 잘 배우지 않고는 나아갈 길이 없습니다. 예를 들어 이전에는 PHP를 사용하여 웹소켓을 만들었는데, 여기에는 데이터 패킷, 데이터 프레임 등의 개념이 포함되어 있었는데, 알아낼 수도 없었고 데이터 처리도 할 수 없어서 나중에 보충해야 했습니다. 그래서 저는 데이터 구조, 알고리즘, 네트워크 등의 기본 지식을 다시 배울 것입니다. 여러분이 이해하기 전까지는 너무 늦을 것입니다.

오늘은 제가 질문받았을 때 완전 이진 트리의 개념조차 잊어버렸던 힙 정렬 질문에 대해 이야기해보겠습니다. 다행스럽게도 아직 자료구조 기초가 조금 남아있고, 정보를 좀 읽어보니 어느 정도 이해가 되서 PHP를 이용해서 힙 종류의 바이너리 트리를 작성해보고 싶은데, 그런데 바이너리 트리, 힙에 대한 리뷰도 하게 되네요. 및 기타 데이터 구조.

Heap

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 힙 정렬 알고리즘 예제에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!