概念
堆是一棵顺序存储的完全二叉树,分为大根堆和小根堆
分类
-
小根堆
每个结点的关键字都不大于其孩子结点的关键字。
-
大根堆
每个结点的关键字都不小于其孩子结点的关键字
举例
举例来说，对于n个元素的序列{R0, R1, ... , Rn}当且仅当满足下列关系之一时，称之为堆：
(1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
(2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)
其中i=1,2,…,n/2向下取整;
如上图所示，序列R{3, 8, 15, 31, 25}是一个典型的小根堆。
堆中有两个父结点，元素3和元素8。
元素3在数组中以R[0]表示，它的左孩子结点是R[1]，右孩子结点是R[2]。
元素8在数组中以R[1]表示，它的左孩子结点是R[3]，右孩子结点是R[4]，它的父结点是R[0]。可以看出，它们满足以下规律：
总结
设当前元素在数组中以R[i]表示，那么，
(1) 它的左孩子结点是：R[2*i+1];
(2) 它的右孩子结点是：R[2*i+2];
(3) 它的父结点是：R[(i-1)/2];
(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。
OC代码实现
思路
根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。
每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。
其实思路很简单，最重要的是怎么将一个初始化的数组构建一个大根堆呢？？
采用的方式是<font color='red' size='4'>自下而上，从右到左</font>自下而上，从右到左的思路，以3个为一个单元，进行构建。
这么说大家可能还会搞不懂，接下来让我们举例说明！
假设有一个无序数组[1, 3, 4, 5, 2, 6, 9, 7, 8, 0]
这其中有个很重要的操作就是递归操作，图中的(4)
具体代码
代码中我加了很多注释，相信大家能够看懂。:-D
// ViewController.m
// Copyright © 2017年 FlyOceanFish. All rights reserved.
//
#import "ViewController.h"
@interface ViewController ()
{
NSMutableArray *array;
}
@end
@implementation ViewController
- (void)viewDidLoad {
[super viewDidLoad];
array = [@[@20,@1,@4,@3,@40,@22,@9,@35,@6,@11,@18,@0] mutableCopy];
for (NSInteger i=array.count/2; i>=0; i--) {
[self headpSort:array parent:i length:array.count];//初始化建立大根堆
}
for (NSInteger i=array.count-1; i>0; i--) {//循环交换将最大的R0放到最后边
NSInteger tem = [array[0] integerValue];
[array replaceObjectAtIndex:0 withObject:@([array[i] integerValue])];
[array replaceObjectAtIndex:i withObject:@(tem)];
[self headpSort:array parent:0 length:i];//交换完成后，树中最大的自然排到了最后边，故只要对剩余的i个数重新调整为大根堆
NSLog(@"排序后:%@",array);
}
}
/**
这种遍历比较是自下而上的进行比较方式（从树的下部往上比较，以三个数为一个部分（假设左右子节点都有））
*/
- (void)headpSort:(NSMutableArray *)array parent:(NSInteger)parent length:(NSInteger)length{
NSInteger parentValue = [array[parent] intValue];
NSInteger rightChild = 2*parent+2;
NSInteger maxChildIndex = -1;
NSInteger maxChild = -1;
if (rightChild<length) {//这里的操作是先比较左右子节点的大小，那其中最大的再去跟父节点比较
if (array[rightChild]<array[rightChild-1]) {
maxChild =[array[rightChild-1] intValue];
maxChildIndex = rightChild-1;
}else{
maxChild =[array[rightChild] intValue];
maxChildIndex = rightChild;
}
}else if (rightChild-1<length){
maxChild = [array[rightChild-1] intValue];
maxChildIndex = rightChild-1;
}
if (maxChild>0) {
if ([array[parent] intValue]<maxChild) {
[array replaceObjectAtIndex:parent withObject:@(maxChild)];
[array replaceObjectAtIndex:maxChildIndex withObject:@(parentValue)];
[self headpSort:array parent:maxChildIndex length:length];//如果子节点是其他子节点的父节点的话，有可能比其子节点小，故需要递归
}
}
}
@end
总结
看的过程可能很爽，一看就明白，也有可能云里雾里。实践出真知！所以建议大家用代码根据原理亲自去实现一遍，相信一切皆明了。
