쌓 기 정렬 철저히 하기:이 진 쌓 기

두 갈래 로 된 더미
이 진 더미 란 무엇 인가?
이 진 더 미 는 본질 적 으로 완전 이 진 트 리 로 두 가지 유형 으로 나 뉜 다.
4.567917.최대 더미:가장 많은 부모 노드 의 수 치 는 모두 그의 왼쪽,오른쪽 아이 노드 와 같은 값(지붕 이 전체 더미 의 최대 요소)보다 크다

최소 더미:최소 더미 의 모든 부모 노드 의 값 은 왼쪽,오른쪽 아이 노드 의 값(더미 꼭대기 가 전체 더미 의 최소 요소)보다 작다

이 진 더미 의 뿌리 노드 를 더미 꼭대기 라 고 한다.
이 진 더미 의 기본 조작

노드 삽입

노드 삭제
이 진 로 를 구축 하 다.
이 몇 가지 조작 은 모두 더미 의 자기 조정 을 바탕 으로 한다.이른바 더미 의 자기 조정 이란 더미 에 부합 되 지 않 는 완전한 이 진 트 리 를 하나의 더미 로 조정 하 는 것 이다.다음은 최소 더 미 를 예 로 들 자.
끼어들다
노드 0 삽입 과정

삭제
노드 를 삭제 하 는 과정 은 삽입 하 는 과정 과 정반 대 이 고 삭제 하 는 것 은 쌓 인 꼭대기 에 있 는 노드 입 니 다.삭제
4.567917.완전 이 진 트 리 의 구 조 를 유지 하기 위해 쌓 인 마지막 요 소 를 임시로 쌓 은 꼭대기 에 보충 합 니 다원래 10 의 위 치 를 삭제 합 니 다4.567917.지붕 의 노드 10 에 대해 침하 작업 을 실시한다
세우다
두 갈래 더 미 를 구축 하 는 것 은 무질서 한 완전 두 갈래 나 무 를 두 갈래 로 조정 하 는 것 이다.본질은 모든 비 잎 노드 를 한 번 에 가라앉 히 는 것 이다.


이 진 로 코드 구현
2 차 더 미 는 완전한 2 차 트 리 이지 만 그 저장 방식 은 체인 식 이 아니 라 순서 저장 이다.다시 말 하면 2 차 더 미 는 모든 노드 가 배열 에 저장 되 어 있다.

부모 노드 가 parent 일 때 왼쪽 아 이 는 2*parent+1 입 니 다.오른쪽 아 이 는 2*parent+2

/**
 * @author ：zsy
 * @date ：Created 2021/5/17 9:41
 * @description：   
 */
public class HeapTest {
    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
        Heap heap = new Heap(arr);
        heap.upAdjust(arr);
        System.out.println(Arrays.toString(arr));
        arr = new int[]{7, 1, 3, 10, 5, 2, 8, 9, 6};
        heap = new Heap(arr);
        heap.buildHead();
        System.out.println(Arrays.toString(arr));
    }
}
class Heap {
    private int[] arr;
    public Heap(int[] arr) {
        this.arr = arr;
    }
    public void buildHead() {
        //            ，    
        for (int i = (arr.length - 2) / 2; i >= 0; i--) {
            downAdjust(arr, i, arr.length);
        }
    }
    private void downAdjust(int[] arr, int parentIndex, int length) {
        int temp = arr[parentIndex];
        int childrenIndex = parentIndex * 2 + 1;
        while (childrenIndex < length) {
            //      ，          ，        
            if (childrenIndex + 1 < length && arr[childrenIndex + 1] < arr[childrenIndex]) {
                childrenIndex++;
            }
            //               ，    
            if (temp <= arr[childrenIndex]) break;
            //    ，    
            arr[parentIndex] = arr[childrenIndex];
            parentIndex = childrenIndex;
            childrenIndex = 2 * childrenIndex + 1;
        }
        arr[parentIndex] = temp;
    }
    public void upAdjust(int[] arr) {
        int childrenIndex = arr.length - 1;
        int parentIndex = (childrenIndex - 1) / 2;
        int temp = arr[childrenIndex];
        while (childrenIndex > 0 && temp < arr[parentIndex]) {
            //    
            arr[childrenIndex] = arr[parentIndex];
            childrenIndex = parentIndex;
            parentIndex = (parentIndex - 1) / 2;
        }
        arr[childrenIndex] = temp;
    }
}

결과:
[0, 1, 2, 6, 3, 7, 8, 9, 10, 5]
[1, 5, 2, 6, 7, 3, 8, 9, 10]
총결산
이 글 은 여기까지 입 니 다.당신 에 게 도움 을 줄 수 있 기 를 바 랍 니 다.또한 당신 이 우리 의 더 많은 내용 에 관심 을 가 져 주 실 수 있 기 를 바 랍 니 다!