堆的性质之类的不再这里阐述,写这个算法只为了更好的理解STL中的堆算法,如果看不懂STL中的算法也可以来参考这里给出的算法,因为是纯C的看起来会省去很多语言方面的细节。同时里面还有一个STL中对应算法的测试以比较两者的效果。

  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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
#include <algorithm>
#include <iostream>
#include <time.h>

using namespace std;

// push_heap为向堆中添加一个新的元素, 调用这个算法的前提是[First, Last)之间的元素满足堆的条件
// 新加入的元素为Last
void    push_heap(int *pFirst, int *pLast);

// pop_heap为从堆中删除一个元素, 调用这个算法的前提是[First, Last)之间的元素满足堆的条件
// 被删除的元素被放置到Last - 1位置,由于这里是max-heap,所以被删除的元素是这个序列中最大的元素
void    pop_heap(int *pFirst, int *pLast);

// make_heap将序列[First, Last)中的元素按照堆的性质进行重组
void    make_heap(int *pFirst, int *pLast);

// 对堆进行排序, 调用这个函数可以成功排序的前提是[pFirst, pLast)中的元素符合堆的性质
void    sort_heap(int *pFirst, int *pLast);

// 判断一个序列[First, Last)是否满足堆的条件,是就返回1,否则返回0
char    is_heap(int *pFirst, int *pLast);

void    test_heap_algo(int *pArray, int nLength);
void    test_heap_algo_in_stl(int *pArray, int nLength);
void    display_array(int *pArray, int nLength);

int main()
{
    srand(time(NULL));
    int Array[10], Array2[10];
    for (int i = 0; i < 10; ++i)
        Array[i] = Array2[i] = rand();

    test_heap_algo(Array, sizeof(Array) / sizeof(int));
    test_heap_algo_in_stl(Array2, sizeof(Array2) / sizeof(int));

    return 0;
}

// 静态函数, 用于根据堆的性质调整堆
static void adjust_heap(int *pFirst, int nHoleIndex, int nLen, int nValue);

// push_heap为向堆中添加一个新的元素, 调用这个算法的前提是[First, Last)之间的元素满足堆的条件
// 新加入的元素为Last
void push_heap(int *pFirst, int *pLast)
{
    int nTopIndex, nHoleIndex, nParentIndex;
    int nValue;

    nTopIndex = 0;
    nHoleIndex = (int)(pLast - pFirst - 1);
    nParentIndex = (nHoleIndex - 1) / 2;
    nValue = *(pLast - 1);
    // 如果需要插入的节点值比父节点大, 上溯继续查找
    while (nHoleIndex > nTopIndex && pFirst[nParentIndex] < nValue)
    {
        pFirst[nHoleIndex] = pFirst[nParentIndex];
        nHoleIndex = nParentIndex;
        nParentIndex = (nHoleIndex - 1) / 2;
    }
    pFirst[nHoleIndex] = nValue;
}

// pop_heap为从堆中删除一个元素, 调用这个算法的前提是[First, Last)之间的元素满足堆的条件
// 被删除的元素被放置到Last - 1位置,由于这里是max-heap,所以被删除的元素是这个序列中最大的元素
void pop_heap(int *pFirst, int *pLast)
{
    int nValue;

    nValue = *(pLast - 1);
    *(pLast - 1) = *pFirst;
    adjust_heap(pFirst, 0, (int)(pLast - pFirst - 1), nValue);
}

// make_heap将序列[First, Last)中的元素按照堆的性质进行重组
void make_heap(int *pFirst, int *pLast)
{
    int nLen, nParentIndex;

    nLen = (int)(pLast - pFirst);
    nParentIndex = (nLen - 1) / 2;

    while (true)
    {
        // 对父节点进行调整, 把父节点的值调整到合适的位置
        adjust_heap(pFirst, nParentIndex, nLen, pFirst[nParentIndex]);
        if (0 == nParentIndex)
            return;
        nParentIndex--;
    }
}

// 对堆进行排序, 调用这个函数可以成功排序的前提是[pFirst, pLast)中的元素符合堆的性质
void sort_heap(int *pFirst, int *pLast)
{
    // 调用pop_heap函数, 不断的把当前序列中最大的元素放在序列的最后
    while (pLast - pFirst > 1)
        pop_heap(pFirst, pLast--);
}

