堆排序不起作用或计算不正确

Question

最大堆函数工作正常但堆排序不工作。

当我运行这段代码。它显示不正确的计算。

Your input is:
9 79 42 86 33 75

Your max-heap is:
86 79 42 75 33 9

Ascending numerical order:
86 79 42 75 33 9

如您所见，我最后的输出，升序数字顺序与 max-heap 的值相同，但这不是我所期望的。

我的任务是必须从最大堆中对数字进行排序。另外，我必须交换最大堆数组中的第一个和最后一个元素，然后忽略最后一个元素。此外，一旦最后一个元素被忽略，我必须再次执行最大堆函数。

计算工作原理的示例。 max-heap is: 86, 79, 42, 75, 33, 9. 在排序部分，我必须交换第一个和最后一个元素，然后忽略最后一个元素，所以堆排序结果应该是：9, 79, 42 , 75, 33, [86] （方括号表示忽略或删除）。我必须从之前的排序中再次进行 max-heap。第二个最大堆结果将是 79、75、9、42、33。当我返回排序时，我必须交换第一个和最后一个元素，然后再次忽略最后一个元素，因此最大堆是 79、75 , 9, 42, 33 堆排序结果应该是：33, 75, 9, 42, [79], [86]。我必须重新执行相同的步骤，直到所有数字都排序。

我要显示的输出示例：

我的输入是 9, 79, 42, 86, 33, 75

最大堆应该是：86、79、42、75、33、9。

升序数应为：9、33、42、75、79、86。

有关更多示例，请访问网站 https://en.wikipedia.org/wiki/Heapsort#Example，请参阅示例 2 - 排序

这里是计算错误的代码：

#include "stdafx.h"
#include <iostream>

using namespace std;

int heap[30];

void main()
{
int n, index, parent, flag, dummy;
n = 7; //size of table

// user input number
for (index = 1; index < 7; index++) 
{
    cout << "Enter value " << index << ": ";
    cin >> heap[index];
}

// output for user element
cout << "\nYour input is:\n";
for (index = 1; index < 7; index++) 
{
    cout << heap[index] << " ";
}

flag = 1;

while (flag == 1)
{
    flag = 0;

    //heapify
    for (index = 7; index >1; index--)
    {
        parent = index / 2;
        if (heap[parent] < heap[index])
        {
            dummy = heap[parent];
            heap[parent] = heap[index];
            heap[index] = dummy;
            flag = 1;
        }

        // Sorting --> swap first and last of the array and then ignore the 
        //last array and reheap from above until all number sorted.

        while (heap[0] >= 1)
        {
            int last = heap[0];
            int temp1 = heap[1];
            heap[1] = heap[last - 1];
            heap[last - 1] = temp1;
            heap[0]--;
        }
    }
}

cout << "\n\nYour max-heap is:\n";
for (index = 1; index < 7; index++) // output for after heap
{
    cout << heap[index] << " ";
}

cout << "\n\nAscending numerical order:\n";
for (index = 1; index < 7; index++) //output for sorting.
{
    cout << heap[index] << " ";
}

getchar();
getchar();
}

还有我无法更改或替换的代码

    while (flag == 1)
{
    flag = 0;

    //heapify
    for (index = 6; index >1; index--)
    {
        parent = index / 2;
        if (heap[parent] < heap[index])
        {
            dummy = heap[parent];
            heap[parent] = heap[index];
            heap[index] = dummy;
            flag = 1;
        }
    }

}

Answer 1

您的代码中有很多错误。

我注意到的第一个是在你的 while 循环中

while (heap[0] >= 1) //heap[0] = 0 since you declared your array statically
    {
        int last = heap[0]; // last = 0
        int temp1 = heap[1];
        heap[1] = heap[last - 1]; //trying to find element heap[-1] ERROR
        heap[last - 1] = temp1; //heap[-1] = heap[1]
        heap[0]--; //heap[0] = -1 why?
    }

第二个是您在输入循环中从索引 1 开始并转到索引 6（代码中的第一个 for 循环），但是当您试图在第三个 for 循环中对堆产生一些影响时，您是从索引 7 开始，然后转到索引 2。

我在你的代码中找不到方法，所以我 post 我的。它遵循您 post 编辑的维基页面中的算法。

#include <iostream>

using namespace std;



void build_heap(int *heap, int index)
{
    if(index>1)
    {
       int new_input = heap[index], tmp = 0;
    //since your index starts from 1 and goes up to n in heap
    //parent from index k is (k%2==1) ? (k-1)/2 : k/2
    if(index % 2 == 1)
        index--;
    if(heap[index/2] < new_input)
    {

        tmp = heap[index/2];
        heap[index/2] = new_input;
        heap[index] = tmp;
        build_heap(heap, index/2);
       }
    }
}

void make_order_in_heap(int *heap, int n)
{
if(n>1)
{
    int index = 1;
    int child_index;
    bool work = true;

    while(work && index < n)
    {
        //finding child_index
        if( index * 2 + 1 <= n)
        {
            child_index = heap[index*2] > heap[index*2+1] ? index*2 : index*2+1;
        }
        else if(index * 2 <= n)
        {
            child_index = index*2;
        }
        else
        {
            //this index has no  children
            return;
        }
        work = false;
        if(heap[child_index] > heap[index])
        {
            int tmp = heap[index];
            heap[index] = heap[child_index];
            heap[child_index] = tmp;
            index = child_index;
            work = true;
        }
    }

}
}

void swap_first_and_last(int *heap, int n)
{
if(n>1)
{
    int tmp = heap[1];
    heap[1] = heap[n];
    heap[n] = tmp;
}
}

void sort_heap(int *heap, int n)
{
if(n>1)
{
    swap_first_and_last(heap, n);
    //we swaped first and last element in heap with n elements
    //so now first element in heap of n-1 elements is not on his      possiton
    make_order_in_heap(heap, n-1);
    sort_heap(heap, n-1);
}
}

int main()
{
int heap[30];
int n, index, parent, flag, dummy;
n = 7; 

for (index = 1; index <= n; index++) 
{
    cout << "Enter value " << index << ": ";
    cin >> heap[index];
    build_heap(heap, index);
}

cout << "\nYour input is:\n";
for (index = 1; index <= n; index++) 
{
    cout << heap[index] << " ";
}


sort_heap(heap, n);

cout << "\n Sorted array is:\n";
for (index = 1; index <= n; index++) 
{
    cout << heap[index] << " ";
}
return 0;
}

堆排序不起作用或计算不正确

Heap sort it not working or incorrect calculation

c++

sorting

data-structures

heapsort

recursive-datastructures