C++ heapsort algorithm example details

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;
}

I hope this article is helpful to you C++ programming.