//建堆的过程是从最后一个元素开始
+(void)setHeap:(NSMutableArray *)arr
{
NSInteger len = arr.count;
//对每一个非叶子节点（非终端结点）进行遍历
for (NSInteger i = (len-2)*0.5; i>=0; i--) {
NSInteger parent = i;
NSInteger child = 2*parent+1;
//只要有左孩子节点就需要进行大小判断（因为有左孩子就是有孩子），这里是对以父节点parent为根节点的树进行调整
while (child<len) {
if (child+1<len&&[arr[child+1] integerValue]<[arr[child] integerValue]) {
child ++;
}
if ([arr[child] integerValue]<[arr[parent] integerValue]) {
NSNumber *num = arr[child];
arr[child] = arr[parent];
arr[parent] = num;
//这里是因为只要有替换，那么以替换节点child为根的树就有可能也需要调整，那么就需要继续while循环
parent = child;
child = 2*parent+1;
}
else
{
//不需要替换，那么就跳出while循环，继续对下一个节点i为根节点的树进行调整
break;
}
}
}
}
中间的调整部分(向下调整)可以提取出来：
+(void)adjustDown:(NSMutableArray *)arr parent:(NSInteger)parent
{
NSInteger len = arr.count;
NSInteger child = 2*parent+1;
//只要有左孩子节点就需要进行节点大小判断（因为有左孩子就是有孩子），这里是对以父节点parent为根节点的树进行调整
while (child<len) {
if (child+1<len&&[arr[child+1] integerValue]<[arr[child] integerValue]) {
child ++;
}
if ([arr[child] integerValue]<[arr[parent] integerValue]) {
NSNumber *num = arr[child];
arr[child] = arr[parent];
arr[parent] = num;
//这里是因为只要有替换，那么以替换节点child为根的树就有可能也需要调整，那么就需要继续while循环
parent = child;
child = 2*parent+1;
}
else
{
//不需要替换，那么就跳出while循环，继续对下一个节点i为根节点的树进行调整
break;
}
}
}
//向堆中添加元素（被插入的节点只需要直接跟父节点进行大小比较，而不需要跟其同层的另一个孩子节点进行大小比较）
+(void)insert:(NSMutableArray *)arr Node:(NSNumber *)num
{
[arr addObject:num];
NSInteger child = arr.count - 1;
NSInteger parent = (child - 1)*0.5;
while (child!=0) {
//因为只有做了交换的节点才有可能需要继续交换，所以这里并不需要再比较左右节点
if ([arr[child] integerValue]<[arr[parent] integerValue]) {
NSNumber *num = arr[child];
arr[child] = arr[parent];
arr[parent] = num;
child = parent;
parent = (child - 1)*0.5;
}
else
{
break;
}
}
}
//堆排序
+(void)sort:(NSMutableArray *)arr
{
NSInteger len = arr.count;
NSNumber *num = arr[len - 1];
arr[len - 1] = arr[0];
arr[0] = num;
//每次循环确定好最后一个元素的位置（也就是当前堆的最小值），所以循环变量如下
for (NSInteger length = len-1; length>=1; length--) {
NSInteger parent = 0;
NSInteger child = 2*parent + 1;
//有交换则以被交换的孩子节点为根的树可能需要继续进行调整，那么就要继续，如果没有交换那么就可以直接跳出while循环，此时已经将当前堆调整完毕
while (child<length) {
if (child+1<length&&[arr[child+1]integerValue]<[arr[child]integerValue]) {
child ++;
}
if ([arr[child]integerValue]<[arr[parent]integerValue]) {
NSNumber *num = arr[child];
arr[child] = arr[parent];
arr[parent] = num;
parent = child;
child = 2*parent + 1;
}
else
{
break;
}
}
//交换第一个元素（当前堆的最小值）和当前堆的最后一个元素
NSNumber *num = arr[length - 1];
arr[length - 1] = arr[0];
arr[0] = num;
}
}
转发 C 堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。时间复杂度O(n*logn) 如果从底部最后的父节点开始建堆，那么我们可以大概算一下： 假如有N个节点，那么高度为H=logN，最后一层每个父节点最多只需要下调1次，倒数第二层最多只需要下调2次，顶点最多需要下调H次，而最后一层父节点共有2(H-1)个,倒数第二层公有2(H-2),顶点只有1(2^0)个，所以总共的时间复杂度为s = 1 * 2^(H-1) + 2 * 2^(H-2) + ... + (H-1) * 2^1 + H * 2^0 将H代入后s= 2N - 2 - log2(N)，近似的时间复杂度就是O(N)。
建堆时间复杂度应该是O(m),不是O(mlogm)。堆调整的时间复杂度是O(logm)
最终时间复杂度等于，1次建堆时间+n次堆调整时间=O(m+nlogm)=O(nlogm)
更改堆元素后重建堆时间：O(nlogn)
推算过程：
1、循环 n -1 次，每次都是从根节点往下循环查找，所以每一次时间是 logn（也就是每次选取二叉树的一条路径往下比较交换，因为有lgn层，那么就要lgn的时间），总时间：logn(n-1) = nlogn - logn ；
综上所述：堆排序的时间复杂度为：O(nlogn)
算法设计：从一个很大很大的数组里找前N个最大数的思路之一
http://blog.csdn.net/yanzi1225627/article/details/8109035
网友评论