# C++ heapsort algorithm example details

• 2020-05-27 06:43:35
• OfStack

The example of this paper describes the C++ heapsort algorithm. I will share it with you for your reference as follows:

The arrangement of the elements in the heap is divided into two types: max-heap or min-heap, where the key of each node is greater than or equal to the key of the child node, and key of each node is less than or equal to the key of the child node.

Since the heap can be regarded as a complete two-fork tree, array of continuous space can be used to simulate a complete two-fork tree. The simple and original implementation is as follows:

``````
#include<iostream>
int heapsize=0;// The global variable records the size of the heap
void heapSort(int array[],int n){
void buildHeap(int [],int);
void exchange(int[],int,int);
void heapify(int[],int);
buildHeap(array,n);
for(int i=n-1;i>=1;i--){
exchange(array,0,i);
heapsize--;
heapify(array,0);
}
}
// Building the heap
void buildHeap(int array[],int n){
void heapify(int[],int);
heapsize=n;
// Starting with the smallest parent node, the heap is made all the way to the root node
for(int i=heapsize/2-1;i>=0;i--){
heapify(array,i);
}
}
// The heap,
void heapify(int array[],int n){
void exchange(int[],int,int);
int left_child=n*2+1;
int right_child=n*2+2;
int largest;
if(left_child<heapsize&&array[left_child]>array[n]){
largest = left_child;
}
else{
largest = n;
}
if(right_child<heapsize&&array[right_child]>array[largest]){
largest=right_child;
}
if(largest!=n){
exchange(array,largest,n);
heapify(array,largest);
}
}
void exchange(int array[],int i,int j){
int tmp = array[i];
array[i]=array[j];
array[j]=tmp;
}
int main(){
int arr[9]={3,1,6,9,8,2,4,7,5};
heapSort(arr,9);
for(int i=0;i<9;++i){
std::cout<<arr[i]<<" ";
}
std::cout<<std::endl;
return 0;
}
STL Implemented in the max-heap In the operation. In the use of heap The algorithm is required to add header files algorithm .
#include <iostream>
#include<vector>
#include<algorithm>
int main()
{
int arr[9]={0,1,2,3,4,8,9,3,5};
std::vector<int> vec(arr,arr+9);
//0 1 2 3 4 8 9 3 5
for(auto c:vec){
std::cout<<c<<" ";
}
std::cout<<std::endl;
make_heap(vec.begin(),vec.end());
//9 5 8 3 4 0 2 3 1
for(auto c:vec){
std::cout<<c<<" ";
}
std::cout<<std::endl;
vec.push_back(7);
push_heap(vec.begin(),vec.end());
//9 7 8 3 5 0 2 3 1 4
for(auto c:vec){
std::cout<<c<<" ";
}
std::cout<<std::endl;
pop_heap(vec.begin(),vec.end());
//8 7 4 3 5 0 2 3 1 9, I just moved the maximum to zero vector Finally, there is no deletion
for(auto c:vec){
std::cout<<c<<" ";
}
std::cout<<std::endl;
std::cout<<vec.back()<<std::endl;//9
// will 9 delete
vec.pop_back();
// continuous pop_heap Operation, the maximum value is placed at the end of each time, and finally, the increment sort is presented
sort_heap(vec.begin(),vec.end());
//0 1 2 3 3 4 5 7 8
for(auto c:vec){
std::cout<<c<<" ";
}
std::cout<<std::endl;
return 0;
}

``````