二叉堆（英语：binary heap）是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。
当父节点的键值总是大于或等于任何一个子节点的键值时为“最大堆”。当父节点的键值总是小于或等于任何一个子节点的键值时为“最小堆”。—-Wikipedia

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
/**
 * @file heap.c
 * @author your name (you@domain.com)
 * @brief 二叉堆，二叉堆一般使用使用数组实现，在逻辑结构上又具有二叉树的特征，
 * 数组下标一般从1开始，这样对于任意的下标为i的非叶子节点，它的左子节点下标是2i,右子节点是2i+1。
 * 如果数组下标从0开始，这样对于任意的下标为i的非叶子节点，它的左子节点下标是2i+1,右子节点是2i+2。
 * @version 0.1
 * @date 2022-04-15
 * 
 * @copyright Copyright (c) 2022
 * 
 */

#include "stdio.h"
#include "stdlib.h"

typedef struct HeapStruct
{
    int capacity;
    int size;
    int* heap;
} HeapStruct;


HeapStruct* initialize(int maxSize)
{
    HeapStruct* h = (HeapStruct*)malloc(sizeof(HeapStruct));
    if (!h)
    {
        printf("out of memory\n");
        return NULL;
    }
    h->capacity = maxSize;
    h->size = 0;
    h->heap = (int*)malloc((maxSize + 1) * sizeof(int)); /**< 加1是因为数组从下标1开始，空间要多一个 */
    if (!h->heap)
    {
        printf("out of memory\n");
        free(h);
        return NULL;
    }
    return h;
}

void deinitialize(HeapStruct* h)
{
    if (h)
    {
        if (h->heap)
        {
            free(h->heap);
        }
        free(h);
    }
}


/**
 * @brief 在堆中插入数据，使用上滤percolate up
 *
 * @param h 
 * @param x 
 */
void insert(HeapStruct* h, int x)
{
    if (h->size == h->capacity)
    {
        return;
    }
    int i = ++h->size;
    for (; (i >> 1) >= 1 && h->heap[i >> 1] > x; i >>= 1)
    {
        h->heap[i] = h->heap[i >> 1];
    }
    h->heap[i] = x;
}


/**
 * @brief 删除最小元素，下滤
 * 上滤或者下滤过程类似于插入排序
 * @param h 
 * @param x 
 */
int deleteMin(HeapStruct* h)
{
    if (h->size == 0)
    {
        printf("no element\n");
        return 0;
    }
    int i;
    int min = h->heap[1];
    int child;
    int lastOne = h->heap[h->size];
    for (i = 1; i * 2 <= h->size;i = child)
    {
        child = i * 2;
        /* 找到左右child中的最小者 */
        if (child < h->size && h->heap[child + 1] < h->heap[child])
        {
            ++child;
        }
        /* 删除的时候，一定会有一个位置空出来，
           使用左右子元素和最后一个元素三者间最小的元素去填充
        */
        if (lastOne > h->heap[child])
        {
            h->heap[i] = h->heap[child];
        }
        else
        {
            break;
        }
    }
    h->heap[i] = lastOne;
    --h->size;
    return min;
}


int main(void)
{
    int array[] = {3,4,1,2,5,7,8,6,5,9,10,5};
    HeapStruct* h = initialize(sizeof(array)/sizeof(int));
    int i = 0;
    for (i = 0; i < sizeof(array)/sizeof(int); ++i)
    {
        insert(h, array[i]);
    }
    for (i = 0; i < sizeof(array)/sizeof(int); ++i)
    {
        printf("%d,", h->heap[i]);
    }
    printf("\n");
    while (h->size > 0)
    {
        printf("%d ", deleteMin(h));
    }
    printf("\n");
    deinitialize(h);
    return 0;
}