C语言实现小根堆

发表于 更新于 阅读次数：
本文字数： 3.9k 阅读时长 ≈ 4 分钟

数据结构有 堆排序 ，但 堆排序 在众多排序算法中的能力并不突出，这是因为排序并不体现 堆 的优势，而只能算是它附带的能力。

堆 的优势在于当从 堆 中弹出最小值（针对 小根堆 而言）时，或将某个数值放入 堆 中时，相比其他数据结构，它需要检索和调整其他数据元素的操作最少，效率最优，所以它更适合用来实现 优先队列，因为 优先队列 每次只会获取队列中优先级最高的数据元素，而不会操作其他数据元素，这和 小跟堆 每次只能弹出最小值而不能弹出其他值的行为一致。因此如 Dijkstra 算法在面临规模上万的顶点个数的时候，其内部权值检索环节采用 优先队列 实现的话能显著提升算法效率。除 Dijkstra 算法外，还有像 Huffman 树的构建过程中，需要频繁从当前森林中获取根节点权值最小的树，直到森林中只剩一棵树为止，这个过程若采用 优先队列 也能显著改善性能，总之， 优先队列 在各类算法中的应用非常广泛。

堆通过两个关键性操作 shift up（上浮）和 shift down （下沉）维护堆内数据，shift up 用于往堆中插入新的数据元素，shift down 用于从堆中弹出数据元素。

以下是我用C语言实现的 小根堆 的完整代码，以供参考。

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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
/********************************************
* Min-Heap
* Copyright (C) i@foxzzz.com
*
* C implementation of the Min-Heap.
*********************************************/

#define _CRT_SECURE_NO_WARNINGS /*for visual studio*/

#include <stdio.h>
#include <memory.h>
#include <malloc.h>
#include <assert.h>

/*!
* @brief 堆结构体
* @data 数据元素
* @capacity 数组容量
* @len 元素数量
*/
typedef struct _tHeap {
    int* data;
    int capacity;
    int len;
} Heap, * pHeap;

/*!
* @brief 创建堆结构体
* @param[in] capacity 指定数组容量
* @return 空指针失败 其他成功
*/
pHeap createHeap(int capacity) {
    pHeap heap = (pHeap)malloc(sizeof(Heap));
    assert(heap);
    assert(capacity > 0);
    memset(heap, 0, sizeof(Heap));
    heap->capacity = capacity;
    heap->data = (int*)malloc(sizeof(heap->data[0]) * heap->capacity);
    assert(heap->data);
    return heap;
}

/*!
* @brief 销毁堆结构体
* @param[in] heap 需要销毁的结构体指针
*/
void destroyHeap(pHeap heap) {
    if (heap) {
        if (heap->data) {
            free(heap->data);
            heap->data = NULL;
        }
        free(heap);
    }
}

/*!
* @brief 元素上浮
* @param[in] heap 需要操作的堆结构指针
* @param[in] position 指定要上移的元素
*  - position 是元素编号，所以对应到数组元素时候需要 -1
*/
void shiftUp(pHeap heap, int position) {
    while (position >> 1) {
        int parent = position >> 1;
        /*与父元素进行比较，如果大于父元素则进行交换*/
        if (heap->data[parent - 1] > heap->data[position - 1]) {
            int temp = heap->data[parent - 1];
            heap->data[parent - 1] = heap->data[position - 1];
            heap->data[position - 1] = temp;
            position = parent;
        } else break;
    }
}

/*!
* @brief 元素下沉
* @param[in] heap 需要操作的堆结构指针
* @param[in] position 指定要下沉的元素
*  - position 是元素编号，所以对应到数组元素时候需要 -1
*/
void shiftDown(pHeap heap, int position) {
    while (position << 1 <= heap->len) {
        int target = position << 1;
        /*指定左右孩子中的较小者*/
        if (target + 1 <= heap->len) {
            if (heap->data[target] < heap->data[target - 1]) {
                target += 1;
            }
        }
        /*父节点大于较小者则交换*/
        if (heap->data[position - 1] > heap->data[target - 1]) {
            int temp = heap->data[target - 1];
            heap->data[target - 1] = heap->data[position - 1];
            heap->data[position - 1] = temp;
            position = target;
        } else break;
    }
}

/*!
* @brief 插入元素
* @param[in] heap 需要操作的堆结构指针
* @param[in] v 需要插入的元素
*/
void insertHeap(pHeap heap, int v) {
    /*容量满了按1倍扩容*/
    if (heap->capacity == heap->len) {
        heap->capacity <<= 1;
        heap->data = (int*)realloc(heap->data, heap->capacity);
        assert(heap->data);
    }
    /*插入到堆尾*/
    heap->data[heap->len++] = v;
    /*调整堆结构，对堆尾元素进行上浮*/
    shiftUp(heap, heap->len);
}

/*!
* @brief 返回对顶元素，此操作要求堆不为空
* @param[in] heap 需要操作的堆结构指针
* @return 返回对顶元素
*/
int topHeap(pHeap heap) {
    return heap->data[0];
}

/*!
* @brief 弹出对顶元素
* @param[in] heap 需要操作的堆结构指针
*/
void popHeap(pHeap heap) {
    if (heap->len > 0) {
        /*将堆尾元素放入堆顶*/
        heap->data[0] = heap->data[heap->len - 1];
        --heap->len;
        /*调整堆结构，对新的堆顶元素进行下沉*/
        shiftDown(heap, 1);
    }
}

int main() {
    /*create heap*/
    pHeap heap = createHeap(16);

    /*insert value*/
    insertHeap(heap, 3);
    insertHeap(heap, 1);
    insertHeap(heap, 4);
    insertHeap(heap, 7);
    insertHeap(heap, 6);
    insertHeap(heap, -4);

    /*pop value & print*/
    while (heap->len) {
        int v = topHeap(heap);
        popHeap(heap);
        printf("%d ", v);
    }

    /*destroy heap*/
    destroyHeap(heap);
    return 0;
}