힙 정렬

힙 정렬

힙 정렬은 힙의 데이터 구조를 사용하여 설계된 정렬 알고리즘입니다. 힙 정렬은 최악, 최고, 평균 시간 복잡도가 모두 O(nlogn)이며 불안정한 정렬입니다. . 먼저 힙 구조에 대해 간단히 알아보겠습니다.

Heap

힙은 다음 속성을 갖는 완전한 이진 트리입니다. 각 노드의 값은 큰 힙이라고 하는 왼쪽 및 오른쪽 하위 노드의 값보다 크거나 같습니다. 각 노드의 값이 왼쪽 및 오른쪽 자식 노드의 값보다 작거나 같으면 작은 상단 힙이라고 합니다.

추천 과정: PHP 튜토리얼.

아래와 같이:

동시에 힙의 노드에 레이어별로 번호를 매기고 이 논리 구조를 배열에 매핑합니다. 이는 다음과 같습니다

배열은 다음과 같습니다. 논리적으로 말하면 힙 구조입니다. 힙의 정의를 설명하기 위해 간단한 공식을 사용하겠습니다.

빅 탑 힙: arr[i] >= arr[2i+1] && arr[i] >= arr [2i+2 ]

작은 상단 힙: arr[i]

힙 정렬의 기본 아이디어는 다음과 같습니다. :

정렬할 내용을 넣습니다. 시퀀스는 큰 상위 힙으로 구성됩니다. 이때 전체 시퀀스의 최대값은 힙 상단의 루트 노드입니다. 마지막 요소와 바꾸면 마지막 값이 최대값이 됩니다. 그런 다음 나머지 n-1개 요소를 힙으로 재구성하여 n개 요소 중 다음으로 가장 작은 값을 얻습니다. 이것을 반복해서 실행하면 순서대로의 시퀀스가 ​​나옵니다

위 내용은 힙 정렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!