1. Heap.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

typedef int(*Compare)(int x, int y);

// call back
int Greater(int x, int y);
int Less(int x, int y);

typedef struct Heap {
    int* arr;
    int capacity;
    int size;
    Compare compare;
} Heap;

void Swap(int* x, int* y);

void AdjustDown(Heap* pH, int root);

void HeapInit(Heap* pH, int* arr, int size, Compare com);

void HeapDestroy(Heap* pH);

void CheckCapacity(Heap* pH);

void AdjustUp(Heap* pH, int index);

void HeapInsert(Heap* pH, int data);

void HeapDelete(Heap* pH);

int HeapSize(Heap* pH);

int HeapTop(Heap* pH);

int HeapEmpty(Heap* pH);

void HeapTest();

void HeapSort(int* arr, int size, Compare compare);

void TestSort();

2. Heap.c

#include "Heap.h"

int Greater(int x, int y) { return x > y; }
int Less(int x, int y) { return x < y; }

void Swap(int* x, int* y) {
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

void AdjustDown(Heap* pH, int root) {
    assert(pH);

    int* arr = pH->arr;
    int parent = root;
    int child = parent * 2 + 1;  // left child

    while (child < pH->size) {
        if (child + 1 < pH->size && pH->compare(arr[child + 1], arr[child])) {
            child++;
        }

        if (pH->compare(arr[child], arr[parent])) {
            Swap(&arr[child], &arr[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else {
            break;
        }
    }
}

void HeapInit(Heap* pH, int* arr, int size, Compare com) {
    assert(pH);

    pH->arr = (int *)malloc(sizeof(int) * size);
    if (pH->arr == NULL) {
        perror("malloc error");
        exit(0);
    }

    memcpy(pH->arr, arr, size * 4);
    pH->capacity = size;
    pH->size = size;
    pH->compare = com;

    for (int root = (pH->size - 2) / 2; root >= 0; root--) {
        AdjustDown(pH, root);
    }
}

void HeapDestroy(Heap* pH) {
    assert(pH);

    free(pH->arr);
}

void CheckCapacity(Heap* pH) {
    assert(pH);

    if (pH->size == pH->capacity) {
        int* newArr = (int *)realloc(pH->arr, sizeof(int) * pH->capacity * 2);
        if (newArr == NULL) {
            perror("realloc error");
            exit(0);
        }

        pH->arr = newArr;
        pH->capacity *= 2;
    }
}

void AdjustUp(Heap* pH, int index) {
    assert(pH);

    int* arr = pH->arr;
    int child = index;
    int parent;

    while (child) {
        parent = (child - 1) / 2;

        if (pH->compare(arr[child], arr[parent])) {
            Swap(&arr[child], &arr[parent]);
            child = parent;
        }
        else {
            break;
        }
    }
}

void HeapInsert(Heap* pH, int data) {
    assert(pH);

    CheckCapacity(pH);

    pH->arr[pH->size] = data;
    pH->size++;
    AdjustUp(pH, pH->size - 1);
}

void HeapDelete(Heap* pH) {
    assert(pH);

    if (HeapEmpty(pH)) {
        return;
    }

    Swap(&(pH->arr[0]), &(pH->arr[pH->size - 1]));
    pH->size--;
    AdjustDown(pH, 0);
}

int HeapSize(Heap* pH) {
    return pH->size;
}

int HeapTop(Heap* pH) {
    return pH->arr[0];
}

int HeapEmpty(Heap* pH) {
    return pH->size == 0;
}

void HeapTest() {
    int arr[] = { 3, 7, 4, 2, 5, 1, 9, 8, 6, 0 };
    Heap h;

    HeapInit(&h, arr, sizeof(arr) / sizeof(arr[0]), Less);  // 小堆
    HeapDelete(&h);
    HeapDelete(&h);
    HeapInsert(&h, -1);
    HeapInsert(&h, -2);
    HeapInsert(&h, 10);

    printf("\n");
}