Binary Heap implementation for Objective-C with ARC
Objective-C Ruby
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
POSDataStructures.xcodeproj
POSDataStructures
POSDataStructuresTests
.gitignore
LICENSE
POSDataStructures.podspec
README.md

README.md

Data Structures Collection

Version

Repository contains data structures which are completely absent in iOS SDK or its implementation their is insufficient. All of them were tested in production code of iOS 5.0 applications with ARC memory management model.

POSBinaryHeap

Binary Heap is implemented over NSMutableArray. There is CFBinaryHeapRef in Core Foundation framework. But CFBinaryHeapRef has a very poor interface for removing objects from it. The only possible options are CFBinaryHeapRemoveAllValues and CFBinaryHeapRemoveMinimumValue. So there are two reasons to create my Binary Heap:

  • Make possible to remove equal and identical objects from the heap.
  • Make Objective-C ARC compatible implementation instead of plain C.

Example

Ascending heap sort implementation with POSBinaryHeap

- (void)testAscendingHeapSort {
    POSBinaryHeap *heap = [[POSBinaryHeap alloc] initWithOrderingType:POSBinaryHeapOrderingAscending
                                                           comparator:^(NSNumber *l, NSNumber *r) {
        return [l compare:r];
    }];
    [heap addObjectsFromArray:@[@5, @4, @3, @2, @1, @0, @0, @1, @2, @3, @4, @5]];
    NSMutableArray *sortedArray = [NSMutableArray new];
    while ([heap count]) {
        [sortedArray addObject:[heap popTopObject]];
    }
    const BOOL sorted = [sortedArray isEqualToArray:@[@0, @0, @1, @1, @2, @2, @3, @3, @4, @4, @5, @5]];
    STAssertTrue(sorted, @"Ascending heap sort is working.");
}