前言

数据结构中的堆是一种结构，C语言的堆是空间管理的程序员malloc，free的空间，两者没多大关系。

1.堆

• 逻辑上

  堆（Heap）是一类基于完全二叉树的特殊数据结构。通常将堆分为两种类型：

  1.大顶堆（Max Heap）：在大顶堆中，根结点的值必须大于他的孩子结点的值，对于二叉树中所有子树都满足此规律
  

  2.小顶堆（Min Heap）：在小顶堆中，根结点的值必须小于他的孩子结点的值，对于二叉树中所有子树都满足此规律
  

• 物理上

  之前有个性质：完全二叉树中用数组空间来存储结构，从1号下标开始存储第一个元素，i号下标的根节点是2\i，左孩子2i,右孩子2i+1，接下来我们来看下怎么处理堆的逻辑。

2.堆的操作逻辑

如图，有8个数组组成了最小堆初始化数，我已经申请了9个空间（因为是完全二叉树用数组空间存储，从1号下标开始存元素），定义两个 指针：len指针用来表示待插入位置，capacity用来表示数组空间容量

插入逻辑：

1.在最后一个位置上插入新元素，从代码角度讲 ++len;data[len]=v;
2.如果是小顶堆，找这个元素的父节点，如果父节点的值大于这个元素，交换两个节点的值
3.继续交换节点的父节点继续执行条件判断，是否交换
4.直到找到根或者已不满足条件

2，3，4我们的称为上浮操作

如图初始化时把9放进来

把3放进来，发现3比9小，于是交换两个节点的值，并在数据区里也更新对应的值

把7放进来

把6放进来，发现父节点9的值比它大，交换

一直这样直到把全部数字都放进堆中，最终结果如图

提取数据：
1.提取根元素，提取到最值
2.我们不能直接给它删了，我们要继续保持这颗树的逻辑结构
3.把最后一个元素放到根节点的值，有效长度再减1，等价于删除最后一个元素(因为删除完全二叉树的节点时都是删除叶子节点，这样才可以保持树的结构，但是没有满足小顶堆的约束)。
4.把现在的根节点的值放入到正确的位置

3，4我们称为下沉。

如图我们要提取根节点1，按照上述逻辑，我们要保持整棵树的结构，先把叶子节点9的值交给1，删除叶子节点，len–

开始完成约束条件，把根节点的值放入正确的位置，此时我们需要比较根节点的左右孩子的大小，选择较小的那个，因为如果我们把9和3交换位置，3比2大依然没有满足小顶堆的约束，所以9和2交换位置，此时9来到2的位置，再次比较左右孩子的大小，发现5是较小值，交换5和9。如图：

如果我们有100个元素，但是我们只想要提取前5个，你可以把这100个排好序，然后取前5个即可，但是这样时间复杂度是O(n²)，我们完全可以用小顶堆排好这100个元素，然后提取5次小顶堆的根节点，时间开销就很少，这样效率就较好。例如应用：Top10，在音乐榜单中的前10首歌曲，就可以采取这种思想，把成千上万首歌放进小顶堆，然后取10次小顶堆的根节点就拍好序了。

3.堆的代码实现

数据结构实现

#ifndef MINI_HEAP_H
#define MINI_HEAP_H
#include "../sortHelper.h"
// 定义小顶堆的结构
typedef struct {keyType *data;int len;            // 堆data的长度int capacity;       // 最大容量
} MiniHeap;MiniHeap *createMiniHeap(int n);            // 产生n个元素的堆空间
void releaseMiniHeap(MiniHeap *miniHeap);// 插入
void insertMiniHeap(MiniHeap *heap, keyType e);
// 提取
keyType extractMinMiniHeap(MiniHeap *heap);
#endif //MINI_HEAP_H

创建树的接口：MiniHeap *createMiniHeap(int n);

MiniHeap * createMiniHeap(int n) {MiniHeap * heap = malloc(sizeof(MiniHeap));if (heap==NULL) {return NULL;}heap->data = malloc(sizeof(int)*n);if (heap->data == NULL) {free(heap);return NULL;}heap->capacity=n;heap->len=0;return heap;
}

释放树的接口：void releaseMiniHeap(MiniHeap *miniHeap);

void releaseMiniHeap(MiniHeap *miniHeap) {if (miniHeap) {if (miniHeap->data) {free(miniHeap->data);}free(miniHeap);}
}

插入接口：void insertMiniHeap(MiniHeap *heap, keyType e);

