Почему (n / 2) -1 в куче сортировки? - PullRequest
Новая
       6

Почему (n / 2) -1 в куче сортировки?

1 голос
/ 10 февраля 2020

При сортировке в куче, при перестановке массива для l oop, почему нам нужен i = n / 2-1, и я проверил с помощью n / 2, также он работает как ожидалось. 

 // Build heap (rearrange array) 
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i);

Вместо Я использовал, как показано ниже: 

// Build heap (rearrange array) 
    for (int i = n / 2; i >= 0; i--) 
        heapify(arr, n, i);

Ниже приведена полная программа, 

// Java program for implementation of Heap Sort 
public class HeapSort { 
public void sort(int arr[]) 
{ 
    int n = arr.length; 

    // Build heap (rearrange array) 
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i); 

    // One by one extract an element from heap 
    for (int i=n-1; i>=0; i--) 
    { 
        // Move current root to end 
        int temp = arr[0]; 
        arr[0] = arr[i]; 
        arr[i] = temp; 

        // call max heapify on the reduced heap 
        heapify(arr, i, 0); 
    } 
} 

// To heapify a subtree rooted with node i which is 
// an index in arr[]. n is size of heap 
void heapify(int arr[], int n, int i) 
{ 
    int largest = i; // Initialize largest as root 
    int l = 2*i + 1; // left = 2*i + 1 
    int r = 2*i + 2; // right = 2*i + 2 

    // If left child is larger than root 
    if (l < n && arr[l] > arr[largest]) 
        largest = l; 

    // If right child is larger than largest so far 
    if (r < n && arr[r] > arr[largest]) 
        largest = r; 

    // If largest is not root 
    if (largest != i) 
    { 
        int swap = arr[i]; 
        arr[i] = arr[largest]; 
        arr[largest] = swap; 

        // Recursively heapify the affected sub-tree 
        heapify(arr, n, largest); 
    } 
} 

/* A utility function to print array of size n */
static void printArray(int arr[]) 
{ 
    int n = arr.length; 
    for (int i=0; i<n; ++i) 
        System.out.print(arr[i]+" "); 
    System.out.println(); 
} 

// Driver program 
public static void main(String args[]) {
    int arr[] = {12, 11, 13, 5, 6, 7}; 
    int n = arr.length; 
    HeapSort ob = new HeapSort(); 
    ob.sort(arr);
    System.out.println("Sorted array");
    printArray(arr); 
} }

1 Ответ

4 голосов
/ 10 февраля 2020

Полная двоичная куча высотой h имеет 2^h - 1 элементов. Из них элементы в закрытом диапазоне [0, (2^h)/2-1] являются внутренними узлами (включая root), а элементы в закрытом диапазоне [(2^h)/2, 2^h-2] являются листовыми узлами. Узлы листа - это уже (тривиальные) кучи. Первый элемент, который вам нужно heapify - потому что у него есть дочерний элемент, который может нарушать свойство heap, - имеет индекс (2^h)/2-1.

Это свойство - внутренний узел с самым высоким индексом находится немного ниже половина пути - распространяется и на неполные двоичные кучи. Вытяните несколько куч, и вы увидите шаблон.

...