百度百科给出堆的介绍是：堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。
堆的性质：
堆的实现代码：堆的实现代码，点击此处。
将根结点最大的堆叫做最大堆，或者大根堆。反之，根结点最小的堆叫做最小堆或者小根堆。
下面展示的小根堆的向下调整算法，对于大根堆，就需要修改小于号为大鱼号就行。总之，先上代码。
注意：
//向下调整
void AdjustDown(int* 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[parent], &a[child]);//交换函数，自己实现
parent = child;//迭代公式
child = parent * 2 + 1;
}
else{//子节点小于或等于父节点
break;
}
}
}
对上述代码的解释：假设有数组：
int a[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
其二叉树结构为：
比较交换：（其余比较都类似）
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 HeapInit(HP* php, HPDataType *a, int n)
{
assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType)*n);
if (php->a == NULL){
printf("malloc fail\n");
exit(-1);
}
memcpy(php->a, a, sizeof(HPDataType)*n);
php->size = n;
php->capacity = n;
//建堆
for (int i = (php->size - 1 - 1) / 2; i >= 0; --i){
AdjustDown(php->a, php->size, i);
}
}
void HeapPush(HP* php, HPDataType x)
{
if (php->size == php->capacity){
HPDataType* tmp = (HPDataType*)realloc(php->a, php->capacity * 2 * (sizeof(HPDataType)));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
php->a = tmp;
php->capacity *= 2;
}
php -> a[php->size] = x;
php->size++;
//向上调整算法，插入数据大于父节点
AdjustUp(php->a,php->size-1);
}
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);
Swap(&php->a[0], &php->a[php->size - 1]);//交换堆顶和最后一个数据
php->size--;
AdjustDown(php->a, php->size, 0);//向下调整
}
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
int HeapSize(HP* php)
{
assert(php);
return php->size;
}
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
void HeapPrint(HP* php)
{
for (int i = 0; i < php->size; i++){
printf("%d ", php->a[i]);
}
printf("\n\n");
int num = 0;
int levelSize = 1;
int i = 0;
for (int j = 0; j < php->size; j++){
printf("%d ", php->a[i++]);
++num;
if (num == levelSize){
printf("\n");
levelSize *= 2;
num = 0;
}
}
printf("\n\n");
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){
HP hp;
HeapInit(&hp, arr, arrSize);//初始化堆
int * retArr = (int*)malloc(sizeof(int)*k);//开辟一个存放堆的数组
for (int i = 0; i < k; ++i){
retArr[i] = HeapTop(&hp);//堆顶数据存放在开辟的数组中
HeapPop(&hp);//删除堆顶，堆减少一个数据
}
HeapDestroy(&hp);//销毁堆
*returnSize = k;
return retArr;
}
思考：堆排序如何实现？下一篇博客将介绍。
cs