java 데이터 구조의 무더기 정렬(HeapSort) 상세 정보 및 실례

한 무더기 정렬
더미는 중요한 데이터 구조로 큰 뿌리 더미와 작은 뿌리 더미로 나뉘는데 완전 두 갈래 나무이다. 밑에 만약에 수조로 데이터를 저장한다면 어떤 원소를 i(Java수조는 0에서 시작하여 i는 0에서 n-1)로 가정하고 왼쪽 나무가 있다면 왼쪽 나무의 위치는 2i+1이고 오른쪽 나무가 있으면 오른쪽 나무의 위치는 2i+2이며 아버지 노드가 있으면 아버지 노드의 위치는 (n-1)/2로 정한다.가장 큰 무더기의 임의의 나무 뿌리 노드는 임의의 자결점보다 작지 않고, 가장 작은 무더기의 뿌리 노드는 임의의 자결점보다 크지 않다.
이른바 무더기 정렬이란 무더기라는 데이터 구조의 성질을 이용하여 수조를 정렬하는 것이다. 수조의 비강차 정렬에서 사용해야 할 것은 바로 큰 무더기이다. 왜냐하면 큰 무더기의 성질에 따라 알 수 있듯이 가장 큰 값은 반드시 무더기 꼭대기에 있기 때문이다.정렬이 불안정한 정렬 알고리즘으로 시간 복잡도는 O(nlogn)이다.
2 알고리즘 사상
(1) 최대 더미 구축;
(2) 상단을 선택하고 0 위치 요소와 교환한다.
(3) 절차(2)의 교환으로 인해 가장 많은 성질이 깨질 수 있다. 즉, 0위치의 원소가 더 이상 최대 원소가 아니라면maxHeap조정더미(침강법)를 호출하여 실제 상황에 따라 절차를 반복해야 한다(2).
더미 정렬에서 가장 중요한 알고리즘은 maxHeap이다. 이 함수는 한 원소의 두 개의 하위 노드가 가장 큰 무더기의 성질(즉 왼쪽, 오른쪽 하위 나무가 가장 큰 무더기)을 충족시키고 뿌리 원소만 최대 무더기의 성질을 위반할 수 있다고 가정한다. 그러면 이 원소와 좌우 하위 노드의 최대 원소를 찾아낸다. 만약에 이 원소가 가장 크다면 전체 나무는 가장 큰 무더기이고 프로그램이 종료된다. 그렇지 않으면 뿌리 원소와 최대 원소의 위치를 교환한다.최대 요소가 있는 하위 트리를 만들기 위해 maxHeap을 계속 호출합니다.
3 Java 코드

public class HeapSort {
  public static void main(String[] args) {
    int[] arr = {3, 2, 1, 0, -1, -2, -3};
    System.out.println("Before heap:");
    printArray(arr);
    heapSort(arr);
    System.out.println("After heap sort:");
    printArray(arr);
  }

  public static void heapSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
      return;
    }
    buildMaxHeap(arr); // 
    for (int i = arr.length - 1; i >= 1; i--) {
      exchangeElements(arr, 0, i); // 0 
      maxHeap(arr, i, 0); // ， ， 
    }
  }

  private static void buildMaxHeap(int[] arr) { // 
    if (arr == null || arr.length <= 1) {
      return;
    }
    int half = arr.length / 2;
    for (int i = half; i >= 0; i--) {
      maxHeap(arr, arr.length, i);
    }
  }

  private static void maxHeap(int[] arr, int heapSize, int index) {
    int left = index * 2 + 1; // 
    int right = index * 2 + 2; // 
    int largest = index; // 
    if (left < heapSize && arr[left] > arr[index]) {
      largest = left;
    }
    if (right < heapSize && arr[right] > arr[largest]) {
      largest = right;
    }
    if (index != largest) { // 
      exchangeElements(arr, index, largest);
      maxHeap(arr, heapSize, largest);
    }
  }

  public static void printArray(int[] arr) { // 
    System.out.print("{");
    for (int i = 0; i < arr.length; i++) {
      System.out.print(arr[i]);
      if (i < arr.length - 1) {
        System.out.print(", ");
      }
    }
    System.out.println("}");
  }

  public static void exchangeElements(int[] arr, int index1, int index2) { // 
    int temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
  }
}

읽어주셔서 감사합니다. 여러분에게 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!