힙 정렬로 정렬하는 방법

1 초기 힙을 구성합니다.

힙 리프가 아닌 모든 노드가 필터링됩니다.

마지막 비종단 요소의 첨자는 [n/2] 반올림되므로 필터링은 [n/2]번째 반올림 요소부터 시작하여 뒤에서 앞으로 진행하면 됩니다. .

예를 들어 배열이 주어지면 먼저 배열 요소를 기반으로 완전한 이진 트리를 구성합니다.

그런 다음 리프가 아닌 마지막 노드부터 시작하여 매번 부모 노드, 왼쪽 자식, 오른쪽 자식 노드에서 비교 및 ​​교환이 수행됩니다. 교환으로 인해 자식 노드가 속성을 충족하지 못할 수 있습니다. 따라서 교환된 하위 노드는 각 교환 후에 다시 조정되어야 합니다.

2. 힙 정렬 수행:

초기 힙이 확보되면 정렬할 수 있습니다.

힙 정렬은 선택 정렬입니다. 생성된 초기 힙은 정렬되지 않은 초기 영역입니다.

정렬이 시작되면 먼저 힙의 최상위 요소를 출력하고(가장 높은 값이므로) 힙의 최상위 요소를 마지막 요소와 교환하여 n번째 위치(즉, , 마지막 위치)이 정렬된 영역으로 사용되며, 첫 번째 n-1 위치는 여전히 정렬되지 않은 영역이므로 정렬되지 않은 영역을 조정하고 힙을 얻은 후 힙의 상단과 마지막 요소를 교환하여 힙의 길이가 주문한 면적은 2가 됩니다. . .

이 작업을 계속하여 나머지 요소를 힙에 다시 조정한 다음 힙의 최상위 요소를 주문한 영역에 출력합니다. 각 교환 결과는 순서가 지정되지 않은 영역에 대해 -1, 순서가 지정된 영역에 대해 +1입니다. 이 과정을 정렬된 영역의 길이가 n-1이 될 때까지 반복하여 정렬이 완료됩니다.

3. 힙 정렬 예:

먼저 다음과 같이 초기 힙 구조를 설정합니다.

#🎜 🎜#

그런 다음 힙의 맨 위에 있는 요소와 마지막 요소를 교환합니다. 이때 마지막 위치가 정렬된 영역으로 사용되며(주문된 영역은 노란색으로 표시됨) 그런 다음 순서가 지정되지 않은 다른 영역의 힙 조정이 수행됩니다. 큰 상위 힙을 되찾은 후 상단과 두 번째 요소의 위치를 ​​바꿉니다...

이 과정을 반복하세요:

#🎜 🎜#

마지막으로 주문한 영역의 확장이 완료되었습니다. 즉, 정렬이 완료되었습니다.

#🎜🎜 #

정렬 과정에서 알 수 있듯이, 오름차순을 원하면 큰 상단 힙을 만들고, 내림차순을 원하면 작은 상단 힙을 만듭니다.

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