typedef int E;

typedef struct node{
    E data;
    struct node* next;
}Node;

typedef struct{
    Node* head;
    Node* tail;    
    int size;
}List;

//API
List* list_create(void);
void list_destroy(List* list);

//插入
void add_before_head(List* list, E val);
void add_behind_head(List* list, E val);
void add_node(List* list, int idx, E val)

#include"List.h"
#include<stdio.h>
#include<stdlib.h>

//API
List* list_create(void){
    return calloc(1,sizeof(List)); //创建并清零
}

void list_destroy(List* list);

//头插法
void add_before_head(List* list, E val){
    //1.创建新节点
    Node* new_node = malloc(sizeof(Node));
    if(!new_node){
        printf("Error:malloc failed in add_before_head");
        exit(1);
    }
    //2.初始化节点
    new_node -> data = val;
    new_node -> next = list->head;
    //3.更新链表的信息
    list->tail = new_node;
    if(list->tail == NULL){
		list->tail = new_node;
    }
    list->size++;
}

void add_behind_head(List* list, E val){
    //1.创建新节点
    Node* new_node = malloc(sizeof(Node));
    if(!new_node){
        printf("Error:malloc failed in add_behind_head");
        exit(1);
    }
    //2.初始化节点
    new_node -> data = val;
    new_node-next = NULL;
    //new_node -> next = list->NULL;空指针解引用异常
    //3.链接到尾部
   	if(list->tail == NULL){
        list->head = new_node;
        list->tail = new_node;
    }else{
        list->tail->next = new_node;
        list->tail = new_node;
    }
    //4.更新链表的信息
    list->tail = new_node;
    if(list->tail == NULL){
		list->tail = new_node;
    }
    list->size++;
}


void add_node(List* list, int idx, E val){
    //参数校验
    if(idx < 0 || idx > list->size){
        printf("Error:Illegal Argument: idx = %d, size = %d\n", idx, list-> size);
        exit(1);
    }
    if(idx = 0){
        add_before_head(list,val);
        return;
    }
    if(idx == list->size){
        add_behind_tail(list,val);
    }
    //在链表的中间插入
    //找索引为idx-1的节点
    //循环不变式，current和i对应
    //进入循环体前一直不变的关系
    Node* curr - list -> head;
    for(int i = 0; i < idx-1; i++){
 		curr = curr->next;       
    } // i = idx - 1,curr指向索引为idx-1的节点
    //再curr后添加节点
    //1.创建新节点
    Node* new_node = malloc(sizeof(Node));
    if(!new_node){
        printf("Error:malloc failed in add_behind_head");
        exit(1);
    }
    //2.初始化节点
    new_node -> data = val;
    new_node-next = curr->next;
    //3.链接
    curr->next = new_node;
    //4.修改链表的信息
    list->size++;
    }
}

#include"List.h"
//单元测试
int main(void){
    List* list = list_create();
    add_before_head(list,1);
    add_before_head(list,1);
    add_before_head(list,1);
    add_before_head(list,1);
    
    return 0;
}

[*][D][*] <====> [*][D][*] <====> [*][D][*] 

Eg1.
   input: 1-->2-->3
  output: 2
Eg2.
   input: 1-->2-->3-->4
  output: 3

[1][*]--->[2][*]--->[3][*]--->[4][*]---->NULL


                     <----------- ^
                     |            |
[1][*]--->[2][*]--->[3][*]--->[4][*]


  <------------------------------ ^
  |                               |
[1][*]--->[2][*]--->[3][*]--->[4][*]

bool hasCycle(struct ListNode *heaed);

struct ListNode* revereseList(struct ListNode* head);

Eg1.
   input: 1-->2-->3
  output: 3-->2-->1
Eg2.
   input: 1
  output: 1

Eg1.
   input: 1-->3-->5
          2-->4-->6
  output: 1-->2-->3-->4-->5-->6
Eg2.
   input: 1-->2-->3-->4
          6-->7-->8
  output: 1-->2-->3-->4-->6-->7-->8

    |_____|栈顶(只能在栈顶操作)
    |_____|  
    |_____|
    |_____|
    |_____|栈底

    [ ][*]-->[ ][*]-->[ ][*]-->[ ][*]
     ^                          
     |                          
  top[栈顶]

                             ┌────────hash桶-[]
                             |
