一.堆的实现

1.堆的概念

堆是一种数据结构，首先它总是一颗完全二叉树(因为堆适合表示完全二叉树)，在逻辑上堆是一颗完全二叉树，真正实现上是使用数组来实现的。根据不同的规则(任意根节点比左右孩子大或者小)区分出大根堆和小根堆。

上图就是一个大根堆的演示，小根堆则相反。

2.堆的代码实现

堆的底层逻辑就是数组，所以创建堆只需要先创建个数组。接着我们想通过数组建堆，就需要调整数据在数组中的位置。
现在我们假设有一个乱序的数组:

我们要将其调整为大根堆的情况，则需要从第二层左孩子开始向上调整。上图为数据26作为孩子节点大于其父节点15，则26与15 交换

以此类推继续调整右孩子12…逐层向下。最终可以将其调整为一个大根堆:

代码的实现如下:
创建堆结构，初始化与销毁:

typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void HeapInit(HP* php);
void HeapDestroy(HP* php);void HeapInit(HP* php)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);if (php->a == NULL){perror("malloc fail");return;}php->capacity = 4;php->size = 0;
}void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

向堆插入数据后，为了保持堆为大根堆，需要对数据进行调整:

typedef int HPDataType;void HeapPush(HP* php, HPDataType x);
void AdjustUp(HPDataType* a, int child);void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);if (tmp == NULL){perror("malloc fail");return;}php->a = tmp;php->capacity *= 2;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}void Swap(HPDataType* a, HPDataType* b)
{int tmp = *a;*a = *b;*b = tmp;
}void AdjustUp(HPDataType* a, int child)//插入数据后向上调整
{int parent = (child - 1) / 2;while (child > 0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

删除堆中的数据使用的方法是将根节点的数据与最后一个数据交换，将堆容量减一即可。再交换过数据后，需要对堆进行向下调整(因为将最后一个数据也就是最小的数据放在了根节点)

void HeapPop(HP* php);
void AdjustDown(HPDataType* a, int n, int parent);void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapPop(HP* php)
{assert(php);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}

还有判空 堆的大小等操作:

typedef int HPDataType;HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);HPDataType HeapTop(HP* php)
{assert(php);return php->a[0];
}bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}int HeapSize(HP* php)
{assert(php);return php->size;
}

二.堆排序的讲解

想要使用堆排序，我们首先需要有一个堆，但是如果像上面那样手搓出一个堆，未免太过麻烦。有没有什么方法能让我们像使用其他排序一样(qsort、冒泡等)能直接使用堆排序，对数据进行排序呢?答案是肯定的！
举个例子:我们现在有一个数组，数组中有数据待排。我们首先应该建个堆、再进行排序。其中有两种不同的方式可以建堆———向上调整建堆和向下调整建堆时间复杂度分别为O(N*lgN）、O(N)

void HeapSort(int* a, int n)
{// 建堆 -- 向上调整建堆 -- O(N*logN)for (int i = 1; i < n; ++i){AdjustUp(a, i);}// 建堆 -- 向下调整建堆 -- O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}}int main()
{int a[10] = { 2, 1, 5, 7, 6, 8, 0, 9, 4, 3}; // 对数组排序HeapSort(a, 10);return 0;
}

我们通过调试窗口观察是否达到我们的预期:

建好堆后，就是对数据进行排序,这里有一个重要的结论--------如果想要排升序就要建大根堆、想要排降序则需要建小根堆
最后效果如下:

void HeapSort(int* a, int n)
{// 建堆 -- 向上调整建堆 -- O(N*logN)/*for (int i = 1; i < n; ++i){AdjustUp(a, i);}*/// 建堆 -- 向下调整建堆 -- O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);//排升序--end;}
}int main()
{int a[10] = { 2, 1, 5, 7, 6, 8, 0, 9, 4, 3}; // 对数组排序HeapSort(a, 10);return 0;
}