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

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

藏色散人
藏色散人원래의
2020-06-29 10:29:1910842검색

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

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

Heap sort

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

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

소개:

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

힙 작업

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

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

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

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

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

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

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.