힙은 데이터 구조에서 중요한 구조입니다. "힙"의 개념과 작동을 이해 한 후에는 힙 분류를 빠르게 마스터 할 수 있습니다.
힙의 개념
힙은 특별한 완전한 바이너리 트리입니다. 완전히 이진 트리의 모든 노드의 값이 자녀보다 작지 않은 경우,이를 큰 루트 힙 (또는 큰 상단 힙)이라고합니다. 모든 노드의 값이 자녀보다 크지 않으면 작은 뿌리 힙 (또는 작은 상단 힙)이라고합니다.
배열 (첨자 번호 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) 공간 복잡성이 허용되지 않음)?
방법이 있습니다. 최대 힙을 구축 한 다음 마지막 위치에서 최대 값을 출력하고 마지막 위치에서 두 번째 최대 값을 출력합니다. 매번 최대 요소 출력이 첫 번째 공간을 확보하기 때문에 추가 공간이 필요없이 그러한 요소를 배치 할 수 있습니다. 아주 아름다운 아이디어, 맞습니까?
Public Class Heapsort {public static void main (String [] args) {int [] arr = {50, 10, 90, 30, 70, 40, 80, 60, 20}; System.out.println ( "정렬 전 :"); for (int i = 0; i <arr.length; i ++) {system.out.print (arr [i]+""); } // 힙 정렬 Heapsort (ARR); System.out.println (); System.out.println ( "정렬 후 :"); for (int i = 0; i <arr.length; i ++) {system.out.print (arr [i]+""); }} / *** Heap Sort* / private static void heapsort (int [] arr) {// 시퀀스를 대형 상단 힙으로 정렬 할 순서를 구성합니다 (int i = arr.length / 2; i> = 0; i-) {HeaPadjust (arr, i, arr.length); } // 각 최대 값의 루트 노드를 끝 요소로 점차적으로 바꾸고 이진 트리를 조정하여 (int i = arr.length-1; i> 0; i-) {스왑 (arr, 0, i); // 힙 상단 레코드를 현재 소멸되지 않은 후속 히파드 주름의 마지막 레코드로 교환합니다 (ARR, 0, i); // 교환 후 힙이 큰 상단 힙을 충족하는지 여부를 다시 확인해야합니다. 충족하지 않으면 조정해야합니다}} / *** 힙을 구축하는 과정* @param arr 배열* @param i를 구축 해야하는 힙의 루트 노드 수* / 개인 정적 void headjust (int [] arr, int i, int n) {int n); int 아버지; for (아버지 = arr [i]; leftchild (i) <n; i = child) {child = leftchild (i); // 왼쪽 하위 트리가 오른쪽 하위 트리보다 작 으면 오른쪽 하위 트리를 부모 노드와 비교해야합니다. // 오른쪽 하위 트리를 가리키고 일련 번호를 1 씩 증가시킵니다} // 상위 노드가 하위 노드보다 작은 경우 (아버지 <arr [child]) {arr [i] = arr [child]; } else {break; // 큰 상단 힙 구조가 파괴되지 않으며 조정이 필요하지 않습니다}} arr [i] = 아버지; } // 왼쪽 자식 노드를 가져옵니다. 비공개 정적 int leftchild (int i) {return 2 * i + 1; } // 스왑 요소 위치 private static void swap (int [] arr, int index1, int index2) {int tmp = arr [index1]; ARR [index1] = ARR [index2]; ARR [index2] = TMP; }}