How do I fix my heapSort function to get my code to work in c++? This is my code
ID: 3705192 • Letter: H
Question
How do I fix my heapSort function to get my code to work in c++?
This is my code: Everything works except for the heapsort function, in which it causes my program to break. The program is a minheap of a person class.
#include <iostream>
#include <string>
using namespace std;
class Person
{
public:
string name;
int age;
int height;
int weight;
Person() {}
Person(string n, int a, int h, int w)
{
name = n;
age = a;
height = h;
weight = w;
}
};
class Heap
{
public:
Person* A;
int last = -1;
Heap(int asize)
{
A = new Person[asize];
}
void Insert(Person x)
{
last++;
A[last] = x;
Heapify(last);
}
int getParentIndex(int childIndex)
{
if (childIndex % 2 == 0) return childIndex / 2 - 1;
else
{
return childIndex / 2;
}
}
int getChildL(int parentIndex)
{
return 2 * parentIndex + 1;
}
int getChildR(int parentIndex)
{
return 2 * parentIndex + 2;
}
void Heapify(int childIndex)
{
int parentIndex = getParentIndex(childIndex);
while (parentIndex >= 0 && childIndex > 0)
{
if (A[childIndex].name < A[parentIndex].name)
{
Person temp = A[parentIndex];
A[parentIndex] = A[childIndex];
A[childIndex] = temp;
}
childIndex = parentIndex;
parentIndex = getParentIndex(parentIndex);
}
}
void Delete(Person x)
{
int index = -1;
for (int i = 0; i <= last; i++)
{
if (A[i].name == x.name)
{
index = 1; break;
}
}
if (index == -1)
{
cout << "Element not found " << endl;
}
Person temp = A[index];
A[index] = A[last];
A[last] = temp;
last--;
HeapifyDown(index);
}
void HeapifyDown(int parentIndex) // only done when parent
{
while (true)
{
int largest = parentIndex;
int childLindex = getChildL(parentIndex);
int childRindex = getChildR(parentIndex);
if (childLindex >= last && A[childLindex].name < A[largest].name)
{
largest = childLindex;
}
if (childRindex >= last && A[childRindex].name < A[largest].name)
{
largest = childRindex;
}
if (largest != parentIndex)
{
Person temp = A[parentIndex];
A[parentIndex] = A[largest];
A[largest] = temp;
parentIndex = largest;
}
else
{
break;
}
}
}
void HeapSort()
{
for (int i = 0; i <10; i++)
{
Delete(A[0]);
}
}
void Print()
{
for (int i = 0; i <= last; i++)
{
cout << "[ " << A[i].name << " " << A[i].age << " " << A[i].height << " " << A[i].weight << "]";
}
cout << endl;
}
};
int main()
{
Person* people = new Person[10];
people[0] = { "Becca", 25, 69, 202 };
people[1] = { "Tom", 19, 59, 200 };
people[2] = { "Mike", 21,67,250 };
people[3] = { "Amanda", 23, 50, 140 };
people[4] = { "Katie", 15, 74, 150 };
people[5] = { "Scott", 35, 58, 145 };
people[6] = { "Jen", 45, 62, 165 };
people[7] = { "Carol", 75, 52, 157 };
people[8] = { "George", 77, 54, 167 };
people[9] = { "Zach", 20, 60, 190 };
Heap* heap = new Heap(10);
heap->Insert(people[0]); heap->Print();
heap->Insert(people[1]); heap->Print();
heap->Insert(people[2]); heap->Print();
heap->Insert(people[3]); heap->Print();
heap->Insert(people[4]); heap->Print();
heap->Insert(people[5]); heap->Print();
heap->Insert(people[6]); heap->Print();
heap->Insert(people[7]); heap->Print();
heap->Insert(people[8]); heap->Print();
heap->Insert(people[9]); heap->Print();
heap->HeapSort();
heap->Print();
getchar();
return 0;
}
Explanation / Answer
The heap is already sorted in the ascending order of names of person. While inserting a new element to heap, the heapify method is called to sort the heap. There is no need of sorting the heap again.Modified code is given below
#include <iostream>
#include <string>
using namespace std;
class Person
{
public:
string name;
int age;
int height;
int weight;
Person() {}
Person(string n, int a, int h, int w)
{
name = n;
age = a;
height = h;
weight = w;
}
};
class Heap
{
public:
Person* A;
int last = -1;
Heap(int asize)
{
A = new Person[asize];
}
void Insert(Person x)
{
last++;
A[last] = x;
Heapify(last);
}
int getParentIndex(int childIndex)
{
if (childIndex % 2 == 0) return childIndex / 2 - 1;
else
{
return childIndex / 2;
}
}
int getChildL(int parentIndex)
{
return 2 * parentIndex + 1;
}
int getChildR(int parentIndex)
{
return 2 * parentIndex + 2;
}
void Heapify(int childIndex)
{
int parentIndex = getParentIndex(childIndex);
while (parentIndex >= 0 && childIndex > 0)
{
if (A[childIndex].name < A[parentIndex].name)
{
Person temp = A[parentIndex];
A[parentIndex] = A[childIndex];
A[childIndex] = temp;
}
childIndex = parentIndex;
parentIndex = getParentIndex(parentIndex);
}
}
void Delete(Person x)
{
int index = -1;
for (int i = 0; i <= last; i++)
{
if (A[i].name == x.name)
{
index = 1; break;
}
}
if (index == -1)
{
cout << "Element not found " << endl;
}
Person temp = A[index];
A[index] = A[last];
A[last] = temp;
last--;
HeapifyDown(index);
}
void HeapifyDown(int parentIndex) // only done when parent
{
while (true)
{
int largest = parentIndex;
int childLindex = getChildL(parentIndex);
int childRindex = getChildR(parentIndex);
if (childLindex >= last && A[childLindex].name < A[largest].name)
{
largest = childLindex;
}
if (childRindex >= last && A[childRindex].name < A[largest].name)
{
largest = childRindex;
}
if (largest != parentIndex)
{
Person temp = A[parentIndex];
A[parentIndex] = A[largest];
A[largest] = temp;
parentIndex = largest;
}
else
{
break;
}
}
}
void Print()
{
for (int i = 0; i <= last; i++)
{
cout << "[ " << A[i].name << " " << A[i].age << " " << A[i].height << " " << A[i].weight << "]";
}
cout << endl;
}
};
int main()
{
Person* people = new Person[10];
people[0] = { "Becca", 25, 69, 202 };
people[1] = { "Tom", 19, 59, 200 };
people[2] = { "Mike", 21,67,250 };
people[3] = { "Amanda", 23, 50, 140 };
people[4] = { "Katie", 15, 74, 150 };
people[5] = { "Scott", 35, 58, 145 };
people[6] = { "Jen", 45, 62, 165 };
people[7] = { "Carol", 75, 52, 157 };
people[8] = { "George", 77, 54, 167 };
people[9] = { "Zach", 20, 60, 190 };
Heap* heap = new Heap(10);
heap->Insert(people[0]); heap->Print();
heap->Insert(people[1]); heap->Print();
heap->Insert(people[2]); heap->Print();
heap->Insert(people[3]); heap->Print();
heap->Insert(people[4]); heap->Print();
heap->Insert(people[5]); heap->Print();
heap->Insert(people[6]); heap->Print();
heap->Insert(people[7]); heap->Print();
heap->Insert(people[8]); heap->Print();
heap->Insert(people[9]); heap->Print();
cout<<"the sorted heap"<<endl;
heap->Print();
return 0;
}
output
[ Becca 25 69 202]
[ Becca 25 69 202][ Tom 19 59 200]
[ Becca 25 69 202][ Tom 19 59 200][ Mike 21 67 250]
[ Amanda 23 50 140][ Becca 25 69 202][ Mike 21 67 250][ Tom 19 59 200]
[ Amanda 23 50 140][ Becca 25 69 202][ Mike 21 67 250][ Tom 19 59 200][ Katie 15
74 150]
[ Amanda 23 50 140][ Becca 25 69 202][ Mike 21 67 250][ Tom 19 59 200][ Katie 15
74 150][ Scott 35 58 145]
[ Amanda 23 50 140][ Becca 25 69 202][ Jen 45 62 165][ Tom 19 59 200][ Katie 15
74 150][ Scott 35 58 145][ Mike 21 67 250]
[ Amanda 23 50 140][ Becca 25 69 202][ Jen 45 62 165][ Carol 75 52 157][ Katie 1
5 74 150][ Scott 35 58 145][ Mike 21 67 250][ Tom 19 59 200]
[ Amanda 23 50 140][ Becca 25 69 202][ Jen 45 62 165][ Carol 75 52 157][ Katie 1
5 74 150][ Scott 35 58 145][ Mike 21 67 250][ Tom 19 59 200][ George 77 54 167]
[ Amanda 23 50 140][ Becca 25 69 202][ Jen 45 62 165][ Carol 75 52 157][ Katie 1
5 74 150][ Scott 35 58 145][ Mike 21 67 250][ Tom 19 59 200][ George 77 54 167][
Zach 20 60 190]
the sorted heap
[ Amanda 23 50 140][ Becca 25 69 202][ Jen 45 62 165][ Carol 75 52 157][ Katie 1
5 74 150][ Scott 35 58 145][ Mike 21 67 250][ Tom 19 59 200][ George 77 54 167][
Zach 20 60 190]
Process returned 0 (0x0) execution time : 0.148 s
Press any key to continue.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.