概念
堆是按照一定規(guī)則順序存儲的完全二叉樹(二叉樹是每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu))箕戳，其中可以分為大根堆和小根堆耗溜。
- 大根堆: 每個父結(jié)點的關(guān)鍵字都大于其子節(jié)點的關(guān)鍵字(如果有子結(jié)點的話)
- 小根堆: 每個父結(jié)點的關(guān)鍵字都小于其子節(jié)點的關(guān)鍵字(如果有子結(jié)點的話)
舉例來說奋刽，有個數(shù)組[A0, A1, A2, A3...An]假設(shè)父結(jié)點為Ai(其中i=1,2,…,n/2向下取整), 由二叉樹的排列規(guī)律可知其左子結(jié)點為A(2 * i + 1), 右子結(jié)點為A(2 * i + 2)因此大根堆必須滿足:Ai >= A(2 * i + 1)且Ai >= A(2 * i + 2), 小根堆必須滿足Ai <= A(2 * i + 1)且Ai <= A(2 * i + 2)
假如有個數(shù)列[3, 8, 15, 31, 25]砌溺，以二叉樹的形式表示如下圖：
首先需要按照堆的規(guī)則去構(gòu)造初始堆(即構(gòu)建一個完全二叉樹阁将，保證所有的父結(jié)點都比它的孩子結(jié)點數(shù)值大)，構(gòu)造規(guī)則為不同行從下往上侮措、相同行從右往左分別比較每一個子二叉樹的結(jié)點懈叹，如果父結(jié)點的關(guān)鍵字不是最大值，讓子節(jié)點中最大的值與父節(jié)點進行交換分扎。如此遍歷一遍后可以得到一個初始堆澄成。
注意: 當(dāng)?shù)谝患壎鏄渥咏Y(jié)點值大于父結(jié)點的值進行交換后，交換后新的子結(jié)點作為父結(jié)點的第二級子二叉樹中如果依然不是最大值則需要再次與其最大子結(jié)點進行交換畏吓。例:有個數(shù)組[5,3,1,8,7]在調(diào)整后變?yōu)閇5,8,1,3,7]->[8,5,1,3,7]墨状，然而此時由于在(5,3,7)這個子二叉樹中父結(jié)點5不是最大值，因此需要再次向下比較一次進行交換
在初始堆的基礎(chǔ)上交換數(shù)組中被調(diào)整的首尾元素菲饼，并讓數(shù)組重新調(diào)整為大根堆(這次調(diào)整忽略移到末尾的元素),采用遞歸的方式就可以依次把所有元素按升序排列到數(shù)組中了肾砂。
OC語言實例
給可變數(shù)組創(chuàng)建一個分類來存放該堆排序方法。
- (NSMutableArray *)heapSort
{
// 判斷是不是NSNumber的數(shù)組
BOOL isFullNSNumber = YES;
for (id value in self) {
if (![value isKindOfClass:[NSNumber class]]) {
isFullNSNumber = NO;
}
}
NSAssert(isFullNSNumber, @"數(shù)組中應(yīng)當(dāng)全是NSNumber對象");
// 初始化一個終止計算結(jié)點索引位置(一次排序后把最大值移動到數(shù)組計算結(jié)點范圍的末尾)
int endIndex = (int)(self.count - 1);
while (endIndex > 0) {
// 遍歷一次數(shù)組按照堆的規(guī)則排序一次
[self binaryTreeSortWithArray:self maxIndex:endIndex];
// 將建立堆得到的最大根與數(shù)組中最后一個數(shù)組互換
[self exchangeObjectAtIndex:0 withObjectAtIndex:endIndex--];
}
return self;
}
/// 二叉樹規(guī)則(大根堆)排序 -- (排序范圍為索引為0的位置到待排序結(jié)點最大索引位置)
- (void)binaryTreeSortWithArray:(NSMutableArray *)array maxIndex:(int)maxIndex
{
// 從可排序結(jié)點的最大索引處開始進行排序
for (int i = maxIndex; i >= 0; i--) {
// 獲取移動后的子結(jié)點的索引
int newIndex = [self compareNodesSizeWithMaxIndex:maxIndex fatherNodeIndex:i];
while (newIndex > 0) {
newIndex = [self compareNodesSizeWithMaxIndex:maxIndex fatherNodeIndex:newIndex];
}
}
}
/// 遞歸比較指定索引位置的結(jié)點與其左右子節(jié)點的大小
- (int)compareNodesSizeWithMaxIndex:(int)maxIndex fatherNodeIndex:(int)fatherIndex
{
// 獲取當(dāng)前索引位置的左右子節(jié)點索引
int leftIndex = fatherIndex * 2 + 1;
int rightIndex = fatherIndex * 2 + 2;
// 該索引和左右子節(jié)點值
NSNumber *currentValue = [self objectAtIndex:fatherIndex];
NSNumber *leftValue = nil;
NSNumber *rightValue = nil;
if (leftIndex <= maxIndex) {
leftValue = [self objectAtIndex:leftIndex];
}
if (rightIndex <= maxIndex) {
rightValue = [self objectAtIndex:rightIndex];
}
if (rightValue != nil) // 右子節(jié)點存在, 則左子節(jié)點必定存在, 判斷三者的值并把最大值換到父節(jié)點上
{
if (currentValue.doubleValue > leftValue.doubleValue && currentValue.doubleValue > rightValue.doubleValue) {
return -1;
}else {
// 與父節(jié)點進行交換的結(jié)點的索引
int index = (leftValue.doubleValue > rightValue.doubleValue ? leftIndex : rightIndex);
[self exchangeObjectAtIndex:fatherIndex withObjectAtIndex: index];
// 移動完畢之后同時還要進行(被移動到子節(jié)點的值)與(該被移動節(jié)點的左右子節(jié)點值)進行比較 -- 遞歸
return index;
}
}
else if (leftValue != nil) // 右結(jié)點不存在, 左結(jié)點存在, 判斷左結(jié)點是否大于父結(jié)點的值
{
if (currentValue.doubleValue < leftValue.doubleValue) {
[self exchangeObjectAtIndex:fatherIndex withObjectAtIndex:leftIndex];
return leftIndex;
}else {
return -1;
}
}
return -1;
}