[Key的取值范围]---取出key--->hash函数────hash桶-[]-[]
                             |
                             └────────hash桶(容器)

checksam:
     256bit
      [ ]─────────────────>[ ]
       A              	    B
md5──>md5码(256b)    md5──>md5码(256b)
       |                    |
      指纹                验证指纹

//size 是key-val键值对的个数
//hashseed 用于保证安全性
   
   table[*]------>[*][*][*][*][*][*][*][*]
    size[ ]           |
capacity[ ]         [key]
hashseed[ ]         [val]
                     [*]
                      |
                    [key]
                    [val]
                     [*]

//Hashmap.c
typedef struct{
    Node** table;
    int size;
    int capacity;
    uint32_t hashseed;
}HashMap;

//
#icnlude<stdio.h>
#include"Hashmap.h"

int main(void){
    //1.创建空的哈希表
    HashMap* map = hashmap_create();
    hashmap_put(map,"liuqiangdong","zhangzetian");
    hashmap_put(map,"wangbaoqiang","marong");
    hashmap_put(map,"wenzhang","mayiliang");
    hashmap_put(map,"jianailiang","lixaolu");
    return 0;
}

#include<hashmap.h>
#include<time.h>
#define DEDAULT_CAPACITY
typedef char* V;
HashMap* hasmap_create(void){
    HashMap* map = malloc(sizeof(HashMap));
    if(!map){
        //错误处理
    }
    //NULL用calloc
    map->table = calloc(DEFAULT_CAPACITY,sizeof(Node*));
	map->size = 0;
    map->capacity = DEFAULT_CAPACITY;
    map->hashseed = time(NULL);
    
    return map;
}

// 如果key不存在，添加key-val,并返回null
// 如果key存在，更新key关联的val，并返回原来的val
V hashmap_put(HashMap* map, K key, V val){
    int idx = hash(key,strlen(key),map->hashseed)%map->capacity;  //求得索引(hash桶)
    //遍历链表
    Node* curr = map->table[idx]; //table中的第一个元素是链表的地址
    while(curr){
        if(strcmp(curr->key,key) == 0){
            //更新Key关联的值，并返回原来的值
            V oldval val = curr->val;
            curr->val = val;
            return oldval;
        }
        curr = curr->next;
    }// curr == NULL
    //添加Key-val,并返回null;用头插法
    Node* newnode = malloc(sizeof(Node));
    
    newnode->key = key;
    newnode->val = val;
    newnode->next = map->table[idx];
    //链接过程
    map->table[idx] = newnode;
	//更新hash表的信息
    map->size++;
    return NULL;
}


//根据Key，获取关联值，如果Key不存在，返回NULL
V hashmap_get(HashMap* map, K key){
  	int idx = hash(key,strlen(key), map->hashseed) % map->capacity;
    Node* curr = map->table[idx];
    while(curr){
        if(strcmp(curr->key,key) == 0){
            return curr->val;
        }
        curr = curr->next;
    }
    return NULL;
}

//删除键值对，如果Key不存在，什么也不做
void hashmap_delete(HashMap* map, K key){
    int idx = hash(key,strlen(key),map->hashseed)%map->capacity;
    Node* prev = NULL;
    Node* curr = map->table[idx];
    while(curr){
        if(strcmp(curr->key, key) == 0){
            // todo: 删除curr节点
            	if(prev == NULL){
                    map->table[idx] = curr->next;
                }else{
                    prev->next = curr->next;
                }
            	free(curr);
            	map->size--;
            	return;
        }
        prev = curr;
        curr = curr->next;
    }
}


//销毁hash表
void hashmap_destroy(HashMap* map){
    for (int i = 0; i < map->capacity; i++){
        Node* curr = map->table[i];
        while(curr){
            Node* next = curr->next;
            free(curr);
            curr = next;
        }
        //释放动态数组
        free(map->table);
    }
    free(map);
}
    

L = size/capacity
要保证L不超过一个一个常 数(L<=1或L<=0.75)
                   |
              load factor
                负载因子

 BitMap
 
array[*]---->[][][][][][]
 bits[ ]

//bitmap.h
#include<stdint.h>
#include<stdlib.h>
typedef struct{
    uint32_t* array;  //动态数组，放在堆上，大小要确定（32bits）,2.无符号整数
    size_t btis;  //位图的长度
}BitMap;

