The max-heap function is working fine but heapsort is not working.
When I run this code. it shows incorrect calculation.
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
As you can see my last output, the Ascending numerical order is the same value as max-heap but this is not what I am expecting.
My task is that I have to sort a number from the max-heap. Also, I have to swap first and last element from the max-heap array and then ignore the last element. Also, once the last element is ignored I have to do max-heap function again.
An example of how the calculation works. max-heap is: 86, 79, 42, 75, 33, 9. In the sorting section, I have to swap first and last element and then ignore the last element, so the heap sort result should be: 9, 79, 42, 75, 33, [86] (square bracket mean ignored or removed). I have to do max-heap again from the previous sorting. The second max-heap result would be 79, 75, 9, 42, 33. when I come back to the sorting I have to swap the first and last element and then ignore the last element again so the max-heap is 79, 75, 9, 42, 33 and the heap sort result should be: 33, 75, 9, 42, [79], [86]. I have to do the same step all over again until all the number sorted.
An example of output that I want to display on:
My input is 9, 79, 42, 86, 33, 75
Max- heap should be: 86, 79, 42, 75, 33, 9.
Ascending number should be: 9, 33, 42, 75, 79, 86.
For more example, Please visit the website https://en.wikipedia.org/wiki/Heapsort#Example, See example 2 - Sorting
And Here the code of incorrect calculation:
#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();
}
Also the code that I can not change or replace which are
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;
}
}
}
You have many bugs in your code.
First one i have noticed is in your while loop
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?
}
Second one is that you are starting from index 1 and go to index 6 in your input loop (first for loop in code), but when you are trying to make some difference in your heap in third for loop you are starting from index 7 and you go to index 2.
I couldn't find a way in your code so i will post mine. It is following the algorithm in that wiki page you posted.
#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;
}