堆的实现——堆的应用（堆排序）

大家在学堆的时候，需要有二叉树的基础知识，大家可以看我的二叉树文章：二叉树

1.堆的实现

如果有⼀个关键码的集合 K = {k0 , k1 , k2 , …，kn−1 } ，把它的所有元素按完全⼆叉树的顺序存储⽅
式存储，在⼀个⼀维数组中，并满⾜： Ki <= K2∗i+1 （ Ki >= K2∗i+1 且 Ki <= K2∗i+2 ），
i = 0、1、2… ，则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆
叫做最⼩堆或⼩根堆。
如下就是堆的例子：

堆有很多的应用，例如：①堆排序 ②TOP-K问题

堆的底层就是数组，我们主要实现如下接口：

//堆的初始化
void HeapInit(Heap* php);
// 堆的销毁
void HeapDestory(Heap* php);
// 堆的插入
void HeapPush(Heap* php, HPDataType x);
// 堆的删除
void HeapPop(Heap* php);
// 取堆顶的数据
HPDataType HeapTop(Heap* php);
// 堆的数据个数
int HeapSize(Heap* php);
// 堆的判空
int HeapEmpty(Heap* php);

堆结构：

typedef int HPDataType;typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;

对于堆的初始化和销毁很简单：

//堆的初始化
void HeapInit(Heap* php)
{assert(php);php->_a = NULL;php->_size = php->_capacity = 0;
}// 堆的销毁
void HeapDestory(Heap* php)
{assert(php);php->_capacity = php->_size = 0;free(php->_a);php->_a = NULL;
}

对于堆的插入，例如我们建一个小根堆，我们每次插入一个数，是把他放在堆尾的（即数组的最后一个元素），然后使用向上调整算法，

Q：什么是向上调整算法？
A：对于我们新插入来的数，我们把他放在堆的最后一个元素上，我们需要不断比较他（即孩子节点）与父节点谁小，若父节点小，则终止循环，若孩子节点小，则需要他和父节点交换位置，并循环下去比，代码如下：

//向上调整算法，建小堆
void AdjustUp(HPDataType* arr, int n)
{int child = n - 1;while (child > 0){int parent = (child - 1) >> 1;if (arr[child] < arr[parent]){swap(arr[child], arr[parent]);}child = parent;}
}

所以，对于堆插入一个元素代码如下：

// 堆的插入
void HeapPush(Heap* php, HPDataType x)
{assert(php);//判断是否需要增容if (php->_capacity == php->_size){int newCapacity = php->_capacity == 0 ? 4 : 2 * php->_capacity;HPDataType* tmp = (HPDataType*)realloc(php->_a, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail");exit(-1);}php->_capacity = newCapacity;php->_a = tmp;}php->_a[php->_size++] = x;//向上调整算法AdjustUp(php->_a, php->_size);
}

对于堆的删除，也就是我们要把最小的那个元素pop出来，已知的是堆顶是最小的元素，我们只需要让堆顶元素和最后一个元素互换，然后size–，然后在执行向下调整算法即可：如下

//向下调整算法
void AdjustDown(HPDataType* arr, int n)
{int parent = 0;int child = parent * 2 + 1;while (child < n){if (child + 1 < n && arr[child + 1] < arr[child]) child = child + 1;if (arr[child] < arr[parent]){swap(arr[child], arr[parent]);parent = child;child = parent * 2 + 1;}else break;}
}// 堆的删除
void HeapPop(Heap* php)
{assert(php);assert(!HeapEmpty(php));swap(php->_a[0], php->_a[php->_size - 1]);php->_size--;AdjustDown(php->_a, php->_size);
}

余下的接口：

// 取堆顶的数据
HPDataType HeapTop(Heap* php)
{assert(php);assert(!HeapEmpty(php));return php->_a[0];
}// 堆的数据个数
int HeapSize(Heap* php)
{assert(php);return php->_size;
}
// 堆的判空
int HeapEmpty(Heap* php)
{assert(php);return php->_size == 0 ? 1 : 0;
}

2.堆的应用–堆排序

我们想一想，给我们传入一个数组，让我们堆数组里面的元素进行排序，需要注意的是，向上调整算法和向下调整算法我们都要求除了他，其他的都是一个堆。也就是我们需要对每个数据都进行一遍调整算法，那么向上还是向下呢？我们来分析一下时间复杂度：

1. 向上调整算法：我们需要从第一个元素开始都进行一遍向上调算法，
   
   因此来说：==向上调整算法的时间复杂度是O(nlogn)，==为什么这么高，我们可以想一下，月考后面的元素在二叉树上呈现的是越多的，而且他还要向上移动比较的次数更多，那他的复杂度不就高了吗

2. 向下调整算法：这里，我们不需要从最后一个元素开始向下调整，我们只需要从最后一个非叶子节点开始向下调整算法即可，
   
   因此向下调整算法的时间复杂度为：O(n)

注意：这里是向下调整算法建堆的时间复杂度是O(n)，但是单单一个元素向下调整算法是O(logn)的。

因此对于堆排序，我们采用向下调整算法较优。

堆排序，大家可以参考我的这篇文章：堆排序