Page 251 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes int n;
cout << “Please insert the number of elements to be sorted:”;
cin >> n; // The total number of elements
for(int i=0;i < n;i++)
{
cout << “Input” << i << “element:”;
cin >> a[i]; // Adding the elements to the array
}
cout << “Unsorted list:” << endl; // Displaying the
unsorted array
for(int i=0;i < n;i++)
{
cout << a[i] << “ ”;
}
heap_gen1(a,v,n);
cout << “nGenerated Heap:n”;
display(v,n);
cout << “nAfter sorting”;
heap_sort(a,n,v);
cout << “n”;
display(a,n);
return 0;
}
The output is shown as below:

Source: http://www.exforsys.com/tutorials/c-algorithms/heap-sort.html
The function heap_sort is the one that is removing the top of the heap tree and making the
sorting list. The implementation of the algorithm simply follows the same steps as those from
the above example.

Complexity

HeapSort’s space-complexity is O(1), just a few scalar variables. It uses a data structure known as
a max-heap which is a complete binary tree where the element at any node is the maximum of
itself and all its children. A tree can be stored either with pointers as per the pictorial representation
we are normally used to visualize, or by mapping it to a vector. Here if a node in the tree is
mapped to the ith element of an array, then its left child is at 2i, its right child is at (2i+1) and its
parent is at floor(i/2). We can construct a heap by starting with a an existing heap, adding an

244 LOVELY PROFESSIONAL UNIVERSITY