堆

堆是完整二叉树(除了最后一层，其他层都被完全填满)的一种。根据根节点放置的是所有键值中的最大值还是最小值，堆被分为最大堆和最小堆。堆常用数组来存储。

堆(heap)

• 堆是一个完整的树(所有的层都被填满了，除了最后一层，最后一层有尽可能多的键)。堆的这个属性使它适合存储在数组中。
• 堆不是最小堆就是最大堆。在最小堆中，根上的键必须是最小的(最小堆只保证子树的根部节点值小于左子树和右子树,最终保证了整个树根是最小值)。
• 堆的数组描述(针对数组 Arr)
  1. 根节点 Arr[0]
  2. 父节点: Arr[(i - 1) / 2] (i > 0)
  3. 左子节点: Arr[(2 * i) + 1] (i >= 0)
  4. 右子节点: Arr[(2 * i) + 2] (i >= 0)

堆的应用

• 堆排序: 堆排序的时间复杂度是 O(nlogn)
• 优先队列：使用二进制堆可以有效地实现优先队列，因为它支持在 O(logn) 时间内的 insert() 、delete() 操作。
• 图算法：如 Dijkstra 最短路径 和 prim 最小生成树 。
• 数组中第K个最大的元素。
• 合并K个排序数组。

最小堆实现

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

/**
 *  最小堆的实现
 *
 */

// 最小堆的容量
#define MIN_HEAP_CAPACITY   1000

typedef struct _Heap {
    int* ptr;
    int size;
    int capacity;
}Heap;

// 交换两个值
static void swap(int* x, int* y) {
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

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

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

static int parent(int i) {
    return (i - 1) / 2;
}

// 初始化
void minheap_init(Heap** heap/* out */) {
    *heap = (Heap*) malloc(sizeof(Heap));
    // 判断返回值
    (*heap)->ptr = (int*)malloc(sizeof(int) * MIN_HEAP_CAPACITY);
    // 判断
    (*heap)->size = 0;
    (*heap)->capacity = MIN_HEAP_CAPACITY;
}

// 由根部开始向下调整
void minheap_heapify(Heap* heap, int i) {
    int l = left(i);
    int r = right(i);
    int smallest = i; // 根节点
    if(l < heap->size && *(heap->ptr + l) < *(heap->ptr + smallest)) { // 根节点和左孩子比较
        smallest = l;
    }

    if (r < heap->size && *(heap->ptr + r) < *(heap->ptr + smallest)) { // 根节点和右孩子比较
        smallest = r;
    }

    if (i != smallest) { // 需要调整堆结构
        swap(heap->ptr + i, heap->ptr + smallest);
        minheap_heapify(heap, smallest);
    }
}

void minheap_insert(Heap* heap, int i) {
    if(heap->size >= heap->capacity) {
        // 超出堆的大小
        puts("error!");
        return;
    }

    ++ heap->size;
    int t = heap->size - 1; // 最小堆末尾插入值
    *(heap->ptr + t) = i;

    // 检查是否违反最小堆的性质(根节点小于子节点), 违反则修复
    while (t != 0 && *(heap->ptr + parent(t)) > *(heap->ptr + t)) {
        swap(heap->ptr + t, heap->ptr + parent(t));
        t = parent(t);
    }
}

// 返回最小堆的最小值 (根部值)
int minheap_pop(Heap* heap) {
    if (heap->size <= 0) {
        return INT_MIN; // 错误
    }
    if (heap->size == 1) {
        -- heap->size;
        return *heap->ptr;
    }

    // 保存最小值
    int m = *heap->ptr;

    // 覆盖根部并开始调整
    *heap->ptr = *(heap->ptr + heap->size - 1);
    -- heap->size;
    minheap_heapify(heap, 0);

    return m;
}

int main(void) {
    Heap* heap = NULL;

    // 初始化堆
    minheap_init(&heap);
    // 检查返回值 heap

    // 插入
    minheap_insert(heap, 1);
    minheap_insert(heap, 0);
    minheap_insert(heap, 188);
    minheap_insert(heap, 71);
    minheap_insert(heap, 61);
    minheap_insert(heap, 51);
    minheap_insert(heap, 41);
    minheap_insert(heap, 71);
    minheap_insert(heap, 81);
    minheap_insert(heap, -1);
    minheap_insert(heap, -128);
    minheap_insert(heap, -33);
    minheap_insert(heap, -4);
    minheap_insert(heap, 1);
    minheap_insert(heap, 18);
    minheap_insert(heap, 188);
    minheap_insert(heap, 71);
    minheap_insert(heap, 61);
    minheap_insert(heap, 51);
    minheap_insert(heap, 41);
    minheap_insert(heap, 71);
    minheap_insert(heap, 81);

    printf("size: %dn", heap->size);
    printf("capacity: %dnn", heap->capacity);

    // 输出看看是不是由小到大
    int i = 0;
    for(i = heap->size; i > 0; -- i) {
        int v = minheap_pop(heap);
        printf("%dt", v);
    }
    printf("nncomplete!!!n");

    return 0;
}