// 判断一个序列[First, Last)是否满足堆的条件,是就返回1,否则返回0
char is_heap(int *pFirst, int *pLast)
{
    int nLen, nParentIndex, nChildIndex;

    nLen = (int)(pLast - pFirst);
    nParentIndex = 0;
    for (nChildIndex = 1; nChildIndex < nLen; ++nChildIndex)
    {
        if (pFirst[nParentIndex] < pFirst[nChildIndex])
            return 0;

        // 当nChildIndex是偶数时, 那么父节点已经和它的两个子节点进行过比较了
        // 将父节点递增1
        if ((nChildIndex & 1) == 0)
            ++nParentIndex;
    }

    return 1;
}

// 一个静态函数仅供adjust_heap调用以证实JJHOU的结论
static void push_heap(int *pFirst, int nHoleIndex, int nTopIndex, int nValue)
{
    int nParentIndex;

    nParentIndex = (nHoleIndex - 1) / 2;
    while (nHoleIndex > nTopIndex && pFirst[nParentIndex] < nValue)
    {
        pFirst[nHoleIndex] = pFirst[nParentIndex];
        nHoleIndex = nParentIndex;
        nParentIndex = (nHoleIndex - 1) / 2;
    }
    pFirst[nHoleIndex] = nValue;
}

// 对堆进行调整, 其中nHoleIndex是目前堆中有空洞的节点索引, nLen是待调整的序列长度
// nValue是需要安插进入堆中的值
static void adjust_heap(int *pFirst, int nHoleIndex, int nLen, int nValue)
{
    int nTopIndex, nSecondChildIndex;

    nTopIndex = nHoleIndex;
    nSecondChildIndex = 2 * nTopIndex + 2;
    while (nSecondChildIndex < nLen)
    {
        if (pFirst[nSecondChildIndex] < pFirst[nSecondChildIndex - 1])
            --nSecondChildIndex;
        pFirst[nHoleIndex] = pFirst[nSecondChildIndex];
        nHoleIndex = nSecondChildIndex;
        nSecondChildIndex = 2 * nHoleIndex + 2;
    }
    if (nSecondChildIndex == nLen)
    {
        pFirst[nHoleIndex] = pFirst[nSecondChildIndex - 1];
        nHoleIndex = nSecondChildIndex - 1;
    }

    // 以下两个操作在这个函数中的作用相同, 证实了<<STL源码剖析>>中P178中JJHOU所言
    //pFirst[nHoleIndex] = nValue;
    push_heap(pFirst, nHoleIndex, nTopIndex, nValue);
}

void test_heap_algo(int *pArray, int nLength)
{
    std::cout << "\ntest_heap_algo()\n";
    make_heap(pArray, pArray + nLength);
    display_array(pArray, nLength);

    push_heap(pArray, pArray + nLength);
    display_array(pArray, nLength);

    pop_heap(pArray, pArray + nLength);
    display_array(pArray, nLength);

    if (is_heap(pArray, pArray + nLength - 1))
    {
        std::cout << "is heap!\n";
    }
    else
    {
        std::cout << "is not heap!\n";
    }

    make_heap(pArray, pArray + nLength);
    display_array(pArray, nLength);

    if (is_heap(pArray, pArray + nLength))
    {
        std::cout << "is heap!\n";
    }
    else
    {
        std::cout << "is not heap!\n";
    }

    sort_heap(pArray, pArray + nLength);
    display_array(pArray, nLength);
}

void test_heap_algo_in_stl(int *pArray, int nLength)
{
    std::cout << "\ntest_heap_algo_in_stl()\n";

    std::make_heap(pArray, pArray + nLength);
    display_array(pArray, nLength);

    std::push_heap(pArray, pArray + nLength);
    display_array(pArray, nLength);

    std::pop_heap(pArray, pArray + nLength);
    display_array(pArray, nLength);

    // 注意is_heap不是STL中支持的算法, 貌似只有SGI的实现才有这个函数!
    if (is_heap(pArray, pArray + nLength - 1))
    {
        std::cout << "is heap!\n";
    }
    else
    {
        std::cout << "is not heap!\n";
    }

    std::make_heap(pArray, pArray + nLength);
    display_array(pArray, nLength);

    if (is_heap(pArray, pArray + nLength))
    {
        std::cout << "is heap!\n";
    }
    else
    {
        std::cout << "is not heap!\n";
    }

    std::sort_heap(pArray, pArray + nLength);
    display_array(pArray, nLength);
}

void display_array(int *pArray, int nLength)
{
    for (int i = 0; i < nLength; ++i)
        std::cout << pArray[i] << " ";
    std::cout << std::endl;
}