在C中創建降序堆排序時出現問題

Question

void heapSort(int list[], int last) 
{ 
    // Local Declarations 
    int sorted; 
    int holdData; 
    int walker; 

    // Statements 
    for (walker = 1; walker <= last; walker++) 
      reheapUp (list, walker); 

    // Min Heap created. Now to sort! 
    sorted = last; 
    while (sorted > 0) 
    { 
      holdData = list[0]; 
      list[0] = list[sorted]; 
      list[sorted] = holdData; 
      sorted--; 
      reheapDown (list, 0, sorted, moves, comparisons); 
    } 

    return; 
} 

void reheapUp (int heap[], int newNode) 
{ 
    // Local Declarations 
    int parent; 
    int hold; 

    // Create a min heap 
    // Statements 
    if (newNode) 
    { 
      parent = (newNode - 1)/2; 
      if (heap[newNode] > heap[parent]) // Only change made from ascending order 
      { 
       hold = heap[parent]; 
       heap[parent] = heap[newNode]; 
       heap[newNode] = hold; 
       reheapUp (heap, parent); 
      } 
    } 

    return; 
} 

void reheapDown (int heap[], int root, int last) 
{ 
    // Local Declarations 
    int hold; 
    int leftKey; 
    int rightKey; 
    int largeChildKey; 
    int largeChildIndex; 

    // Statements 
    if ((root * 2 + 1) <= last) 
    {  
      // There is atleast one child 
      leftKey = heap[root * 2 + 1]; 
      if ((root * 2 + 2) <= last) { 
       rightKey = heap[root * 2 + 2]; 
      } 
      else 
       rightKey = -1; 

      // Determine which child is larger 
      if (leftKey > rightKey) 
      { 
       largeChildKey = leftKey; 
       largeChildIndex = root * 2 + 1; 
      } 
      else 
      { 
       largeChildKey = rightKey; 
       largeChildIndex = root * 2 + 2; 
      } 
      // Test if root > large subtree 
      if (heap[root] < heap[largeChildIndex]) 
      {  
       // parent < child 
       hold = heap[root]; 
       heap[root] = heap[largeChildIndex]; 
       heap[largeChildIndex] = hold; 
       reheapDown(heap, largeChildIndex, last); 
      } 
    } 

    return; 
} 

我得到了升序堆排序以通過創建最大堆函數。我讀到創建一個降序排序堆我需要創建一個最小堆，我所做的改變heap[newNode] < heap[parent]爲heap[newNode] > heap[parent]如代碼所示。但是，它仍然沒有秩序。因此，我想要做其他的步驟？我也需要改變reheapDown嗎？

Answer 1

你需要改變你所做的所有值比較heap[root] < heap[largeChildIndex]你沒有提到你改變了。

Answer 2

首先，您需要相應地更改每個比較運算符，只需全部考慮並考慮問題即可。

其次，你只需要重新堆疊到（last/2）來創建堆，因爲在（last/2 + 1）處的鍵沒有任何孩子。

我在C中做了一些堆排序，而且我的代碼行少了，只有一個「heapify」函數。你可能想看看你的代碼，並嘗試簡化事情。

編輯：如果你想在這裏一些靈感是我做過什麼

void fixHeap(int position,int length) 
{ 
    int child = (2*position)+1; 
    int temp;     

    while (child<=length) 
    { 
     if (child<length && vector[child]<vector[child+1]) 
     { 
      child++; 
     } 

     if (vector[position]<vector[child]) 
     { 
      temp = vector[position]; 
      vector[position] = vector[child]; 
      vector[child] = temp; 
      position = child; 
      child = (2*position)+1; 
     } 
     else 
     { 
      return; 
     } 
    } 
} 

void heapSort(int vector[],int N) 
{ 
    int counter; 
    int temp; 

    for (counter=(N-1)/2; counter>=0; counter--) 
    { 
     fixHeap(counter,N-1); 
    } 
    for (counter=N-1; counter>0; counter--) 
    { 
     temp = vector[counter]; 
     vector[counter] = vector[0]; 
     vector[0] = temp; 
     fixHeap(0,counter-1); 
    } 
} 

Answer 3

Here is heap sort using min heap implementation. Have a look, if it helps! 
#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 min_heapify(int input[], int i, int n) 
{ 
    int least; 
    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]) { 
     least = l; 
    } else { 
     least = i; 
    } 

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

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


void heapify(int input[], int n) 
{ 
    for (int i = n/2; i >= 0; i--) 
     min_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; 
     min_heapify(input, 0, n); 
    } 
} 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    int input[] = {5, 3, 17, 10, 84, 19, 6, 22, 9, 1}; 
    int n = sizeof(input)/sizeof(input[0]); 

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

    return 0; 
}