数据结构之二叉树——堆 详解（含代码实现）

1.堆

如果有一个关键码的集合 K = { ， ， ， … ，}，把它的所有元素按完全二叉树的顺序存储方式存储

在一个一维数组中，则称为小堆( 或大堆 ) 。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

堆中某个节点的值总是不大于或不小于其父节点的值；

堆总是一棵完全二叉树。

创建堆

向上调整建堆

向下调整建堆

堆的插入

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆

向上调整算法

数组一个个循环插入时边插入边成堆，当插入新的元素时向上调整成新的堆

使用向上调整算法，每次孩子与父亲相比较，当孩子大于或小于父亲时进行交换，改变孩子的下标，再次进行判断然后交换，知道孩子的下标为0

堆的删除

向下调整算法

给出一个数组，逻辑上看做一颗完全二叉树。通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

当已经成大堆或者小堆后想删元素，最好的办法是把堆的第一个元素与最后一个进行交换，当交换完成，堆中最大或最小的元素就到了最后一个结点，减小下标进行删除，此时堆顶的左右子树为大堆或者小堆，用向下调整算法，将父亲与孩子循环比较大小进行交换，形成新的堆，再次把堆顶元素与最后一个元素交换，使用向下调整成新的堆，反复进行即可删除堆

堆的排序   升序  降序

向上调整建堆，堆顶元素与最后一个元素交换，再次向上或向下调整，得到升序或降序

向上调整建堆

向下调整建堆

向上向下调整对比

向下调整时间复杂度分析

向上调整时间复杂度分析

总结

堆排序时间复杂度

堆的代码实现

//头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;
//初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp);
//向上调整
void Adjustup(HPDataType* a, int child);
//向下调整
void Adjustdown(HPDataType* a, int parent);
void swap(Heap* hp, int child, int parent);

//函数实现
#define _CRT_SECURE_NO_WARNINGS  1
#pragma warning(disable:6031)
#include"heap.h"
//初始化
void HeapInit(Heap* hp)
{assert(hp);hp->a = NULL;hp->size = hp->capacity = 0;
}
void swap( int *p1, int *p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
bool HeapEmpty(Heap* hp)
{assert(hp);return hp->size == 0;
}// 堆的销毁
void HeapDestory(Heap* hp)
{free(hp->a);hp->a = NULL;free(hp);hp = NULL;
}
//向上调整
void Adjustup(HPDataType* a, int child)
{assert(a);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 HeapPush(Heap* hp, HPDataType x)
{assert(hp);if (hp->capacity == hp->size)//1未开劈空间 2.已满没有空间{int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;Heap* tmp = (Heap*)realloc(hp->a, sizeof(HPDataType)* newcapacity);if (tmp == NULL){perror("realloc fail");return NULL;}hp->a = tmp;hp->capacity = newcapacity;}//空间够  hp->a[hp->size] = x;hp->size++;//放进之后 向上调整形成新的堆Adjustup(hp->a, hp->size - 1);
}
//向xia调整
void Adjustdown(HPDataType* a,int n, int parent)
{assert(a);int child = parent * 2 + 1;while (child < n){     //右孩子小于huo大于左孩子if (child + 1 < n && a[child + 1] < a[child]){child++;}if (a[parent] > a[child]){swap(&a[child], &a[parent]);parent = child;child= parent * 2 + 1;}else {break;}}
}
// 堆的删除
void HeapPop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp));//把第一个元素与最后一个交换，向下调整swap( &hp->a[0],&hp->a[hp->size-1]);hp->size--;Adjustdown(hp->a, hp->size, 0);}
//取堆顶数据
HPDataType HeapTop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp));return hp->a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{assert(hp);return hp->size;
}

#define _CRT_SECURE_NO_WARNINGS  1
#pragma warning(disable:6031)
#include"heap.h"
void test()
{Heap hp;HeapInit(&hp);int a[] = { 60,50,6,8,14,7,3 };for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++){HeapPush(&hp, a[i]);}HeapDestroy(&hp);
}
void HeapSort(int* a, int n)
{// 升序 -- 建大堆// 降序 -- 建小堆Heap hp;HeapInit(&hp);//建堆--向上调整建堆/*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[0], &a[end]);// 再调整，选出次小的数AdjustDown(a, end, 0);--end;}
}
int main()
{test();return 0;
}