Heap Sort in C++

Okay, so after struggling with trying to debug this, I have finally given up. I'm a beginner in C++ & Data Structures and I'm trying to implement Heap Sort in C++. The code that follows gives correct output on positive integers, but seems to fail when I try to enter a few negative integers.

Please point out ANY errors/discrepancies in the following code. Also, any other suggestions/criticism pertaining to the subject will be gladly appreciated.

//Heap Sort
#include <iostream.h>
#include <conio.h>
int a[50],n,hs;
void swap(int &x,int &y)
{
    int temp=x;
    x=y;
    y=temp;
}
void heapify(int x)
{
    int left=(2*x);
    int right=(2*x)+1;
    int large;
    if((left<=hs)&&(a[left]>a[x]))
    {
        large=left;
    }
    else
    {
        large=x;
    }
    if((right<=hs)&&(a[right]>a[large]))
    {
        large=right;
    }
    if(x!=large)
    {
        swap(a[x],a[large]);
        heapify(large);
    }
}
void BuildMaxHeap()
{
    for(int i=n/2;i>0;i--)
    {
        heapify(i);
    }
}
void HeapSort()
{
    BuildMaxHeap();
   开发者_Python百科 hs=n;
    for(int i=hs;i>1;i--)
    {
        swap(a[1],a[i]);
        hs--;
        heapify(1);
    }
}
void main()
{
    int i;
    clrscr();
    cout<<"Enter length:\t";
    cin>>n;
    cout<<endl<<"Enter elements:\n";
    for(i=1;i<=n;i++)       //Read Array
    {
        cin>>a[i];
    }
    HeapSort();
    cout<<endl<<"Sorted elements:\n";
    for(i=1;i<=n;i++)       //Print Sorted Array
    {
        cout<<a[i];
        if(i!=n)
        {
            cout<<"\t";
        }
    }
    getch();
}

I've been reading up on Heap Sort but I'm not able to grasp most of the concept, and without that I'm not quite able to fix the logical error(s) above.

---

You set hs after calling BuildMaxHeap. Switch those two lines.

hs=n;
BuildMaxHeap();

---

When I implemented my own heapsort, I had to be extra careful about the indices; if you index from 0, children are 2x+1 and 2x+2, when you index from 1, children are 2x and 2x+1. There were a lot of silent problems because of that. Also, every operation needs a single well-written siftDown function, that is vital.

Open up Wikipedia at the Heapsort and Binary heap articles and try to rewrite it more cleanly, following terminology and notation where possible. Here is my implementation as well, perhaps it can help.

Hmmm now that I checked your code better, are you sure your siftDown/heapify function restricts sifting to the current size of the heap?

Edit: Found the problem! You do not initialize hs to n before calling BuildMaxHeap().

---

I suspect it's because you're 1-basing the array. There's probably a case where you're accidentally 0-basing it but I can't spot it in the code offhand.

---

Here's an example if it helps.

#include <iostream>
#include <vector>

using namespace std;

void max_heapify(std::vector<int>& arr, int index, int N) {
    // get the left and right index
    int left_index = 2*index + 1;
    int right_index = 2*index + 2;

    int largest = 0;
    if (left_index < N && arr[left_index] > arr[index]) {
        // the value at the left_index is larger than the 
        // value at the index of the array
        largest = left_index;
    } else {
        largest = index;
    }

    if (right_index < N && arr[right_index] > arr[largest]) {
        // the value at the right_index is larger than the
        // value at the index of the array
        largest = right_index;
    }

    // check if largest is still the index, if not swap
    if (index != largest) {
        // swap the value at index with value at largest
        int temp = arr[largest];
        arr[largest] = arr[index];
        arr[index] = temp;

        // once swap is done, do max_heapify on the index
        max_heapify(arr, largest, N);
    }
}

void build_max_heap(std::vector<int>& arr, int N) {
    // select all the non-leaf except the root and max_heapify them
    for (int i = N/2 - 1; i >= 0; --i) {
        max_heapify(arr, i, N);
    }
}

void heap_sort(std::vector<int>& arr) {
    int N = arr.size();
    int heap_size = N;
    // build the max heap
    build_max_heap(arr, N);

    // once max heap is built,
    // to sort swap the value at root and last index
    for (int i = N - 1; i > 0; --i) {
        // swap the elements
        int root = arr[0];
        arr[0] = arr[i];
        arr[i] = root;

        // remove the last node
        --heap_size;

        // perform max_heapify on updated heap with the index of the root
        max_heapify(arr, 0, heap_size);
    }
}

int main() {
    std::vector<int> data = {5,1,8,3,4,9,10};

    // create max heap from the array
    heap_sort(data);

    for (int i : data) {
        cout << i << " ";
    }

    return 0;
}

---

# include <iostream>   //Desouky//
 using namespace std;

void reheapify(int *arr, int n, int i)
{
int parent = i; // initilaize largest as parent/root
int child1 = 2 * i + 1; // to get first chid 
int child2 = 2 * i + 2; // to get second child

if (child1 < n && arr[child1] > arr[parent]) // if child2 >  parent
{
    parent = child1;
}
//if child > the parent 
if (child2 < n && arr[child2] > arr[parent])
{
    parent = child2;
}
// if the largest  not the parent 
if (parent != i)
{
    swap(arr[i], arr[parent]);
    // Recursively heapify the affected sub-tree
    reheapify(arr, n, parent);
}

}
 void heapsort(int *arr, int n)
 {
 // build a heap
for (int i = n - 1; i >= 0; i--)
{
    reheapify(arr, n, i);
}
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--)
{
    // Move current root to end
    swap(arr[0], arr[i]);

    // call max heapify on the reduced heap
    reheapify(arr, i, 0);
 }
 }

 int main()
 {

freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int n;
cin >> n;
int* arr = new int[n];
for (int i = 0; i < n; i++)
{
    cin >> arr[i];
}
heapsort(arr, n);
for (int i = 0; i < n; i++)
{
    cout << arr[i] << " ";
}

 }