一、定义
堆：实际上是一颗 完全二叉树 ，但是它还满足父结点大于（或小于）子结点特性。父结点大于子结点称为最大堆（或大顶堆，array[i]>=array[2i+1] && array[i]>=array[2i+2]，i从0开始），父结点小于子结点称为最小堆（或小顶堆，array[i]<=array[2i+1] && array[i]<=array[2i+2] ，i从0开始）源码地址 GitHub
源码位置
注意：本文全部已最大堆为例，之后不再说明，最小堆与最大堆条件完全相反，不再详细介绍
二、调整
这里先简单介绍一下，稍后详细演示调整过程
向下调整：从父结点、左孩子、右孩子三个结点中选择最大的与父结点进行交换，交换后可能造成孩子结点不满满足堆的性质，因此每次交换后需要从新对交换后的孩子结点进行调整
//交换
void swap(int *x, int *y){
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
// 向下调整
// 非递归实现
// array 是待调整的堆数组，i是待调整的数组元素的位置，nlength是数组的长度
// 本函数功能是：根据数组array构建大根堆
void heapDownAdjust(int array[],int i,int nLength) {
int nChild;
while(2*i+1 < nLength) {
nChild = 2*i+1; // 左孩子（2*（父节点位置）+ 1）
if(nChild<nLength-1 && array[nChild+1]>array[nChild])
++nChild; // 得到子节点中较大的节点
if(array[i] >= array[nChild]) {
break;
}
swap(array+i,array+nChild); // 较大子节点大于父节点向上移动
i=nChild;
}
}
// 递归实现
void heapDownRecursiveAdjust(int array[],int i,int nLength) {
int nChild;
if (2*i+1 < nLength) {
nChild = 2*i+1; // 左孩子（2*（父节点位置）+ 1）
if((nChild < nLength-1) && (array[nChild+1] > array[nChild])) // 得到子节点中较大的节点
++nChild;
if(array[i] < array[nChild]){
swap(array+i,array+nChild);
heapDownRecursiveAdjust(array, nChild, nLength);
}
}
}
向上调整：当前结点与其父结点进行比较，如果比父结点大进行交换，否则退出，依次比较上移直到根结点
// 向上调整
// 非递归实现
void heapUpAdjust(int *array, int index, int nLength) {
int i = index;
int j = (i-1)/2; // 父节点
int temp = array[i];
while(i > 0){
if(temp <= array[j]) break;
array[i] = array[j]; // 比交换高明
i = j;
j = (j-1)/2; // 移动到下一节点
}
array[i] = temp;
}
// 递归实现
void heapUpRecursiveAdjust(int array[], int index, int nLength) {
int i = index;
int j = (i-1)/2;
if(i > 0){
if(array[i] <= array[j]) return;
swap(array+i, array+j);
heapUpRecursiveAdjust(array, j, nLength);
}
}
三、创建
- 创建堆就是从最后一个非叶子结点到根结点不断进行调整的过程
举例说明：给定数组 array[6]={4,5,6,9,8,7} ,创建最大堆
1.构建完全二叉树：
1.构建完全二叉树
2.调整结点6（6与7交换）
2.调整结点6
3.调整结点5（5与9交换）
调整结点5
4.调整结点4（4与9交换，交换后由于子节点不满足性质，4与8交换）
调整结点4
此时最大堆以构建完毕！
// 创建堆
void createHeap(int *array,int length) {
int i;
// 调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素
// length/2-1 是最后一个非叶节点，此处"/"为整除
for(i = length/2-1; i >= 0; --i)
heapDownAdjust(array,i,length);
//heapDownRecursiveAdjust(array,0,i);
}
四、插入
- 把新数据放在数组最后，然后再进行向上调整
以我们创建的最大堆为例
插入结点10：
1.将结点10插入最后
将结点10插入最后
2.子结点10与父结点7交换
子结点10与父结点7交换
3.子结点10与父结点9交换
子结点10与父结点9交换
交换到根结点完成！！！
// 插入元素
int insertElement(int *array, int length, int element) {
if (length) {
array[length] = element; // 放入元素，这里注意数组长度要大于length+1
++length;
heapUpAdjust(array, length-1, length);
//heapUpRecursiveAdjust(array, length-1, length);
return length;
}
return -1;
}
五、删除（根据堆得性质，只能删除根结点）
- 将根结点与最后一个结点交换后，再对根结点向下调整
以我们创建的最大堆为例
删除过程：
1.将根结点9删除，最后的结点6移至根结点（排序时将这两个结点交换）
根结点9删除，结点6根结点
2.由于根结点6不满足堆的性质，调整根结点
调整根结点
// 删除堆元素（堆只能删除根元素）
int deleteElement(int *array, int length) {
if (length) {
swap(array,array+length-1); // 根节点与最后一个节点交换
heapDownAdjust(array,0,length-1); // 向下交换
return length-1;
}
return 0;
}
六、排序
将根结点与最后一个结点进行交换，再对根结点进行向下调整，最后的元素向前移动一个位子继续做上述过程，直到根结点
以上边创建的堆为例，我们来进行排序
已创建好的最大堆
排序过程：
1.将根结点9与最后一个结点6进行交换
9与6交换（然后调整6）
2.将根结点8与最后一个结点4进行交换
8与4交换（然后调整4）
3.将根结点7与最后一个结点5进行交换
7与5交换（然后调整5）
4.将根结点6与最后一个结点4进行交换
6与4交换（然后调整4）
5.将根结点5与最后一个结点4进行交换
5与4交换
6.已剩最后一个结点，排序完成 {4,5,6,7,8,9}
排序完成
// 堆排序算法（传入 array 已是堆）
void heapSort(int *array,int length) {
int i;
//从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
for(i = length-1; i > 0; --i) {
// 把第一个元素和当前的最后一个元素交换，
// 保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
swap(array,array+i);
heapDownAdjust(array,0,i); // 不断缩小范围，每一次调整完毕第一个元素是当前序列的最大值
// heapDownRecursiveAdjust(array,0,i);
}
}
七、测试
int array[] = {12, 14, 54, 5, 6, 3, 9, 8, 47, 89, -1};
for (int i=0; i< 10; i++)
{
printf("%d ", array[i]);
}
printf("\n");
printf("创建堆：");
createHeap(array,10);
for (int i=0; i < 10; i++)
{
printf("%d ", array[i]);
}
printf("\n");
printf("删除元素：");
int length = deleteElement(array,10);
for (int i=0; i < length; i++)
{
printf("%d ", array[i]);
}
printf("\n");
printf("插入元素：");
length = insertElement(array,length,99);
for (int i=0; i < length; i++)
{
printf("%d ", array[i]);
}
printf("\n");
printf("堆排序：");
heapSort(array, length);
for (int i=0; i < length; i++)
{
printf("%d ", array[i]);
}
printf("\n");
关于堆先介绍到这里，如有疑问或是错误之处，欢迎留言！
网友评论