Java의 힙 정렬 알고리즘 분석 예

이 글에서는 주로 Java 힙 정렬 알고리즘과 관련된 코드를 자세히 소개합니다. 관심 있는 친구들이 참고할 수 있습니다.

힙은 데이터 구조에서 중요한 구조입니다. 힙 정렬을 빠르게 익히는 데 도움이 될 수 있습니다.

힙의 개념

힙은 특별한 완전 이진 트리입니다. 완전한 이진 트리의 모든 노드 값이 자식 노드보다 작지 않으면 이를 큰 루트 힙(또는 빅탑 힙)이라고 합니다. 모든 노드의 값이 자식 노드보다 크지 않으면 이를 호출합니다. 작은 루트 힙(또는 작은 상단 힙).

배열(루트 노드는 첨자 0에 저장됨)에서 다음 공식을 쉽게 얻을 수 있습니다(이 두 공식은 매우 중요합니다).

1 첨자 i가 있는 노드, 상위 노드 좌표는 ( i- 1)/2;

2. 첨자가 ​​i인 노드의 경우 왼쪽 자식 노드의 좌표는 2*i+1이고 오른쪽 자식 노드는 2*i+2입니다.

힙 생성 및 유지 관리

힙은 다양한 작업을 지원할 수 있지만 이제 우리는 두 가지 질문에만 관심이 있습니다.

1. 순서가 지정되지 않은 배열이 주어지면 힙으로 만드는 방법은 무엇입니까?

2. 힙의 최상위 요소를 삭제한 후 배열을 새 힙으로 조정하는 방법은 무엇입니까?

두 번째 질문을 먼저 살펴보겠습니다. 이미 큰 루트 더미가 준비되어 있다고 가정합니다. 이제 루트 요소를 삭제했지만 다른 요소는 이동하지 않았습니다. 무슨 일이 일어나는지 생각해 보세요. 루트 요소는 비어 있지만 다른 요소는 여전히 힙 속성을 유지합니다. 마지막 요소(코드명 A)를 루트 요소의 위치로 이동할 수 있습니다. 특별한 경우가 아니면 힙의 성격이 소멸된다. 그러나 이는 A가 자식 중 하나보다 작기 때문입니다. 따라서 A와 이 하위 요소의 위치를 ​​바꿀 수 있습니다. A가 모든 하위 요소보다 크면 힙이 조정됩니다. 그렇지 않으면 위 프로세스가 반복되고 A 요소는 적절한 위치에 도달할 때까지 트리 구조에서 계속 "싱크"되고 배열은 힙을 다시 얻습니다. 속성. 위의 과정을 일반적으로 '스크리닝'이라고 하며, 방향은 명백히 하향식입니다.

요소를 삭제할 때도 마찬가지고, 새 요소를 삽입할 때도 마찬가지입니다. 차이점은 새 요소를 끝에 배치한 다음 상위 노드, 즉 상향식 필터링과 비교한다는 것입니다.

그렇다면 첫 번째 문제를 어떻게 해결해야 할까요?

내가 읽은 많은 데이터 구조 책은 리프가 아닌 첫 번째 노드부터 루트 요소가 필터링될 때까지 필터링됩니다. 이 방법을 "스크리닝 방법"이라고 하며 n/2개 요소를 스크리닝하려면 루프가 필요합니다.

그러나 우리는 "무에서 유를 만든다"는 생각에서도 배울 수 있습니다. 첫 번째 요소를 힙으로 처리하고 여기에 새 요소를 계속 추가할 수 있습니다. 이 방법을 "삽입 방법"이라고 하며 루프에 (n-1)개의 요소를 삽입해야 합니다.

심사 방법과 삽입 방법이 다르기 때문에 동일한 데이터에 대해 생성되는 힙도 일반적으로 다릅니다.

힙에 대한 전반적인 이해가 끝나면 힙 정렬은 당연합니다.

알고리즘 개요/아이디어

오름차순 시퀀스가 ​​필요한데 어떻게 해야 하나요? 최소 힙을 구축한 다음 매번 루트 요소를 출력할 수 있습니다. 그러나 이 방법에는 추가 공간이 필요합니다. 그렇지 않으면 많은 수의 요소가 이동되고 복잡도가 O(n^2)로 치솟습니다. 제자리에서 정렬해야 하는 경우(예: O(n) 공간 복잡도는 허용되지 않음) 어떻게 해야 합니까?
방법이 있습니다. 최대 힙을 쌓은 다음 거꾸로 출력하면 마지막 위치에 최대값이 출력되고, 마지막 위치에 두 번째로 큰 값이 출력되는데... 매번 가장 큰 요소 출력이 첫 번째 공간을 확보하게 되므로 , 우리는 추가 공간이 필요하지 않은 요소를 배치할 수 있습니다. 정말 좋은 아이디어죠?

rreee

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