C语言实现堆数据结构和基本操作

总有一种在垃圾堆里刨食的感觉，为了让垃圾堆里多一些有用的东西，我特意写了这个文章。本文章的代码是从别的地方抄来的，如果原作者不希望代码放在这里，请联系帖主删除帖子。

#include 
#include 
#include 
#include 
#include 

typedef int HPDateType;

typedef struct Heap
{
    HPDateType *a;
    int size;
    int capacity;
} HP;

void HeapInit(HP *php, HPDateType *a, int n); // 初始化一个堆
void HeapDestroy(HP *php);                    // 销毁一个堆，释放他的空间
void HeapPush(HP *php, HPDateType x);         // 在堆里面插入一个数，并且让它的结构还是一个堆
void HeapPop(HP *php);                        // 删除堆的顶的数据，并且让它的结构还是一个堆
HPDateType HeapTop(HP *php);                  // 返回堆顶的数据
int HeapSize(HP *php);                        // 返回堆里面数据的个数
bool HeapEmpty(HP *php);                      // 判断堆是否为空
void HeapPrint(HP *php);                      // 输出一个堆
void AdjustUp(HP *st, int child);             // 向上调整算法
void AdjustDown(HP *st, int praent);          // 向下调整算法
void Swap(int *p1, int *p2);                  // 交换值
void HeapSort(HP *php);                       // 堆排序








int main(int argc, char **argv)
{
    HP st;
    int a[] = {15, 18, 28, 34, 65, 19, 49, 25, 37, 27};
    int n = sizeof(a) / sizeof(a[0]);

    printf("ntest HeapInit(), HeapPrint():n");
    HeapInit(&st, a, n);
    HeapPrint(&st);

    printf("ntest HeapPush(&st, 8):n");
    HeapPush(&st, 8);
    HeapPrint(&st);

    printf("ntest HeapPush(&st, 88):n");
    HeapPush(&st, 88);
    HeapPrint(&st);

    printf("ntest HeapPop(&st):n");
    HeapPop(&st);
    HeapPrint(&st);

    printf("ntest HeapPop(&st):n");
    HeapPop(&st);
    HeapPrint(&st);

    printf("n对堆进行排序：n");
    HeapSort(&st);
    HeapPrint(&st);


    
    HeapDestroy(&st);

    if(st.a == NULL)
        printf("n销毁堆成功n");

    return 0;
}

// 交换
void Swap(int *p1, int *p2)
{
    int temp = *p1;
    *p1 = *p2;
    *p2 = temp;
}

// 向上调整算法
void AdjustUp(HP *st, int child)
{
    int parent = (child - 1) / 2;

    while (child > 0)
    {
        if (st->a[child] < st->a[parent])
        {
            Swap(&st->a[child], &st->a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}

// 向下调整算法
void AdjustDown(HP *st, int praent)
{
    int child = praent * 2 + 1;

    while (child < st->size)
    {
        if (child + 1 < st->size && st->a[child + 1] < st->a[child])
        {
            child++;
        }

        if (st->a[child] < st->a[praent])
        {
            Swap(&st->a[child], &st->a[praent]);
            praent = child;
            child = praent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

void HeapInit(HP *php, HPDateType *a, int n)
{
    if (php == NULL)
        return;

    php->a = (HPDateType *)calloc(1, sizeof(HPDateType) * n);

    if (php->a == NULL)
        exit(EXIT_FAILURE);

    memcpy(php->a, a, sizeof(HPDateType) * n);
    php->capacity = n;
    php->size = n;

    int i;

    //建小堆
    for (i = (php->size - 2) / 2; i >= 0; i--)
        AdjustDown(php, i);
}

void HeapDestroy(HP *php)
{
    if (php == NULL)
        return;

    free(php->a);
    php->a = NULL;
    php->size = 0;
    php->capacity = 0;
}

//在堆里面插入一个数，并且让它的结构还是一个堆
void HeapPush(HP *php, HPDateType x)
{
    if (php == NULL)
        return;

    
    if (php->size == php->capacity)
    {
        HPDateType *temp = (HPDateType *)realloc(php->a, sizeof(HPDateType) * php->capacity * 2);
        if (temp == NULL)
            exit(EXIT_FAILURE);

        php->a = temp;
        php->capacity = php->capacity * 2;
    }

    php->a[php->size] = x;
    php->size++;

    AdjustUp(php, php->size - 1);
}

//删除堆的顶的数据，并且让它的结构还是一个堆
void HeapPop(HP *php)
{
    if (php == NULL)
        return;

    if (HeapEmpty(php))
        return;

    int end = php->size - 1;

    Swap(&php->a[0], &php->a[end]);
    php->size--;

    AdjustDown(php, 0);
}

//返回堆顶的数据
HPDateType HeapTop(HP *php)
{
    if (php == NULL)
        return;

    if (HeapEmpty(php))
        return;

    return php->a[0];
}

//返回堆里面数据的个数
int HeapSize(HP *php)
{
    if (php == NULL)
        return;

    return php->size;
}

//判断堆是否为空
bool HeapEmpty(HP *php)
{
    if (php == NULL)
        return;
    return (php->size == 0);
}

//将堆打印出来
void HeapPrint(HP *php)
{
    int i;
    int m = 1, n = 0;

    printf("n从上到下输出堆的内容：n");

    for (i = 0; i < php->size; i++)
    {
        printf("%d ", php->a[i]);
        if (i == n)
        {
            putchar('n');
            m = m * 2;
            n += m;
        }
    }

    printf("nn");
}

void HeapSort(HP *php)
{
    int t = php->size;

    while (php->size != 0)
    {
        HeapPop(php);
    }

    php->size = t;
}

运行效果：