[C++知识库]迟来的数据结构-堆（优先队列）-C语言实现

纸上得来终觉浅，绝知此事要躬行。

头文件 lc_heap.h?

#ifndef LC_HEAP_H
#define LC_HEAP_H#define LC_HeapMinData -1
typedef int LC_HeapElement;

typedef int(*LC_HeapElementCmp)(const LC_HeapElement* l,const LC_HeapElement* r);

typedef struct tagLCHeap{
    int capacity;
    int count;
    LC_HeapElement  * elements;
    LC_HeapElementCmp cmp;
}LC_Heap;

LC_Heap* LC_HeapInit(int capacity,LC_HeapElementCmp cmp);
void LC_HeapDestroy(LC_Heap* heap);
void LC_HeapPrint(LC_Heap* heap);
void LC_HeapInsert(LC_Heap* heap, LC_HeapElement e);
LC_HeapElement LC_HeapPop(LC_Heap* heap);
LC_HeapElement LC_HeapTop(LC_Heap* heap);
int LC_HeapIsFull(LC_Heap* heap);
int LC_HeapIsEmpty(LC_Heap* heap);

#endif //LC_HEAP_H

函数实现? lc_heap.c

#include "lc_heap.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
static int parent(int i)
{
    return i / 2;
}

static int left(int i)
{
    return i * 2;
}

static int right(int i)
{
    return i * 2 + 1;
}

LC_Heap* LC_HeapInit(int capacity, LC_HeapElementCmp cmp)
{
    LC_Heap* heap = ( LC_Heap* )malloc(sizeof(LC_Heap));
    if (heap == NULL) {
        return NULL;
    }
    heap->capacity = capacity + 1;
    heap->elements = ( LC_HeapElement* )malloc(sizeof(LC_HeapElement) * heap->capacity);
    if (heap->elements == NULL) {
        free(heap);
        return NULL;
    }
    memset(heap->elements, 0, sizeof(LC_HeapElement) * heap->capacity);
    heap->elements[0] = LC_HeapMinData;
    heap->cmp         = cmp;
    heap->count       = 0;
    return heap;
}

void LC_HeapDestroy(LC_Heap* heap)
{
    if (heap != NULL) {
        if (heap->elements != NULL) {
            free(heap->elements);
            heap->elements = NULL;
        }
        free(heap);
        heap = NULL;
    }
}

static void LcHeapUpImp(LC_Heap* heap, int index)
{
    while (index != 1) {
        if (heap->cmp(&heap->elements[index], &heap->elements[parent(index)]) < 0) {
            break;
        }
        LC_HeapElement eleTmp = heap->elements[index];
        heap->elements[index] = heap->elements[parent(index)];
        heap->elements[parent(index)] = eleTmp;
        index = parent(index);
    }
}

void LC_HeapInsert(LC_Heap* heap, LC_HeapElement e)
{
    int pos             = ++heap->count;
    heap->elements[pos] = e;
    LcHeapUpImp(heap, pos);
}

static void LcHeapDownImp(LC_Heap* heap, int index)
{
    if (left(index) > heap->count) {
        return;
    }
    int child = left(index);
    if (child < heap->count && heap->cmp(&heap->elements[child + 1], &heap->elements[child]) > 0) {
        child++;
    }
    LC_HeapElement eleTmp = heap->elements[index];
    heap->elements[index] = heap->elements[child];
    heap->elements[child] = eleTmp;
    LcHeapDownImp(heap, child);
}

LC_HeapElement LC_HeapPop(LC_Heap* heap)
{
    LC_HeapElement ele = LC_HeapTop(heap);
    if (ele == LC_HeapMinData) {
        return ele;
    }
    heap->elements[1] = heap->elements[heap->count--];
    LcHeapDownImp(heap, 1);
    return ele;
}

LC_HeapElement LC_HeapTop(LC_Heap* heap)
{
    if (LC_HeapIsEmpty(heap)) {
        return heap->elements[0];
    }
    return heap->elements[1];
}

int LC_HeapIsFull(LC_Heap* heap)
{
    return heap->count + 1 == heap->capacity;
}
int LC_HeapIsEmpty(LC_Heap* heap)
{
    return heap->count == 0;
}


void LC_HeapPrint(LC_Heap* heap)
{
    for (int i = 0; i <= heap->count; ++i) {
        printf("%d-", heap->elements[i]);
    }
    printf("\r\n");
}

测试程序 main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "lc_heap.h"

int LC_HeapElementCmpImp(const LC_HeapElement* l,const LC_HeapElement* r)
{
    return (*r) - (*l);
}

int main()
{
    LC_Heap* heap = LC_HeapInit(100,LC_HeapElementCmpImp);
    LC_HeapElement elems[] = {1,3,4,5,2,6,9,7,8,0};
    for (int i = 0; i < sizeof(elems) / sizeof(elems[0]); ++i) {
        LC_HeapInsert(heap, elems[i]);
        //LC_HeapPrint(heap);
    }
    while(!LC_HeapIsEmpty(heap)) {
        printf("%d - ", LC_HeapPop(heap));
    }
    LC_HeapDestroy(heap);
    return 0;
}