本文共 1389 字，大约阅读时间需要 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中实现一个功能强大的小根堆。

转载地址：http://haifk.baihongyu.com/