//API
BitMap* bitmap_create(size_t bits);
void bitmap_destroy(BitMap* bm);

void bitmap_set(BitMap* bm, size_t n);
void bitmap_unset(BitMap* bm, size_t n);
void bitmap_isset(BitMap* bm, size_t n);
void bitmap_clear(BitMap* bm);

//bitmap.c
#include<bitmap.h>
#include<stdio.h>

#define BITS_PER_WORD 32
#define BITMAP_SHIFT 5
#define BITMAP_MASK 0X1F

// 存储bits,需要word的长度，因为空间申请是按字申请
#define BITMAP_SIZE(bits) ((bits + BITS_PER_WORD -1) >> BITMAP_SHIFT)  //要向上取整

// bits: 位图的长度
// bits = 100
// 100 / 32 + 1  = (100 + 32 -1) / 32
// 1 + (32 - 1) / 32
BitMap* bitmap_create(size_t bits){
    BitMap* bm = malloc(sizeof(BitMap));
    bm->array = calloc(BITMAP_SIZE(bits) ,BITS_PER_WORD >> 3); 
    //乘除2的幂，考虑位运算
    bm->bits = bits;
    return bm;
}

//扩充位图，能够存下Bits位
void grow_capacity(BitMap* bm, size_t bits){
    //位图：内存紧凑的数据结构，应尽可能少的减少扩充空间
    //扩容策略，需要多大，就申请多大的内存空间,可以考虑使用relloc函数
    uint32_t* new_array = realloc(bm->array, BITMAP_SIZE(bits)*(BITS_PER_WORD >> 3);
    if(!new_array){
        printf("Error:failed to allocate in new_array");
        exit(1);
    }
    bm->array = new_array;
    //将扩充的部分置为0
    int bytes = (BITMAP_SIZE(bits) - BITMAP_SIZE(bm->bits)) * (BITS_PER_WORD>>3);
    memset(bm->array + BITMAP_SIZE(bm->bits),0,bytes);
}

//设置索引为n的位
//100, 32 * 4 = 128 
void bitmap_set(BitMap* bm, size_t n){
    if(n+1 > bm->bits){    
        if(BITMAP_SIZE(n+1) > BITMAP_SIZE(bm->bits)){
        //扩容
        	grow_capacity(bm,bits);
    	}
        bm->bits = n + 1;
    }

    //容量足够，直接设置第n位
    //如何表示第n位(word, offset) 在哪个字，偏移值
	size_t word = n >> BITMAP_SHIFT;
    size_t offset = n % 32;  //等价于 n & 0x1F  11011 00 10000
    bm->array[word] |= (0x1 << offset);  // 与其进行0001 000或运算
}
                                  
                                  
void bitmap_unset(BitMap* bm, size_t n){
    //找到第n位
    if(n >= b->bits){
        return;
    }
    size_t word = n >> BITMAP_SHIFT;
    size_t offset = n & BITMAP_MASK;
    bm->array[word] & = ~(0x1 << offset); 
}
                                  
void bitmap_isset(BitMap* bm, size_t n){
    //找到第n位
    if(n >= bm->bits){
        return false;
    }
    //找到第n位
    size_t word = n >> BITMAP_SHIFT;
    size_t offset = n & BITMAP_MASK;
    return bm->array[word] & (0x1 << offset); /*000001000*/; 
}
                                  
void bitmap_clear(BitMap* bm){
    size_t bytes = BITMAP_SIZE(bm->bits)*sizeof(Word);
    memset(bm->array, 0x00, bytes); 
}

                                              长度    
memset(bm->array + BITMAP_SIZE(bm->bits), 0, bytes);
                     起始地址              |  
                                     每一个字节的值（0~0xFF）

//测设单元 main.c
#include "BitMap.h"

int main(void){
    BitMap* bm = bitmap_create(100);
    bitmap_set(bm, 9);
    bitmap_set(bm, 5);    
    bitmap_set(bm, 2);
    bitmap_set(bm, 7);
    
    bitmap_set(bm, 128);
    return 0;
}

         BST    [*]
                 |            
            [*][key][*]
            /          \
       [*][key][*]  [*][key][*]   

typedef int K;
typedef struct tree_node{
    K key;
    struct tree_node* left;
    struct tree_node* right;
}TreeNode;

//typedef TreeNode* BST; 给指针定义别名的方法，灵活性过差，不易扩展其它信息

typedef struct{
    TreeNode* root;
}BST;

//API
#include<stdlib.h>
#include<stdio.h>

//创建一棵空树
BST* bst_create(void){
    return calloc(1,sizeof(BST)); //使用了Calloc返回NULL值
}

//如果key存在，什么也不做,查找路径类似单链表，插入用尾插法
//如果Key不存在，则添加Key
BST* bst_insert(BST* tree,K key){
    TreeNode* parent = NULL;
    TreeNode* curr = tree->root;
    int cmp = 0;
    while(curr){
        cmp = key - curr->key
        if(cmp < 0){
            parent = curr;
            curr = curr->left;
        }else if(cmp > 0){
            parent = curr;
            curr = curr->right;
        }else{
            //相等的情况，说明已经存在，直接返回
            return;
        }
    }//curr == NULL
    //插入节点
    TreeNode* node = malloc(sizeof(TreeNode));
    node->key = key;
    //链接到树中
    if(parent == NULL){
        tree->root = node;
    }else if(cmp < 0){
        parent->left  = key;
    }else if(cmp < 0){
        parent->left  = key;
    }else{
        return;
    }
}

BST* bst_search(BST* tree,K key){
    TreeNode* curr = tree->root;
    while(curr){
        int cmp = key - curr->key;
        if(cmp < 0){
            curr = curr->left;
        }else if(cmp > 0){
            curr = curr->right;
        }else{
            return curr;
        }
    }//curr == NULL的情况
    return NULL;
}

//中序遍历内部细节
void inorder(TreeNode* root){
    //a.边界条件
    if(root == NULL){
        return;
    }
    //b.递归公式
    //遍历左子树
    inorder(root->left);
    //遍历根节点
    printf("%d ",root->key);
    //遍历右子树
    inorder(root->right);
}

//中序遍历对外的API
void bst_inorder(TreeNode* tree){
    //委托给inorder，外包
    inorder(tree->root);
    printf("\n");
}

//层次遍历
void bst_levelorder(BST* tree){
    //1.创建队列
    Queue* q = queue_create();
    //2.将根节点入队列
    queue_push(q, tree->root);
    //3.循环遍历
    while(queue_empty){
        //出队列
        TreeNode* node = queue_pop(q);
        //遍历该节点
        printf("%d ", node->queue->key);
        //判断该节点是否有左孩子
        if(node->left){
            queue_push(q,node->left);
        }
        if(node->right){
            queue_push(q,node->right);
        }
    }// queue_empty(q) == true
    printf("\n");
}

BST* bst_delete(BST* tree,K key){
    //1.查找要删除的节点
    TreeNode* parent = NULL;
    TreeNode* curr = tree->root;
    while(curr){
        int cmp = key - curr->key;
        if(cmp < 0){
        	parent = curr;
            curr = curr->left;
        }else if(cmp > 0){
            parent = curr;
            curr = curr->right;
        }else{
            //TODO:删除curr节点
            //代码缩进的层次越高，代码的复杂度越高
            break;
        }
    }//curr == NULL，不用进行任何操作
    if(curr == NULL) return;
    if(curr->left && curr->right){
        //退化成degree == 0 || degree == 1
        TreeNode* p = curr;
        TreeNode* min = curr->right;
        while(min->left){
            p = min;
            min = min->left;
        }//min->left == NULL;
        
		curr->key = min->key;
        parent = p;
        curr = min;
    }
    // 统一处理（degree == 0 || degree == 1）
    // 删除curr节点
    TreeNode* child = curr->left > curr->right ? curr->left : curr->right;  //找到唯一的孩子
    
    if(parent == NULL){
        tree->root = child;
    }else{
        int cmp = curr->key - parent->key;
        if(cmp < 0){
            parent->left = child;
        }else if(cmp > 0){
            parent->right = child;
        }else{
            parent->right = child
        }
        free(p);
    }
}

BST* bst_destroy(BST* tree);


//测试单元
int main(){
   BST* tree = best_create();
    
   bst_insert
}

  [   ]      []     [ ]
  / | \     [] \    / []
            /\         \
            

  [     ]       [ ]     
  / | | \       / \
              [ ] [ ]    
              / \ / \       

#define SIZE(a) (sizeof(a)/sizeof(a[0]))

int bsearch(int arr[], int left, int right, int key){
    //边界条件
    if(left > right) return -1; 
    //递归公式
    int mid = left + (right - left >> 1);
    int cmp = key - arr[mid];
    
    if(cmp < 0) return bsearch(arr, left, mid - 1, key);
    if(cmp > 0) return bsearch(arr, mid + 1, right, key);
    return mid;
}

//递归方法
int binary_search1(int arr[], int key){
    //闭区间：[0,n-1]
    return bsearch(arr, 0, n-1, key);
}


//循环方法
int binary_search2(int arr[], int key){
    //闭区间：[0,n-1]
	int left = 0, right = n - 1;
    while(left <= right){//注意事项1：left <= right注意等号要不要加
        int mid = left + (right - left >> 1);   //注意事项2
        int cmp = key - arr[mid];
        if( cmp < 0 ){
            right = mid - 1;   //注意事项3
        }else if(cmp > 0){
            left = mid + 1;   //注意事项4
        }else{
            return mid;
        }
    }//left > right
    return -1;
}



//查找第一个和key值相等的元素
int binary_search3(int arr[], int key){
    //闭区间：[0,n-1]
	int left = 0, right = n - 1;
    while(left <= right){//注意事项1：left <= right注意等号要不要加
        int mid = left + (right - left >> 1);   //注意事项2
        int cmp = key - arr[mid];
        if( cmp < 0 ){
            right = mid - 1;   //注意事项3
        }else if(cmp > 0){
            left = mid + 1;   //注意事项4
        }else{
            //if(是第一个和key相等的元素){
            if(mid == left || arr[mid - 1] < key){  
            	return mid;
            }
            right = mid - 1;
        }
    }//left > right
    return -1;
}

//查找第一个大于等于key值相等的元素
int binary_search4(int arr[], int key){
    //闭区间：[0,n-1]
	int left = 0, right = n - 1;
    while(left <= right){//注意事项1：left <= right注意等号要不要加
        int mid = left + (right - left >> 1);   //注意事项2
        
        int cmp = key - arr[mid];
        if( cmp < 0 ){
            left = mid + 1;
        }else{
            if(时第一个大于等于key的元素){
                return mid;
            }
            right = mid - 1;
        }
    }//left > right
    return -1;
}



int main(void){
    int arr[] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90};
    return 0;
}

