C language data structure heap sort order storage (ascending order)

Heap sort order storage (ascending order)

1: the concept of a complete two-fork tree: the former h-1 layer is a full two-fork tree, and the last layer is continuously missing the right node!

2: the first heap is a complete two-fork tree:

a: building a heap is a two-step process: • create a full two-fork tree () and adjust it to 1 heap

(note: large root heap is in ascending order, small root heap is in descending order)

b: algorithm description: create a complete two-fork tree

while(with parents){
A: adjust to large root heap;
B: exchange root and leaf nodes;
C: cut off leaf nodes;
}

c: time complexity is O(nlogn), space complexity is O(1), is unstable sort!

Code implementation:

/* Heapsort idea :[ completely 2 The definition of a fork tree : before  h-1  Layer to full 2 tree 1 The last 1 Layer continuously missing right node ( The children of the right )] . ( The large root heap is sorted in ascending order, and the small root heap is sorted in descending order ) 
   The first pile is 1 A completely 2 tree   , according to the array index can be built 1 Tree completely 2 tree  
   The second :while( To have two parents ){ 
    A:  Adjusted for 1 A large root pile           【 Adjust() Function implementation  
    B:  Swap the last 1 Leaves and roots      【 Swap() Function implementation  
    C:  Cut off the last 1 Leaf nodes        The number of elements  n-- 】  
  } 
*/ 
 
#include <iostream> 
#define N 100 
 
using namespace std;  
 
int b[N]={0};    // An array that stores data   
int n=0;      // Total number of recorded data [ 0 The unit don't , The actual number of elements is zero (n-1) A.  
 
void Swap(int *x,int *y){ 
  int t; 
  t=*x; 
  *x=*y; 
  *y=t; 
}  
 
void Adjust(){ 
  int p;         // Record parent   
  int tag=1;       // Record whether or not it has been tuned to the large root heap ( Signature variable ) 
  while(tag){       // Determine if you have tuned to the large root heap  
    p=(n-1)/2;     // The last 1 The index of two parent nodes  
    tag=0;       // And when you do that, tag=1, Indicates that it has not been adjusted to the large root heap, otherwise continue to adjust   
    while(p>0){     // Make sure you have a parent node  
      if(b[p]<b[2*p]){     // If the root is greater than the left child, we swap   
        Swap(&b[p],&b[2*p]); 
        tag=1; 
      } 
      if(2*p+1<n && b[p]<b[2*p+1]){ // If there is a right child, and the root is larger than the right child, then we swap   
        Swap(&b[p],&b[2*p+1]); 
        tag=1;      
      } 
      p--;        // Until the last 1 We're done at four parent nodes   
    }  
  }  
} 
 
void HeapSort(){ 
  while(n>2){         // There are guaranteed to be parent nodes   
    Adjust();        // Adjust the big root heap function  
    Swap(&b[1],&b[n-1]);  // Will be the last 1 The leaves and the roots are swapped   
    n--;          // Crop the last leaf node   
  } 
}   
    
int main(void){ 
  int i,m; 
  cout<<" Please enter the total number of data [ 0 The unit don't , The actual number of elements is zero (n-1) A. :"<<endl; 
  cin>>n; 
  m=n; 
  cout<<" Please enter each data [ 0 The unit don't , The actual number of elements is zero (n-1) A. :"<<endl; 
  b[0]=0; 
  for(i=1;i<n;i++){ 
    cin>>b[i]; 
  } 
  HeapSort();           // Heap sort  
  cout<<" The large root heap is arranged in ascending order as :"<<endl; 
  for(i=1;i<m;i++){ 
    cout<<b[i]<<" "; 
  }  
  cout<<endl; 
  return 0; 
} 

Thank you for reading, I hope to help you, thank you for your support of this site!