Detailed explanation of heap sort code

  Figure displaying the heap

• The heap is a complete binary tree ;

• The value of each node in the heap must be greater than or equal to （ Or less than or equal to ） Of each node in its subtree value .

  The left side is the big top pile         The right side is a small top pile

  The following code establishes the big top heap

	#include "stdio.h"
	# define MAXSIZE 10
	
	typedef struct {
	    int r[MAXSIZE];             /*  use   On   save   Store   want   row   order   Count   Group   */
	    int length ;                /*  use   On   remember   record   along   order   surface   Of   Long   degree  */
	}SqList ;
	
	
	void swap ( SqList *L, int i, int j){           /*  hand over   in  L  in   Count   Group  r  Of   Next   mark   by  i  and  j  Of   value  */
	    int temp = L->r[i];
	    L->r[i] = L->r[j];
	    L->r[j] = temp;
	}
	
	
	void HeapAdjust(SqList* L,int s,int m){         /*  Structure L The location of , The location of the first judgment node s, The number of nodes m */
	     int temp , j;
	     temp = L->r[s];                            /*  Pass to temp Location s Value on  */
	     for (j = 2*s;j <= m;j *= 2) {              /*  Compare positions s And its two children  */
	         if (j < m && L->r[j] < L->r[j+1])      /*  First find s My two children , Find out the larger value of children  */
	            ++j;                                /* j The following table shows older children  */
	         if ( temp >= L->r[j])                  /*  If temp Big   be   The current structure remains unchanged  */
	             break ;                            /* r[c]  Should be   insert   Enter into   stay   position   Set up  s  On  */
	
	         L->r[s] = L->r[j];                     /*  Otherwise, assign the maximum value to s position  */
	         s = j;                                 /*  by   L->r[s] = temp  Do matting  */
	     }
	     L->r[s] = temp;                            /*  The last step  */
	
	}
	
	
	void HeapSort(SqList* L){                        /*  For the sequence table L Make a heap sort  */
	    int i;
	    for (i = L->length/2; i > 0; i--)            /*  hold  L  in   Of  r  structure   build   become   One   individual   Big   The top   Pile up  */
	        HeapAdjust (L,i,L->length) ;             /*  Afferent structure L The location of    The location of the first judgment node i   The number of nodes length */
	
	    for(i=0;i<MAXSIZE;i++){                      /*  View the result after heap  */
	        printf("%d  ",L->r[i]);
	    }
	    printf("\n");
	
	    for (i = L->length; i > 1; i--) {
	        swap (L, 1 , i) ;                      /*  Put the maximum value at the top of the heap at the end of the array ,i-1  Then he won't participate in the heap process  */
	        HeapAdjust (L, 1 , i-1);           /*  Structure L The location of , Location of the first node s, The number of nodes m */
	
	        for(int j=0;j<MAXSIZE;j++){              /*  Check out the process  */
	            printf("%d--",L->r[j]);
	        }
	        printf("\n");
	
	
	    }
	}
	
	int main(){
	    int i;
	    int a[9]={50,10,90,30,70,40,80,60,20};        /*  initialization  */
	
	    SqList L;
	    L.length=MAXSIZE-1;                           /*   The key : r[0] No need   and   The effective length needs to be reduced from the base     1   */
	    L.r[0]=9999999;
	    for(i=1;i<MAXSIZE;i++){
	        L.r[i]=a[i-1];                            /* r[0] No need  */
	    }
	
	
	    for(i=0;i<MAXSIZE;i++){
	        printf("%d  ",L.r[i]);             /*   Check the original sorting   */
	    }
	    printf("\n");
	
	    HeapSort(&L);                                  /*  Heap up  */
	
	    for(i=0;i<MAXSIZE;i++){                        /*  View the sorted results  */
	        printf("%d  ",L.r[i]);
	    }
	    return 0;
	}