堆排序也是一种选择排序。有大顶堆和小顶推，下面以一个数组为例简单说明（大顶堆）。
NSMutableArray *array = [NSMutableArray arrayWithArray:@[@23,@56,@12,@78,@90,@876,@99]];
一、首先按照层的顺序构造一个完全二叉树，然后初始化堆。
废话少说上代码：
//建立初始堆
for (int i = (int)(array.count-1)/2; i >= 0; i--) {//最后一个非叶子结点开始查找
[self heapOne:array length:array.count index:i];
}
- (void)heapOne:(NSMutableArray *)array length:(NSInteger)n index:(NSInteger)k{
NSInteger k1 = (2*k + 1);//左子树的索引
NSInteger k2 = (2*k + 2);//又子树的索引
if (k1 >= n && k2 >= n) {//K已是叶子结点
return;
}
NSInteger a1 = NSIntegerMax;
NSInteger a2 = NSIntegerMax;
if (k1 < n) {
a1 = [array[k1] integerValue]; //左孩子值
}
if (k2 < n) {
a2 = [array[k2] integerValue];//右孩纸值
}
if ([array[k] intValue] <= a1 && [array[k] intValue] <= a2) {//此时已经是堆了
return;
}
if(a1 < a2){
id m = array[k1];
array[k1] = array[k];
array[k] = m;
[self heapOne:array length:n index:k1];
}else{
id m = array[k2];
array[k2] = array[k];
array[k] = m;
[self heapOne:array length:n index:k2];
}
}
二、每次遍历即可找到最小值。循环遍历即可输出从小到大的排序。
//边输出堆边调整
NSUInteger n = array.count;
while (n > 0) {
NSLog(@"%@ ",array[0]);
array[0] = array[n-1];
n--;
[self heapOne:array length:n index:0];
}
