Latest 1.1.1
Homepage https://github.com/pavelosipov/POSDataStructures
License MIT
Platforms ios 6.0, requires ARC
Frameworks Foundation
Authors

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.");
}

Latest podspec

{
    "name": "POSDataStructures",
    "version": "1.1.1",
    "license": "MIT",
    "summary": "Data Structures Collection. Contains only Binary Heap at that moment.",
    "homepage": "https://github.com/pavelosipov/POSDataStructures",
    "authors": {
        "Pavel Osipov": "[email protected]"
    },
    "source": {
        "git": "https://github.com/pavelosipov/POSDataStructures.git",
        "tag": "1.1.1"
    },
    "platforms": {
        "ios": "6.0"
    },
    "requires_arc": true,
    "source_files": "POSDataStructures/*.{h,m}",
    "frameworks": "Foundation"
}

Pin It on Pinterest

Share This