1. 기본 지식
우리가 일반적으로 힙이라고 부르는 것은 이진 힙을 의미하며, 이는 완전한 이진 트리 또는 대략 완전한 이진 트리라고도합니다. 이진 힙은 가장 큰 힙과 가장 작은 힙으로 나뉩니다.
힙 정렬은 힙 데이터 구조를 사용하여 설계된 정렬 알고리즘을 의미하며, 이는 일종의 분류 선택입니다. 배열의 특성을 사용하여 지정된 인덱스의 요소를 빠르게 찾을 수 있습니다. 배열은 인덱스에 따라 요소를 직접 얻을 수 있으며, 시간 복잡성은 O (1), 즉 상수이므로 가치 획득에 매우 효율적입니다.
최대 힙의 특성은 다음과 같습니다.
최소 힙의 특성은 다음과 같습니다.
2. 알고리즘 생각
1. 가장 큰 힙의 알고리즘 아이디어는 다음과 같습니다.
첫째, 초기 R [0… N-1]은 가장 큰 힙에 내장되어 있습니다. 현재, 그것은 정렬되지 않은 힙입니다. 힙 상단은 가장 큰 요소이며, 순서가없는 영역의 마지막 레코드 r [N-1]가 교환됩니다. 이로 인해 새로운 순서가없는 영역 R [0… N-2] 및 순서 영역 r [N-1]가 발생하며 R [0… N-2] .keys ≤ r [N-1] .key를 만족시킵니다.
첫 번째 r [0… n-2]는 교환 후 최대 힙의 특성을 충족시키지 못할 수 있으므로, 첫 번째 r [0… n-2]는 r [0]의 마지막 요소 만 조정 될 때까지 최대 힙으로 조정됩니다.
최대 힙 정렬이 완료되면 실제로 오름차순 시퀀스입니다. 힙을 조정할 때마다 가장 큰 요소가 얻어지고 전류 힙의 마지막 요소와 교환됩니다. 따라서, 수득 된 최종 서열은 오름차순 시퀀스이다.
2. 가장 작은 힙의 알고리즘 아이디어는 다음과 같습니다.
첫째, 초기 R [0… N-1]은 가장 작은 힙에 내장되어 있습니다. 현재, 그것은 정렬되지 않은 힙입니다. 힙의 최상위 요소는 가장 작은 요소이며, 그 후 상단 R [0]을 반역되지 않은 영역의 마지막 R [N-1]과 교환하여 새로운 비 순응 힙 r [0… N-2] 및 순서 힙 [N-1]을 얻고 R [0… N-2] .keyys> = r [n-1] .key를 만족시킵니다.
첫 번째 R [0… N-2]는 교환 후 최소 힙의 특성을 충족하지 못할 수 있으므로, 첫 번째 R [0… N-2]는 R [0]의 마지막 요소 만 조정되고 최소 힙이 정렬 될 때까지 최소 힙으로 조정됩니다. 최소 힙의 순서가 완료된 후에는 실제로 내림차순 시퀀스입니다. 힙을 조정할 때마다 가장 작은 요소가 얻어지고 전류 비 순서 힙의 마지막 요소와 교환되므로 얻어진 시퀀스는 하강 순서가됩니다.
팁 : 힙 분류 프로세스는 실제로 순서대로 정렬 된 영역을 지속적으로 확장 한 다음 주문 영역 만있을 때까지 무질서한 영역을 지속적으로 줄이는 과정입니다.
3. 분류 프로세스 분석
알고리즘은 비교적 추상적이기 때문에 여기서는 작은 예를 제공하여 힙 분류 프로세스를 직접 설명합니다. 다음으로, 우리는이 순서 대표 시퀀스를 사용하여 힙 분류에 가장 큰 힙을 사용하고 결과 시퀀스는 오름차순 시퀀스 (ASC)입니다.
순서 대상 순서 : 89, -7,999, -89,7,0, -888,7, -7
1 단계 : 빌드 할 최대 힙을 초기화합니다.
2 단계 : 힙 상단의 최대 요소 999를 순서가없는 영역의 마지막 요소로 교환하여 999가 순서대로가됩니다. 교환 후 -7은 힙 상단이됩니다. -7은 정렬되지 않은 영역에서 가장 큰 요소가 아니기 때문에, 순서가없는 영역의 최대 값 89가 힙 상단이되므로 -7과 89가 교환되도록 반면 영역을 조정해야합니다. 교환 후 89의 오른쪽 하위 트리는 가장 큰 힙의 특성을 충족하지 않으므로 오른쪽 하위 트리를 가장 큰 힙으로 조정해야하므로 아래 그림과 같이 -7을 0으로 교환해야합니다.
그림에서 -7% 89% 교환 할 때 파일의 상단이 가장 큰 요소이지만 -7의 왼쪽 자식은 0이고 오른쪽 아이는 -888입니다. -7 <0이므로 노드 -7은 힙의 특성을 충족하지 않으므로 조정해야합니다. 따라서 0은 -7로 교환됩니다.
그런 다음 정렬 된 영역이 될 때까지 두 번째 단계를 반복하십시오.
마지막으로 : 얻은 것은 오름차순 시퀀스입니다
4. 시간 복잡성
힙 분류 시간은 주로 초기 힙을 설정하고 힙을 반복적으로 조정하는 시간 간접비로 구성됩니다. 힙 분류가 불안정하므로 실제 상황에 따라 시간 복잡성이 커질 것이므로 평균 시간 복잡성 만 필요할 수 있습니다.
평균 시간 복잡성은 다음과 같습니다. O (n * log2 (n))
힙 분류의 시간이 소요되는 작업에는 다음이 포함됩니다. 초기 힙 + 힙의 반복 조정 및 시간 복잡성은 다음과 같습니다.
1. 초기 힙 건물 : 각 상위 노드는 왼쪽 및 오른쪽 하위 노드와 최대 2 배를 비교하고 교환하므로 복잡성은 부모 노드 수와 관련이 있습니다. 2x <= n을 기준으로 (x는 n 요소를 반으로 접을 수있는 횟수, 즉 부모 노드의 수) x = log2n으로 얻어집니다. 즉, O (log2n)
2. 힙의 반복 조정 : 힙의 초기화 중에 어레이 비교 결과가 기록되므로 힙 정렬은 원래 시퀀스의 배열 순서에 민감하지 않으며 최상의 상황은 최악의 경우와 유사합니다. 힙 상단 요소는 N-1 회 추출해야합니다. 힙 상단 요소가 취할 때마다 힙을 재구성해야합니다 (O (재구성 힙) <O (초기 힙)). 그래서 O (n-1) * O보다 작습니다 (log2n)
권장 사용 :
힙의 초기화를 비교 해야하는 횟수 이후, 힙 분류는 데이터 양이 매우 큰 상황 (백만 데이터 이상)에 더 적합합니다. 효율적인 빠른 정렬은 재귀 구현을 기반으로하기 때문에 데이터 볼륨이 매우 큰 경우 스택 오버플로 오류가 발생합니다.
5. Java 샘플 코드
공개 클래스 Heapsort {private static int [] sort = new int [] {1,0,10,20,3,6,4,4,9,12, 17,34,11}; public static void main (String [] args) {buildMaxHeapify (정렬); Heapsort (정렬); 인쇄 (정렬); } private static void buildMaxHeApify (int [] data) {// 어린이가없는 사람들만이 최대 힙을 만들어야합니다. 마지막 상위 노드 int startIndex = getParentIndex (data.length-1)에서 시작해야합니다. // 끝에서 최대 힙을 생성하며 (int i = startIndex; i) {maxHeapify (data, i); }}/***최대 힙 생성**@paramdata*@paramheapsize 최대 힙의 크기가 필요합니다. 최대 값은 끝에 배치되기 때문에 종말은 더 이상 최대 힙*@ParamIndex로 분류되지 않습니다. 왼쪽 및 오른쪽 자식 노드 int left = getchildleftIndex (index); int right = getchildrightindex (색인); int large guge = index; if (왼쪽 <heapsize && data [index] <data [left]) {marge = left; } if (right <heapsize && data [large] <data [right]) {가장 큰 = 오른쪽; } // 최대 값을 얻은 후 교환해야 할 수도 있습니다. 교환하면 어린이가 가장 큰 힙이 아닐 수도 있습니다. (가장 큰! = index) {int temp = data [index]; 데이터 [index] = 데이터 [가장 큰]; 데이터 [가장 큰] = 온도; MaxHeApify (데이터, 힙합, 가장 큰); }} /***정렬, 최대 값은 끝에 배치됩니다. 데이터는 가장 큰 힙이지만 * *@paramdata */private static void heapsort (int [] data) {// 끝에 헤더와 교환하고 (int i = data.length-1; i> 0; int tamp = data [0]; 데이터 [0] = 데이터 [i]; 데이터 [i] = 온도; MaxHeapify (데이터, i, 0); }} / ** *paramcurrent *@return * / private static int getParentIndex (int current) {return (current-1) >> 1; } / ** *현재 하위 노드 위치 괄호에주의를 기울이고 추가 우선 순위가 높습니다 *@paramcurrent *@return * / private static int getchildleftIndex (int current) {return (current << 1) +1; } / ** *오른쪽 자식 노드 위치 * *@paramcurrent *@return * / private static int getchildrightIndex (int current) {return (current << 1) +2; } private static void print (int [] data) {int pre = -2; for (int i = 0; i <data.length; i ++) {if (pre <(int) getLog (i+1)) {pre = (int) getLog (i+1); System.out.println (); } system.out.print (data [i]+"|"); }}/** *base 2 * *@paraparam *@return */private static double getLog (double param) {return math.log (param) /math.log (2); }}