在C中创建降序堆排序很麻烦

| 
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
？     
2020-01-23 4 条评论
分享

没有找到相关结果

    已邀请:

    温拎凯玛

            您需要更改所做的所有值比较，例如
    heap[root] < heap[largeChildIndex]
    ，但您没有提到已更改。     
    2020-01-23 0 0
    分享

    恋裂

            首先，您需要相应地更改每个比较运算符，将它们全部考虑下来并考虑问题。 其次，您只需要重新堆集到（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); 
    }
}
        
    2020-01-23 0 0
    分享

    倪蕊悲潍

            
    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;
}
        
    2020-01-23 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    或代码 OrCode.com 备案号：粤ICP备15020848号-1
    Escape time: 0.03774094581604