Может ли кто-нибудь помочь мне выяснить ошибку в куче min-max с помощью C++?
Меня просят создать кучу min-max с использованием C++ в моем назначении класса. Я пытался построить его, но он не складывается. Я проверял код много раз, он тоже не показывает никаких ошибок, но вывод пустой. Я предполагаю, что это ошибка сегментации, но я не могу понять свою ошибку. Может ли кто-нибудь помочь мне понять, что я делаю не так? Я реализовал это из черновика, доступного в Интернете.
#include <iostream>
using namespace std;
#define left(i) (2*i)
#define right(i) ((2*i) + 1)
#define parent(i) ((i)/2)
void TrickleDown(int list[], int n);
void TrickleDownMin(int list[], int n, int i);
void TrickleDownMax(int list[], int n, int i);
bool isMinLevel(int i, int n);
void swap(int x, int y);
void printHeap(int list[], int n);
void TrickleDown(int list[],int n)
{
int i;
for (i = n/2; i>0;i--)
{
if (isMinLevel(i,n) == true)
TrickleDownMin(list, n, i);
else
TrickleDownMax(list, n,i);
}
}
bool isMinLevel(int i, int n)
{
int height = 2;
if (i == 1)
return true;
while (true)
{
if (i >= pow(2, height) && i <= pow(2, (height + 1)) - 1)
return true;
else if (i > n || i < pow(2, height))
return false;
height += 2;
}
}
void TrickleDownMin(int list[], int n, int i)
{
int leftChild = left(i);
int rightChild = right(i);
int m;
int leftChildLeft = left(leftChild);
int rightChildLeft = right(leftChild);
int leftChildRight = left(rightChild);
int rightChildRight = right(rightChild);
if (leftChild > n)
return;
else
{
//finding the index of smallest of children and grandchildren
if (list[leftChild] > list[rightChild])
m = rightChild;
if (list[leftChild] < list[rightChild])
m = leftChild;
if (list[m] > list[leftChildLeft])
m = leftChildLeft;
if (list[m] > list[rightChildLeft])
m = rightChildLeft;
if (list[m] > list[leftChildRight])
m = leftChildRight;
if (list[m] > list[rightChildRight])
m = rightChildRight;
//if m is a grandchildren of i
if (m == leftChildLeft || m == rightChildLeft || m == leftChildRight || m == rightChildRight)
{
if (list[m] < list[i])
{
swap(list[i], list[m]);
if (list[m] > list[parent(m)])
swap(list[m], list[parent(m)]);
}
TrickleDownMin(list, n,i);
}
else // m is a children of i
{
if (list[m] < list[i])
swap(i, m);
}
}
}
void TrickleDownMax(int list[], int n, int i)
{
int leftChild = left(i);
int rightChild = right(i);
int m;
//int mParent = parent(m);
int leftChildLeft = left(leftChild);
int rightChildLeft = right(leftChild);
int leftChildRight = left(rightChild);
int rightChildRight = right(rightChild);
if (leftChild > n)
return;
else
{
//finding the index of largest of children and grandchildren
if (list[leftChild] < list[rightChild])
m = rightChild;
if (list[leftChild] > list[rightChild])
m = leftChild;
if (list[m] < list[leftChildLeft])
m = leftChildLeft;
if (list[m] < list[rightChildLeft])
m = rightChildLeft;
if (list[m] < list[leftChildRight])
m = leftChildRight;
if (list[m] < list[rightChildRight])
m = rightChildRight;
//if m is a grandchildren of i
if (m == leftChildLeft || m == rightChildLeft || m == leftChildRight || m == rightChildRight)
{
if (list[m] > list[i])
{
swap(list[i], list[m]);
if (list[m] < list[parent(m)])
swap(list[m], list[parent(m)]);
}
TrickleDownMin(list, n,m);
}
else // m is a children of i
{
if (list[m] > list[i])
swap(i, m);
}
}
}
void swap(int x, int y)
{
int temp;
temp=x;
x = y;
y =temp;
}
void printHeap(int list[], int n)
{
cout << "Array representation of the min-max heap is: " << endl;
for (int i = 0;i < n;i++)
{
cout << list[i] << " ";
}
cout << endl;
}
int main()
{
int numbers[] = { 25,65,80,8,15,37,5,57 };
int size = sizeof(numbers) / sizeof(numbers[0]);
TrickleDown(numbers, size);
printHeap(numbers, size);
return 0;
}