힙의 특성
힙은 완전히 바이너리 트리이며, 실제로 배열을 통해 구현할 수 있습니다. 가장 중요한 특성 중 하나는 모든 노드가 (보다 크다)는 하위 노드와 같다는 것입니다. 가장 작은 루트 노드가있는 힙을 가장 작은 힙이라고하며 가장 큰 루트 노드가있는 힙을 가장 큰 힙이라고합니다. 다음 그림은 가장 큰 힙과 배열 표현의 예를 보여줍니다. 각 노드는 어린이보다 직관적으로 볼 수 있습니다.
위 그림에서 볼 수 있듯이, 완전히 바이너리 트리의 노드는 어레이 A의 인덱스에 해당하는 루트 노드 번호 1에서 순서대로 배열 될 수 있습니다 (여기서 첨자는 1에서 시작한다는 점). 노드 I가 주어지면 왼쪽 자식이 쉽게 2i, 오른쪽 자식은 2i+1이고 부모 노드는 I/2를 쉽게 얻을 수 있습니다.
힙의 기본 작업
힙에 대한 두 가지 기본 작업이 있습니다 (아래의 최소 힙 참조).
요소 K : k를 배열 끝에 직접 추가 한 다음 버블 위로 힙을 조정하십시오. 버블 업 작동 : 모 노드로 조정할 요소를 비교하고 부모 노드보다 큰 경우 힙의 특성이 복원 될 때까지 교환하십시오.
가장 많은 값을 추출하십시오. 가장 많은 값은 루트 요소입니다. 그런 다음 삭제 한 다음 루트 요소 = 마지막 리프 노드 요소를 보내고 루트 요소에서 버블 다운하여 힙을 조정하십시오. 버블 다운 작동 : 매번 힙의 특성이 복원 될 때까지 왼쪽과 오른쪽 어린이가 교환 할 왼쪽과 오른쪽 어린이가 교환 할 노드를 조정하기 위해 세 노드에서 가장 작은 하위 노드를 선택해야합니다.
실제로, n 요소를 포함하는 변하지 않는 배열을 힙에 구축해야합니다. 아래 힙 클래스의 생성자는 _bubbledown 버블 다운 조정을 통해 힙을 만드는 방법을 보여줍니다. 힙은 본질적으로 완전히 이진 트리이며 트리 높이는 항상 lognlogn입니다. 각 기본 작업의 시간이 소요되는 작업은 힙의 특성을 충족시키기 위해 버블 링 및 조정하는 것이므로 시간 복잡성은 O (Nlogn) O (nlogn)입니다.
Java 예 :
// float public void swim (int k) {while (k/2> = 1 && less (pq [k/2], pq [k]) {exch (pq, k/2, k); k = k/2; }} // 싱크 개인 무효 싱크 () {int k = 1; while (2*k <n) {int j = 2*k; if (Less (pq [j], pq [j+1]) j ++; if (Less (pq [k], pq [j])) exch (pq, k, j); 다른 휴식; k = J; }} 힙 분류 구현 원리
두 단계로 나뉩니다.
1. 바이너리 힙 순서로 배열을 정렬합니다
2. 루트 노드와 마지막 노드의 위치를 변경 한 다음 루트 노드를 가라 앉히십시오.
성취하다:
어쩌면 내 코드는 위의 애니메이션과 약간 다르지만 기본 원칙은 비슷합니다.
공개 클래스 Heapsort 확장베이스 소트 {private int n; @override public void sort (비교 [] a) {n = a.length-1; int k = n/2; while (k> = 1) {싱크 (a, k); 케이--; } k = 1; while (k <= n) {exch (a, k, n-); 싱크 (a, k); }}}