힙 정렬은 어떤 종류인가요?

힙 정렬은 순서가 지정되지 않은 시퀀스에서 최대 힙을 생성하고 힙의 최상위 요소를 마지막 요소와 교환하고 나머지 요소로 최대 힙을 생성한 다음 순서대로 요소를 교환하여 힙을 생성하는 일종의 정렬입니다. 최대 힙.

Heap sort

정렬되지 않은 시퀀스를 최대 힙으로 생성하고, 힙의 최상위 요소를 마지막 요소로 바꾸고, 나머지 요소를 최대 힙으로 생성하고, 순서대로 요소를 교환하고 최대 힙

시간 복잡도: O(NlogN) 공간 복잡도: O(1)

소개:

힙 정렬(영어: Heapsort)은 힙의 데이터 구조를 이용하여 설계된 정렬 알고리즘을 말합니다. 힙은 완전한 이진 트리에 근접하는 구조이며 동시에 힙 속성을 충족합니다. 즉, 하위 노드의 키 값 또는 인덱스는 항상 상위 노드보다 작거나 큽니다.

힙 작업

힙 데이터 구조에서 힙의 최대값은 항상 루트 노드에 위치합니다(힙이 우선순위 큐에서 사용되는 경우 힙의 최소값은 루트 노드에 위치합니다).

다음 작업은 힙에 정의됩니다.

Max Heapify: 하위 노드가 항상 상위 노드보다 작도록 힙의 끝 하위 노드를 조정합니다.

Build Max Heap: 힙 빌드 모든 데이터 재정렬

힙 정렬: 첫 번째 데이터의 루트 노드를 제거하고 최대 힙 조정의 재귀 연산을 수행합니다

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