在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

首先，您需要相应地更改每个比较运算符，只需将它们全部取出来并考虑问题。

其次，您只需使用reheapUp to (last/2)来创建堆，因为(last/2+1)处的键没有任何childs。

我以前用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;
}