堆排序也是一種選擇排序垮衷。有大頂堆和小頂推展蒂，下面以一個(gè)數(shù)組為例簡(jiǎn)單說(shuō)明（大頂堆）又活。
NSMutableArray *array = [NSMutableArray arrayWithArray:@[@23,@56,@12,@78,@90,@876,@99]];
一、首先按照層的順序構(gòu)造一個(gè)完全二叉樹(shù)锰悼，然后初始化堆柳骄。
廢話少說(shuō)上代碼：
//建立初始堆
for (int i = (int)(array.count-1)/2; i >= 0; i--) {//最后一個(gè)非葉子結(jié)點(diǎn)開(kāi)始查找
[self heapOne:array length:array.count index:i];
}
- (void)heapOne:(NSMutableArray *)array length:(NSInteger)n index:(NSInteger)k{
NSInteger k1 = (2*k + 1);//左子樹(shù)的索引
NSInteger k2 = (2*k + 2);//又子樹(shù)的索引
if (k1 >= n && k2 >= n) {//K已是葉子結(jié)點(diǎn)
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) {//此時(shí)已經(jīng)是堆了
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];
}
}
二、每次遍歷即可找到最小值箕般。循環(huán)遍歷即可輸出從小到大的排序耐薯。
//邊輸出堆邊調(diào)整
NSUInteger n = array.count;
while (n > 0) {
NSLog(@"%@ ",array[0]);
array[0] = array[n-1];
n--;
[self heapOne:array length:n index:0];
}
