힙 정렬 알고리즘 설명 및 Java 버전 구현

힙은 데이터 구조에서 중요한 구조입니다. "힙"의 개념과 동작을 이해하면 힙 정렬을 빠르게 익힐 수 있습니다.

힙의 개념
힙은 특별한 완전 이진 트리입니다. 완전한 이진 트리의 모든 노드 값이 자식 노드보다 작지 않으면 이를 대형 루트 힙(또는 대형 최상위 힙)이라고 합니다. 모든 노드의 값이 자식 노드보다 크지 않으면 이를 호출합니다. 작은 루트 힙(또는 작은 상단 힙).
배열(루트 노드는 아래 첨자 0에 저장됨)에서 다음 공식을 쉽게 얻을 수 있습니다(이 두 공식은 매우 중요합니다).
1 아래 첨자 i가 있는 노드, 상위 노드 좌표입니다. 첨자가 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] + " ");
    }
  }
  
  /**
   * 堆排序
   */
  private static void heapSort(int[] arr) { 
    // 将待排序的序列构建成一个大顶堆
    for (int i = arr.length / 2; i >= 0; i--){ 
      heapAdjust(arr, i, arr.length); 
    }
      
    // 逐步将每个最大值的根节点与末尾元素交换，并且再调整二叉树，使其成为大顶堆
    for (int i = arr.length - 1; i > 0; i--) { 
      swap(arr, 0, i); // 将堆顶记录和当前未经排序子序列的最后一个记录交换
      heapAdjust(arr, 0, i); // 交换之后，需要重新检查堆是否符合大顶堆，不符合则要调整
    }
  }
  
  /**
   * 构建堆的过程
   * @param arr 需要排序的数组
   * @param i 需要构建堆的根节点的序号
   * @param n 数组的长度
   */
  private static void heapAdjust(int[] arr, int i, int n) {
    int child;
    int father; 
    for (father = arr[i]; leftChild(i) < n; i = child) {
      child = leftChild(i);
        
      // 如果左子树小于右子树，则需要比较右子树和父节点
      if (child != n - 1 && arr[child] < arr[child + 1]) {
        child++; // 序号增1，指向右子树
      }
        
      // 如果父节点小于孩子结点，则需要交换
      if (father < arr[child]) {
        arr[i] = arr[child];
      } else {
        break; // 大顶堆结构未被破坏，不需要调整
      }
    }
    arr[i] = father;
  }
  
  // 获取到左孩子结点
  private static 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;
  }
}

힙 정렬 알고리즘에 대한 자세한 설명과 Java 버전 구현 관련 기사를 보려면 PHP 중국어 웹사이트를 주목하세요!