堆的插入，删除，创建C语言实现_4.8.12.18.20.40.35.37小根堆插入数c语言

温故而知新。。。昨天刚学了堆的网课，今天就迫不及待地要自己用代码实现了（有人可能会问为什么不昨天实现呢，这肯定不是因为懒，增加一下难度）。
堆地简介：结构上是数组形式地完全二叉树（特性：第i个节点的左子树为ix2右子树为ix2+1）
顺序上：任一父节点大于左右节点（最大堆），堆也可以解释为优先队列，比如操作系统的进程调度里就有其应用（一般情况下优先级最高的最先执行）。。。

//堆（优先队列，用来处理具有优先级特性的数据）
//特性：父节点的全值大于左右节点的权值,结构采用完全二叉数
//常规操作：插入，删除，建立
#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 1000
#define MAX_NUM 1000000
int n;
void recover(int *heap,int i) {//将完全二叉数恢复为堆（最大堆）
    if (i*2+1 <= n) {
        int swap;
        int max = heap[i*2+1] >heap[i*2]?heap[i*2+1]:heap[i*2];
        if (max > heap[i]) {
            if (max == heap[i*2]) {
                swap = heap[i];
                heap[i] = heap[i*2];
                heap[i*2] = swap;
            }
            else if (heap[i*2+1] == max) {
                swap = heap[i];
                heap[i] = heap[i*2+1];
                heap[i*2+1] = swap;
            }
        }
        recover(heap,i*2);
        recover(heap,i*2+1);
    }
}
void create(int *heap) {
    int i;
    heap[0] = MAX_NUM;
    for (i = 1;i <= n;i++) {
        scanf("%d",heap+i);
    }
    i = n/2;//最后一个节点的父节点
    for (int j = i;j > 0;j--) {
        recover(heap,j);
    }
}
void insert(int *heap) {//在最后一位插入，再向上调整
    int num;
    printf("小鬼，请说出你想插入的数字:\n");
    scanf("%d",&num);
    heap[++n] = num;
    int flag = n;
    for (int i = n/2;i > 0;i /= 2) {
        if (heap[i] < heap[flag]) {
            int swap = heap[i];
            heap[i] = heap[flag];
            heap[flag] = swap;
            flag = i;
        }
    }
}
void pri(int *heap) {
    for (int i = 1; i <= n;i++) {
        printf("%d ",heap[i]);
    }
    printf("\n");
}
void delete(int *heap) {//删掉最上面的数，再用末尾的数替换，再恢复
    printf("先说清楚，删掉的数是堆里面最大的那个:%d\n",heap[1]);
    heap[1] = heap[n];
    heap[n--] = 0;
    /*printf("%d\n",heap[1]);*/
    recover(heap,1);
    pri(heap);
}
int main() {
    scanf("%d",&n);
    int *heap = (int *)calloc(MAX_SIZE,sizeof(int)),i;//建堆
    create(heap);
    pri(heap);
    insert(heap);
    pri(heap);
    delete(heap);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

大家一起加油吧。