本文共 1417 字，大约阅读时间需要 4 分钟。

Objective-C实现小根堆

在Objective-C中实现一个小根堆（Min-Heap）可以通过数组来完成。小根堆是一种完全二叉树，满足每个节点的值都小于或等于其子节点的值。以下是小根堆在Objective-C中的实现，包括插入、删除最小元素和获取最小元素的功能。

#import <Foundation/Foundation.h>

@interface MinHeap : NSObject @property (nonatomic, strong) NSMutableArray *heap; @end

插入元素

要将一个元素插入到小根堆中，可以按照以下步骤进行：

- (void)insertElement:(id)element
{
    [self.heap addObject:element];
    int index = [self.heap indexOfObject:element]; // 获取插入位置
    while (index > 0 && [self.heap[index/2] > element]) {
        [self.heap exchangeObjectAtIndex:index withAtIndex:index/2];
        index /= 2;
    }
}

删除最小元素

要删除最小的元素，可以使用以下方法：

- (id)extractMinimum
{
    if ([self.heap count] == 0) {
        return nil;
    }
    
    id min = [self.heap firstObject];
    [self.heap removeObjectAtIndex:0];
    
    int lastIndex = [self.heap count] - 1;
    int parentIndex = 0;
    
    while (lastIndex > 0 && [self.heap[parentIndex] > [self.heap[lastIndex]]) {
        [self.heap exchangeObjectAtIndex:parentIndex withAtIndex:lastIndex];
        lastIndex /= 2;
        parentIndex = lastIndex / 2;
    }
    
    return min;
}

获取最小元素

要获取当前堆中的最小元素，可以直接访问堆的第一个元素：

- (id)peekMinimum
{
    return [self.heap firstObject];
}

代码解释

小根堆的性质

小根堆的主要特点是：

• 父节点的值小于或等于子节点的值。
• 堆的结构是完全二叉树，除了最后一个叶子节点外，其他节点都有两个子节点。

通过以上方法，可以轻松地在Objective-C中实现一个功能强大的小根堆。