static void shiftUp(MiniHeap *miniHeap, int k) {keyType tmp;// k/2表示父节点，k节点子节点while (k > 1 && miniHeap->data[k / 2] > miniHeap->data[k]) {tmp = miniHeap->data[k];miniHeap->data[k] = miniHeap->data[k / 2];miniHeap->data[k / 2] = tmp;k /= 2;}
}void insertMiniHeap(MiniHeap *heap, keyType e) {//防越界if (heap->len + 1 > heap->capacity) {return;}heap->data[++heap->len] = e;shiftUp(heap,heap->len);
}

我这里写了一个内在的接口shifUp即我在2.堆的操作逻辑中的2，3，4操作中的上浮操作，相信大家应该能看懂

提取接口:keyType extractMinMiniHeap(MiniHeap *heap)；

static void shiftDown(MiniHeap *miniHeap, int k) {keyType tmp;while (2 * k <= miniHeap->len) {        // 保证有左孩子int index = 2 * k;if (index + 1 <= miniHeap->len && miniHeap->data[index + 1] < miniHeap->data[index]) {++index;}if (miniHeap->data[k] <= miniHeap->data[index]) {break;}tmp = miniHeap->data[k];miniHeap->data[k] = miniHeap->data[index];miniHeap->data[index] = tmp;k = index;}
}keyType extractMinMiniHeap(MiniHeap *heap) {//防越界if (heap->len <= 0) {return 0;}keyType ret=heap->data[1];heap->data[1]=heap->data[heap->len--];shiftDown(heap,1);return ret;
}

注意在static void shiftDown(MiniHeap *miniHeap, int k)我们不仅要检验左子树有没有越界还要检验右子树有没有越界，先保证有左孩子，如果我们的右孩子没有越界并且右孩子的值小于左孩子的值，那就拿到右孩子的索引，如果父节点的值已经小于了左右孩子节点中的较小值就直接退出，然后进行交换值。

来测一下：

#include <stdio.h>
#include "miniHeap.h"void test01() {int data[] = {9, 3, 7, 6, 5, 1, 10, 2};int n = 20;MiniHeap *miniHeap = createMiniHeap(n);for (int i = 0; i < sizeof(data) / sizeof(data[0]); i++) {insertMiniHeap(miniHeap, data[i]);}printf("extra: ");for (int i = 0; i < sizeof(data) / sizeof(data[0]); i++) {printf("%d ", extractMinMiniHeap(miniHeap));}printf("\n");releaseMiniHeap(miniHeap);
}int main() {test01();return 0;
}

结果：

D:\work\DataStruct\cmake-build-debug\04_Sort\HeapSort.exe
extra: 1 2 3 5 6 7 9 10进程已结束，退出代码为 0

我们再写一个接口来测试堆排序的时间复杂度：

#include "heapSort.h"void miniHeapSort(SortTable *table) {MiniHeap *heap = createMiniHeap(table->length);for (int i = 0; i < table->length; i++) {insertMiniHeap(heap, table->data[i].key);}for (int i = 0; i < table->length; i++) {table->data[i].key = extractMinMiniHeap(heap);}releaseMiniHeap(heap);
}

用快速排序来进行对比：

#include <stdio.h>
#include "miniHeap.h"
#include "heapSort.h"
#include "../02_SwapSort/quickSort.h"void test01() {int data[] = {9, 3, 7, 6, 5, 1, 10, 2};int n = 20;MiniHeap *miniHeap = createMiniHeap(n);for (int i = 0; i < sizeof(data) / sizeof(data[0]); i++) {insertMiniHeap(miniHeap, data[i]);}printf("extra: ");for (int i = 0; i < sizeof(data) / sizeof(data[0]); i++) {printf("%d ", extractMinMiniHeap(miniHeap));}printf("\n");releaseMiniHeap(miniHeap);
}void test02() {int n = 100000;SortTable *table1 = generateRandomArray(n, 0, n + 5000);SortTable *table2 = copySortTable(table1);testSort("Heap Sort", miniHeapSort, table1);testSort("quick Sort", quickSortV1, table2);releaseSortTable(table1);releaseSortTable(table2);
}int main() {test02();return 0;
}

结果：

D:\work\DataStruct\cmake-build-debug\04_Sort\HeapSort.exe
Heap Sort cost time: 0.013000s.
quick Sort cost time: 0.009000s.进程已结束，退出代码为 0

可以看到两者的排序时间是差不多的，这是因为堆排序和树的高度有关，所以时间复杂度也是O(nlogn)。

大概先写这些吧，今天的博客就先写到这，谢谢您的观看。