堆排序outfoxing我

Question

我想實現一個基於數組的堆排序，其排序的前幾個，但不完全，我不明白爲什麼。以下是我的工作：

public class HeapSort{ 

    static int[] numbers = new int[] { 0, 13, 8, 5, 10, 9, 15, 1, 2, 3, 6, 4, 12, 14, 7, 11 }; 
    static int[] array = new int[16]; 

    public static void main(String[] args) { 

     for (int i = 0; i < 15; i++) { 
      array[i] = numbers[i]; 
      if (i > 1) 
       sort(i); 
     } 

     for (int i = 1; i < 15; i++) { 
      System.out.println(array[i]); 
     } 

    } 

    public static void sort(int i) { 

     int parentLocation = i/2; 
     int childLocation = i; 

     int parentValue = array[parentLocation]; 

     int childValue = array[childLocation]; 

      if (childValue < parentValue) { 

       array[parentLocation] = childValue; 
       array[childLocation] = parentValue; 

       sort(parentLocation); 

      } 

    } 

} 

我敢肯定，它在我的使用遞歸的故障召回父的那種，但我不明白爲什麼？

TIA

Answer 1

我有這個min heap implementation在C＃中，很容易閱讀。你的impl缺少了很多。如heapify。看看它。希望能幫助到你。

Answer 2

This is heap_sort which uses heapify and max heap concepts. I coded as per the algorithm in "Intro to Algos" book. Have a look. 

#include "stdafx.h" 

#define LEFT(i)   (2 * (i)) 
#define RIGHT(i)  (((2 * (i)) + 1)) 
#define PARENT(i)  ((i)/2)) 

void print_heap(int input[], int n) 
{ 
    int i; 
    printf("Printing heap: \n"); 
    for (i = 0; i < n; i++) 
     printf("%d ", input[i]); 
    printf("\n"); 
} 

void swap_nodes(int *a, int *b) 
{ 
    int tmp; 
    tmp = *a; 
    *a = *b; 
    *b = tmp; 
} 


void max_heapify(int input[], int i, int n) 
{ 
    int largest; 
    int l = LEFT(i + 1) - 1; // Get 0 based array index 
    int r = RIGHT(i + 1) - 1; // Get 0 based array index 

    if (l < n && input[l] > input[i]) { 
     largest = l; 
    } else { 
     largest = i; 
    } 

    if (r < n && input[r] > input[largest]) { 
     largest = r; 
    } 

    if (largest != i) { 
     swap_nodes(&input[i], &input[largest]); 
     max_heapify(input, largest, n); 
    } 
} 

void heapify(int input[], int n) 
{ 
    for (int i = n/2; i >= 0; i--) 
     max_heapify(input, i, n); 
} 

void heap_sort(int input[], int n) 
{ 
    heapify(input, n); 

    for (int i = n - 1; i >= 1; i--) { 
     swap_nodes(&input[0], &input[i]); 
     n = n - 1; 
     max_heapify(input, 0, n); 
    } 
} 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    //int input[] = {6, 5, 3, 1, 8, 7, 4, 2}; 
    //int input[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7}; 
    int input[] = {5, 3, 17, 10, 84, 19, 6, 22, 9, 1}; 
    //int input[] = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1}; 


    int n = sizeof(input)/sizeof(input[0]); 

    print_heap(input, n); 
    heap_sort(input, n); 
    print_heap(input, n); 

    return 0; 

}