16 1 45 23 99 2 18 67 42 10
i  min_idx

#include<stdio.h>

void insertion_sort(int arr[], int n){
	for(int i = 1; i < n; i++){
        //i表示要插入元素的索引
        int value = arr[i];
        int j = i - 1;
        while(j >= 0 && arr[j] > value){
            arr[j+1] = arr[j]; 
            j--;
        }  //j == 1 || arr[j] <=value
        arr[j + 1] = value;
    }
    print_array(arr, n);
}


void print_array(int arr[], int n){
    for(int i = 0; i < n; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main(void){
    int arr[] = {3, 6, 4, 2, 11, 10, 5 };
    return 0;
}

void shell_sort(int arr[], int n){
    //gap序列：n/2,n/4;
    int gap = n >> 1;
    while(gap){
        //组件插入排序(gap个人轮流抓牌)
        for(int i = gap; i < n; i++){
            //排堆，（gap,n）
            int value = arr[i];
            //保证自己的手牌有序
           	int j = i - gap;
            while(j >= 0 && arr[j] > value){
                arr[j+gap] = arr[j];
                j - = gap;
            }// j < 0 || arr[j]<=value
            arr[j + gap] = value;
        }
        //查看流程
    	print_array(arr, n);
    	gap >>= 2;
    }
    gap >> = 1;
}

            [38][27][43][3][9][82][10]         O(n)
··· 递
         [38][27][43][3]       [9][82][10]       O(n)
          
       [38][27]  [43][3]     [9][82]   [10]       O(n)
       
     [38]  [27]  [43]  [3]  [9]  [82]   [10]       O(n)
···· merge
       [27][38]  [3][43]     [9][82]   [10]        O(n)
       
         [3][27][38][43]       [9][10][82]        O(n)
            
            [3][9][10][27][38][43][82]          O(n)

#include<stdio.h>
#define SIZE(a) (sizeof(a)/sizeof(a[]))

void print_array(int arr[], int n){
    for(int i = 0; i < n; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int tmp[N];

void merge(int arr[], int left, int mid, int right){
    // 左：[left, mid]
    // 右：[mid+1,right]
    int i = left, j = mid + 1, k = left;
   	
    while(i <= mid && j <= right){
        if(arr[i] <= arr[j]){
            tmp[k++] = arr[i++];
        }else if{
            tmp[k++] = arr[j++];
        }
    }
    
    while(i <= mid){
        tmp[k++] = arr[i++];
    }
    
    while(j <= right){
        tmp[k++] = arr[j++];
    }
    
    //将tmp数组的对应区间，复制到arr数组中
    for(int k = left; k <= right; k++){
        arr[k] = tmp[k];
    }
}

void m_sort(int arr[], int left, int right){
    //边界条件
    if(left >= right) return;
    //递归公式
    int mid = left + (right - left >> 1);
    //对左边区间进行排序
    m_sort(arr, left, mid);
    //对右边区间排序
    m_sort(arr, mid+1, right);
    //归并操作
    merge(arr, left, mid, right);
}

void merge_sort(int arr[], int n){
    m_sort(arr, 0, n - 1);
}

int main(void){
 	int arr[N] = {38, 27, 43, 3, 9, 83, 20};   
    return 0;
}

#include<stdio.h>
#define SIZE(a) (sizeof(a)/sizeof(a[0]))

void partition(int arr[], int left, int right){
    //1.选取基准值
    int pivot = arr[left];
    //2. 双向分区
    int i = left, j = right;
    while(i < j){
        // 先移动j，找<pivot的元素
        while(i < j && arr[j] >= pivot){
            j--;
        }// i == j || arr[j] < pivot
        arr[i] = arr[j];
        
        //再移动i，找>pivot的元素
        while(i < j && arr[j] <= pivot){
            i++;
        }// i == j || arr[j] < pivot
        arr[j] = arr[i];
    } // i == j
    arr[i] = pivot;
    return i;
}

void q_sort(int arr[], int left, int right){
    //边界条件
    if(left >= right) return;
    //递归公式
    //1.分区
    int idx = partition(arr, left, right);
    //2.对左边区间进行排序
    q_sort(arr, left, idx-1);
    //3.对右边区间排序
    q_sort(arr, idx+1, right);
}

void quick_sort(int arr[], int n){
    //通过委托实现
    q_sort(arr, 0, n-1);
}


int main(){
	int a[N] = {3, 7, 8, 5, 2, 1, 9, 5, 4}    
    
}

数组 

16 1 45 23 99 2 18 67 42 10

将数组看作一颗二叉树

          16
       /      \
      1        45
    /   \      /  \  
   23    99   2   18
  / \    /
 67  42 10
 
 parent(i) = (i-1)/2
 lchild(i) = 2i+1
 rchild(i) = 2i+2

#include<stdio.h>
#define SIZE(a) (sizeof(a)/sizeof(a[0]))
#define SWAP(arr, i, j){ \
	int t = arr[i];
	arr[i] = arr[j];
	arr[j] = t;
}

void heapify(int arr, int i, int n){
    while(i < n){
        // 求三个元素的最大值
        int lchild = 2 * i + 1;
        int rchild = 2 * i + 2;
        int maxId = i;
        if(lchild < n && arr[lchild] > arr[maxIdx]){
            maxIdx = lchild;
        }
        if(rchild < n && arr[rchild] > arr[maxIdx]){
        	maxIdx = rchild;
        }
        //如果最大值是根节点，调整结束
        if(maxIdx == i) break;
        //如果不是，交换根节点和最大直接点
        SWAP(arr, i, maxIdx);
        //调整maxIdx节点
        i = maxIdx;
    }
}

void build_heap(int arr[], int n){
    //从后往前依次构建大顶堆
    //找到第一个非叶子节点: lchild(i) = 2i+1 <= n -1; => i<= ( n - 2 >> 1)
    for(int i = ( n - 2 >> 1); i >= 0; i--){
        heapify(arr, i, n);
    }
}

void heap_sort(int arr[], int n){
    //1.构建大顶堆
    build_heap(arr,n);　　　
    print_array(arr,n);
    //2.初始化无序区的长度
    int len = n;
    //3.交换堆顶元素和无序区最后一个元素,直到len == 1
    while(len > 1){
        SWAP(arr, 0, len-1);
        len--;
        heapify(arr, 0, len);
        print_array(arr,n);
    }
}

int main(void){
    return 0;
}