堆可以看作各个元素之前有前后续的特殊数组，当然也是一颗完全二叉树。设堆heap的元素为heap[1,2,3,...,heap_size]。注意0<=heap_size<=heap.len，并且节点从1开始计数（便于计算）。
1. 寻找节点
1.1 寻找父节点
若节点编号为 i i i，那么他的父节点为 i 2 \frac{i}{2} 2i向下取整。代码实现如下：
/**
* 求节点i的父节点
*/
int parent(int i){
return i/2;
}
1.2 寻找左孩子
若节点编号为 i i i，那么他的左孩子节点为 2 i 2i 2i。代码实现如下：
/**
* 求左孩子
*/
int left(int i){
return 2*i;
}
1.3 寻找右孩子
若节点编号为 i i i，那么他的左孩子节点为 2 i 2i 2i+1。代码实现如下：
/**求右孩子
*
*/
int right(int i){
return 2*i+1;
}
2. 维护堆
- 在堆nums中维护第i个节点为根的树
参数说明：
- nums:表示待维护的堆
- i表示待维护的节点
- 返回值若为1则说明该堆被维护过，返回值为0则说明该堆不需要被维护
- 注：堆的第一个元素nums[0]存储堆内有效数据的长度，建堆的时候应该明确给出
- 使用flag来监视程序是否更改堆的顺序
int maxHeapIfy(int nums[], int i){
int l = left(i);
int r = right(i);
int largest;
int heapSize = nums[0];
//flag用于判断是否被维护过
int flag = 0;
//判断左子树和根节点哪个大，选出大的节点设为largest
if(l <= nums[0] && nums[l]>nums[i]){
largest = l;
}else{
largest = i;
}
//比较largest和右节点那个大，选出大节点作为largest
if( r <= nums[0] && nums[r]>nums[largest]){
largest = r;
}
//若largest ！= i则说明该节点为根的树需要调整
if(largest != i){
flag=1;
int exchange;
exchange = nums[largest];
nums[largest] = nums[i];
nums[i] = exchange;
maxHeapIfy(nums , largest);
}
return flag;
}
3. 建堆
直接按照输入数组，从最后一个非叶子节点开始（一直到第一个节点）调用维护堆的函数，即可根据输入数组建立一个最大堆。
/**
* 建堆，nums[0]表示第堆的大小
*
*
*/
void buildMaxHeap(int nums[]){
for(int i=nums[0]/2;i>0;i--){
maxHeapIfy(nums,i);
}
}
4. 测试
4.1 测试代码
#include<stdio.h>
#include"tools.h"
#include"tets.h"
int main(){
int s[]={0,2,7,2,9,100,3,6};
s[0] = sizeof(s)/sizeof(s[0])-1;
printf("原始堆顺序如下：\n");
for(int i = 1;i<8;i++){
printf("%d ",s[i]);
}
printf("\n堆的大小为：%d \n",s[0]);
buildMaxHeap(s);
int flag = maxHeapIfy(s,1);
printf("flag:%d \n",flag);
printf("排序后的堆顺序如下：\n");
for(int i = 1;i<8;i++){
printf("%d ",s[i]);
}
return 0;
}
4.2 测试结果
5. 时间复杂度
维护堆时间复杂度:
O
(
log
n
)
=
O
(
h
)
O(\log n)=O(h)
O(logn)=O(h)（
h
h
h即待维护节点的高度）
建堆时间复杂度：
O
(
n
)
O(n)
O(n)