C++ Heapsort 引发错误

Question

这是我的完整实现代码，带有一些注释。我尝试从各处收集一些代码

#include <iostream>
#include <math.h> 
#include <conio.h>
#include "Header.h"
using namespace std;
void swap(int &x, int &y)
{
int temp = x;
x = y;
y = temp;
}
heap::heap()
{
/*
int x[10] = { 1, 12, 33, 44, 2, 6, 7, 8, 9, 10 };
heapsize = 10;
SetData(x);
*/
}
bool heap::empty()
{
return heapsize == 0;
}
int heap::parent(int index)
{
int x;
if (index % 2 == 0)
{
    x = ((index - 1) / 2);
}
else
{
    x = (index / 2);
}
return x;
}
int heap::left(int index)
    {
int a;
a = 2 * index ;
    return a;
    }
    int heap::right(int index)
    {
int a;
a = 2 * index + 1 ;
return a;
}

void heap::Heapify(int i)
{
int temp, l, r, largest;
l = left(i);
r = right(i);
if ((l <= heapsize) && (A[l] > A[i]))
    largest = l;
else largest = i;
if ((r <= heapsize) && (A[r] > A[largest]))
    largest = r;
if (i != largest)
{
    //swap(A[i], A[largest]);
    temp = A[i];
    A[i] = A[largest];
    A[largest] = temp;
    Heapify(largest);
}
}
void heap::Buildheap()
{
for (int i = heapsize ; i > 0; i--)
    Heapify(i);
}

void heap::insert()
{
int insert;
heapsize = (heapsize + 1);
cout << "insert please:" << endl;
cin >> insert;
int temp = insert;
Buildheap();
cout << "Done!" << endl;
}
void heap::viewheap()
{
Buildheap();

for (int count = 0; count <= heapsize ; count++)
{
    cout << A[count]<<" ";
}
cout << endl << endl;
}
void heap::heapsort()
{
Buildheap();
int temp;
for (int i = 0; i < heapsize; i++)
{
    //temp = A[heapsize -1];
    //A[heapsize -1] = A[0];
    //swap(A[1], A[i]);
    swap(A[1], A[i]);
    heapsize--; 
    Heapify(1);
    /*
    temp = A[heapsize - 1];
    A[heapsize - 1] = A[0];
    heapsize--;
    Buildheap();
    */
}
viewheap();
}
int heap::getmax(int)
{
int temp;
if (empty())
    cout << "Queue is EMPTY!" << endl;
else
{
    Buildheap();
    temp = A[0];
}
return temp;
}
void heap::rmax()
{
if (empty())
    cout << "Queue is EMPTY!" << endl;
else
{
    Buildheap();
    A[0] = A[heapsize];
    heapsize--;

    Heapify(0);
}
}
void heap::SetData(int x[])
{
for (int i = 0; i <= (heapsize); i++)
{
    A[i] = x[i];
}
}

这是我的页眉：

class heap
{
private:
int parent(int);
int left(int);
int right(int);
void Buildheap();

void Heapify(int);
public:
int A[100];
heap();
void insert();
bool empty();
void heapsort();
int getmax(int);
void rmax();
int heapsize;
void viewheap();
void SetData(int[]);
};

我的代码引发错误。

Answer 1

在父级而不是

的实现中

 int heap::parent(int index){
    int x;
    if (index % 2 == 0){
      x = ((index - 1) / 2);
    } else {
      x = (index / 2);
    }
    return x;
 }

你可以简单地写

  int heap::parent(int index){
    return index / 2;
 }

在方法 insert 中，您从控制台读取新的 int，然后在不传递任何内容的情况下调用方法 Build，因此方法 Build 不会知道任何关于 int 'insert' 的信息。当你想插入新元素时，你遍历整个数组并为每个索引调用 Heapify。所以在你的算法中插入新元素需要nlogn时间复杂度，这是非常巨大的，在堆中插入一个元素可能在logn时间内完成。您只需要查看插入堆的算法。这是一些描述插入指令的演示 http://upload.wikimedia.org/wikipedia/commons/4/4d/Heapsort-example.gif

还有堆排序算法

http://en.wikipedia.org/wiki/Heapsort

Answer 2

h::insert() 似乎没有向数据结构中插入任何内容。

我找不到一个有效的例子。您能不能提供一个输出错误的最小示例。

C++ Heapsort 引发错误

C++ Heapsort raise error

c++

heap

heapsort