최소 힙을 사용한 내림차순 힙 정렬

힙 정렬 - 힙 정렬은 이진 트리 데이터 구조를 사용하여 숫자 목록을 오름차순 또는 내림차순으로 정렬하는 비교 기반 알고리즘입니다. 루트가 가장 작은 요소인 힙 정렬을 통해 힙 데이터 구조를 생성한 다음 루트를 제거하고 루트 위치의 목록에서 두 번째로 작은 숫자를 제공하여 다시 정렬합니다.

Min Heap - 최소 힙은 상위 노드가 항상 하위 노드보다 작은 데이터 구조이므로 루트 노드는 모든 요소 중에서 가장 작은 요소입니다.

문제 설명

정수 배열이 주어졌습니다. min-heap을 사용하여 내림차순으로 정렬합니다.

예 1

으아아아 으아아아

예 2

으아아아 으아아아

방법 1

최소 힙을 사용하여 내림차순으로 힙 정렬을 수행하려면 요소의 최소 힙을 만들고 한 번에 한 요소씩 추출하여 순서를 반대로 하여 내림차순 배열을 얻습니다.

의사코드

으아아아

예: C++ 구현

다음 프로그램에서는 최소 힙을 사용하여 배열을 정렬한 다음 순서를 반대로 바꾸어 결과를 얻습니다.

으아아아

출력

으아아아

시간 복잡도 - O(nlogn)

공간 복잡성 - O(n)

방법 2

이 문제에 대한 또 다른 해결책은 마지막 비-리프 루트 패턴부터 시작하여 거꾸로 작업하면서 최소 힙을 구축하는 것입니다. 그런 다음 루트 노드와 마지막 리프 노드를 교체하여 배열을 정렬한 다음 최소 힙 속성을 복원할 수 있습니다.

의사코드

으아아아

예: C++ 구현

다음 프로그램에서는 heapify() 함수를 사용하여 인덱스 i에 루트가 있는 하위 트리의 최소 힙 속성을 복원하고, heapSort()를 사용하여 역순으로 최소 힙을 빌드합니다.

으아아아

출력

으아아아

heapSort() 함수를 사용하여 최소 힙을 생성하는 이전 방법을 사용하면 이 솔루션에서도 동일한 방법을 사용할 수 있지만 heapify를 사용하여 최소 힙의 속성을 복원하는 대신 기존 힙 정렬 알고리즘을 사용하여 생성합니다. 아민 힙 및 정렬된 요소의 순서는 오름차순이며 원하는 출력을 얻으려면 더 반대입니다.

의사코드

으아아아

예: C++ 구현

다음 프로그램에서는 힙 정렬 알고리즘을 수정하여 배열을 내림차순으로 정렬합니다.

으아아아

출력

으아아아

결론

요약하자면, 최소 힙을 사용하여 내림차순 힙 정렬을 수행하려면 여러 가지 방법을 사용할 수 있으며 그 중 일부는 O(nlogn)의 시간 복잡도를 가지며 각 방법은 서로 다른 공간 복잡도를 갖습니다.

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