Heap Abstract Class (BinaryHeap and FibonacciHeap)

This defines and declares a Heap abstract base class and two concrete subclasses, BinaryHeap and FibonacciHeap. Subclassing of the Heap class is possible for other structures.

The base class defines the user interface and the implementations add the storage and manipulation backend. The user interface includes the traditional heap interface with push, pop, top, size, and empty, as well as a more Apple-like interface including synonyms addObject, removeTopObject, topObject, and count.

Heaps can be declared as minimum heaps (top object is always the minimum) or maximum heaps (top object is always the maximum). A heap without explicit minimum or maximum will be the default for the heap subclass type; in general these will be maximum heaps.

Heaps can also be declared providing an NSComparator that defines relationships between stored objects or with an NSSortDescriptor to define order.

The objects stored in the heap must implement - (NSComparisonResult) compare: (MyClass *) otherObject; if no comparator or sort descriptor is supplied. They must also implement - (BOOL) isEqual: (id) otherObject; although this is only really needed if methods that need to identify objects are used such as containsObject:, removeObject:, and replaceObject:withObject:.

All heaps are mutable and therefore not thread safe. This seemed appropriate since there is no random access to a heap, if it was not mutable only its top element would every be accessible.

Version 1.00.00

Installation and Usage

Copy both Heap.h and Heap.m files to your project as well as the interface and implementation files for the specific type or types of heap you intend to use (BinaryHeap.h and BinaryHeap.m, and/or FibonacciHeap.h and FibonacciHeap.m). Usage is simple, declare your heap and use it.

BinaryHeap *heap = [BinaryHeap maxHeap];
[heap push: @1];
[heap push: @5];
[heap push: @2];
NSLog( @"The top of the heap is %@\n", heap.top );
// Will output:
//   The top of the heap is 5

Should be compatible with iOS or Mac OS X.

Heap Methods

Traditional heap interface methods:

- (void) push: (ObjectType) object;: Adds the object to the heap. Pushing a nil does nothing.
- (ObjectType) pop;: Removes and returns the top object from the heap. If the heap is empty returns nil.
- (ObjectType) top;: Returns the top object from the heap. If the heap is empty returns nil.
- (NSUInteger) size;: Returns the number of objects in the heap.
- (BOOL) empty;: Returns YES if the heap's size is zero.

More Apple-like interface methods:

- (void) addObject: (ObjectType) object;: Pushes the object to the heap. Adding a nil does nothing.
- (void) removeTopObject;: Removes the top object from the heap. If the heap is empty returns nil.
- (ObjectType) topObject;: Returns the top object from the heap. If the heap is empty returns nil.
- (NSUInteger) count;: Returns the number of objects in the heap.

Additional / expanded interface methods:

- (void) addObjectsFromArray: (NSArray *) array;: Pushes each object from the array to the heap.
- (void) setObjectsFromArray: (NSArray *) array;: Replaces the content of the heap with the objects from the array. This is functionally equivalent to:
[heap removeAllObjects]; [heap addObjectsFromArray: array];
however subclasses may override this if there is a more efficient way to do it.
- (void) replaceTopObjectWithObject: (id) anObject;: Replaces the top object on the heap with anObject (which, of course, may not longer be the top object). This is functionally equivalent to:
[heap pop]; [heap push: anObject];
however subclasses may override this if there is a more efficient way to do it. If anObject is nil then the top object is removed.
- (void) replaceObject: (id) object withObject: (id) newObject;: Replaces the object in the heap with the newObject. This is functionally equivalent to:
[heap removeObject: object]; [heap push: newObject];
however subclasses may override this if there is a more efficient way to do it. If object is nil then nothing is removed. If newObject is nil then nothing is added.
- (BOOL) containsObject: (ObjectType) anObject;: Returns YES if any object in the heap returns YES to isEqual: anObject. If anObject is nil the return value will always be NO
- (void) removeObject: (id) object;: Removes the object from the heap. If object is nil nothing is changed.
- (void) removeAllObjects;: Removes all objects from the heap. This is functionally equivalent to:
while( [heap pop] );
however subclasses may override this if there is a more efficient way to do it.
- (NSArray *) allObjects;: Returns an array containing all the objects in the heap. It the heap is empty then an empty array is returned. No specific order is guaranteed.
- (BOOL) isEqualToHeap: (Heap *) heap;: Two heaps are considered equal if they contain the same number of objects, their top objects are equal and every object is contained in the other heap. Therefore a BinaryHeap can be equal to a FibonacciHeap. Also an empty minimum heap will be equal to an empty maximum heap.

Heap Creation

- (instancetype) init;
- (instancetype) initMax;
- (instancetype) initMin;
- (instancetype) initWithComparator: (NSComparator) comparator;
- (instancetype) initWithSortDescriptor: (NSSortDescriptor *) sd;
- (instancetype) initWithObject: (ObjectType) object;
- (instancetype) initMinWithObject: (ObjectType) object;
- (instancetype) initMaxWithObject: (ObjectType) object;
- (instancetype) initWithComparator: (NSComparator) comparator andObject: (ObjectType) object;
- (instancetype) initWithSortDescriptor: (NSSortDescriptor *) sd andObject: (ObjectType) object;
- (instancetype) initWithObjects: (ObjectType) firstObj, ... NS_REQUIRES_NIL_TERMINATION;
- (instancetype) initMinWithObjects: (ObjectType) firstObj, ... NS_REQUIRES_NIL_TERMINATION;
- (instancetype) initMaxWithObjects: (ObjectType) firstObj, ... NS_REQUIRES_NIL_TERMINATION;
- (instancetype) initWithComparator: (NSComparator) comparator andObjects: (ObjectType) firstObj, ... NS_REQUIRES_NIL_TERMINATION;
- (instancetype) initWithSortDescriptor: (NSSortDescriptor *) sd andObjects: (ObjectType) firstObj, ... NS_REQUIRES_NIL_TERMINATION;
- (instancetype) initWithArray: (NSArray *) array;
- (instancetype) initMinWithArray: (NSArray *) array;
- (instancetype) initMaxWithArray: (NSArray *) array;
- (instancetype) initWithComparator: (NSComparator) comparator andArray: (NSArray *) array;
- (instancetype) initWithSortDescriptor: (NSSortDescriptor *) sd andArray: (NSArray *) array;
- (instancetype) initWithObjects: (const ObjectType *) objects count: (NSUInteger) cnt;
- (instancetype) initMinWithObjects: (const ObjectType *) objects count: (NSUInteger) cnt;
- (instancetype) initMaxWithObjects: (const ObjectType *) objects count: (NSUInteger) cnt;
- (instancetype) initWithComparator: (NSComparator) comparator andObjects: (const ObjectType *) objects count: (NSUInteger) cnt;
- (instancetype) initWithSortDescriptor: (NSSortDescriptor *) sd andObjects: (const ObjectType *) objects count: (NSUInteger) cnt;
+ (instancetype) heap;
+ (instancetype) minHeap;
+ (instancetype) maxHeap;
+ (instancetype) heapWithComparator: (NSComparator) comparator;
+ (instancetype) heapWithSortDescriptor: (NSSortDescriptor *) sd;
+ (instancetype) heapWithObject: (ObjectType) object;
+ (instancetype) minHeapWithObject: (ObjectType) object;
+ (instancetype) maxHeapWithObject: (ObjectType) object;
+ (instancetype) heapWithComparator: (NSComparator) comparator andObject: (ObjectType) object;
+ (instancetype) heapWithSortDescriptor: (NSSortDescriptor *) sd andObject: (ObjectType) object;
+ (instancetype) heapWithObjects: (ObjectType) firstObj, ... NS_REQUIRES_NIL_TERMINATION;
+ (instancetype) minHeapWithObjects: (ObjectType) firstObj, ... NS_REQUIRES_NIL_TERMINATION;
+ (instancetype) maxHeapWithObjects: (ObjectType) firstObj, ... NS_REQUIRES_NIL_TERMINATION;
+ (instancetype) heapWithComparator: (NSComparator) comparator andObjects: (ObjectType) firstObj, ... NS_REQUIRES_NIL_TERMINATION;
+ (instancetype) heapWithSortDescriptor: (NSSortDescriptor *) sd andObjects: (ObjectType) firstObj, ... NS_REQUIRES_NIL_TERMINATION;
+ (instancetype) heapWithArray: (NSArray *) array;
+ (instancetype) minHeapWithArray: (NSArray *) array;
+ (instancetype) maxHeapWithArray: (NSArray *) array;
+ (instancetype) heapWithComparator: (NSComparator) comparator andArray: (NSArray *) array;
+ (instancetype) heapWithSortDescriptor: (NSSortDescriptor *) sd andArray: (NSArray *) array;
+ (instancetype) heapWithObjects: (const ObjectType *) objects count: (NSUInteger) cnt;
+ (instancetype) minHeapWithObjects: (const ObjectType *) objects count: (NSUInteger) cnt;
+ (instancetype) maxHeapWithObjects: (const ObjectType *) objects count: (NSUInteger) cnt;
+ (instancetype) heapWithComparator: (NSComparator) comparator andObjects: (const ObjectType *) objects count: (NSUInteger) cnt;
+ (instancetype) heapWithSortDescriptor: (NSSortDescriptor *) sd andObjects: (const ObjectType *) objects count: (NSUInteger) cnt;

Existing Subclasses

BinaryHeap

The binary heap subclass uses an NSMutableArray as its storage mechanism. It takes no additional space for pointers or other elements for the objects being stored. The binary heap is described in detail on its Wikipedia page. Because its backing storage is a mutable array it adds some addtional initializes including:

- (instancetype) initWithCapacity: (NSUInteger) numItems;
- (instancetype) initMinWithCapacity: (NSUInteger) numItems;
- (instancetype) initMaxWithCapacity: (NSUInteger) numItems;
- (instancetype) initWithComparator: (NSComparator) comparator andCapacity: (NSUInteger) numItems;
- (instancetype) initWithSortDescriptor: (NSSortDescriptor *) sd andCapacity: (NSUInteger) numItems;

Fibonacci Heap

A Fibonacci heap is a heap data structure similar to the binomial heap. It defers ‘clean up’ jobs until later to improved to O(1) several operations. Internally it stores its data in nodes organized as doubly linked lists conecting siblings and parent/child pointers for heap relationships so there is greater memory usage than with the Binary Heap implementation. Much of the code was derived from examples on the Growing with the Web Fibonacci heap page.

Subclassing Instructions

Heaps is implemented as a Class Cluster. The Heap class itself is an abstract super class with no storage. By default, size, pop, and top return nil or zero, empty returns YES, containsObject: returns NO, removeObject: does nothing, and push: throws an exception.

Subclasses of Heap are required to declare and manage the storage of the heap objects and implement the minimum subset of methods described below. They can also define additional methods as appropriate.

Methods that must be overridden in all subclasses include:

- (void) push: (ObjectType) object;: This should add the object to the heap or do nothing if the object is nil. It should not call [super push: object].
- (ObjectType) pop;: This should remove and return the top object in the heap or return nil if the heap is empty. It should not call [super pop].
- (ObjectType) top;: This should return the top object in the heap or nil if the heap is empty. It should not call [super top].
- (NSUInteger) size;: This should return the number of objects in the heap. It should not call [super size].
- (void) removeObject: (id) object;: This should efficiently search through the heap and delete the first object that returns YES when passed object to isEqual:. It should gracefully do nothing if object is nil. It should not call [super removeObject: object]
- (BOOL) containsObject: (ObjectType) anObject;: This should efficiently search through the heap and return YES if any object in the heap returns YES when passed anObject to isEqual:. It should gracefully return nil if anObject is nil. It should not call [super containsObject: object]
- (BOOL) isEqualToHeap: (Heap *) otherHeap;: This should call [super isEqualToHeap: otherHeap] then, if this returns YES go through each object in the heap and call [otherHeap contains: object], returning NO if the other heap returns NO.

The subclass must also implement

- (instancetype) init;
- (instancetype) initMax;
- (instancetype) initMin;
- (instancetype) initWithComparator: (NSComparator) comparator;
- (instancetype) initWithSortDescriptor: (NSSortDescriptor *) sd;

These should each call their [super] then initialize the storage as needed.

Within your subclass you should use - (NSComparisonResult) heapCompareNode: (const id) lhs toNode: (const id) rhs for all object comparisons. For example, here is the internal bubble up code from the BinaryHeap implementation.

- (void) bubbleUpFromIndex: (NSUInteger) i {
	NSUInteger p = parentOf(i);
	while( i > 0 && [self heapCompareNode: _objects[i] toNode: _objects[p]] == NSOrderedDescending) {
		ObjectType t = _objects[p];
		_objects[p] = _objects[i];
		_objects[i] = t;
		i = p;
		p = parentOf(i);
	}
}

This will make your implementation work with the built in comparators, user specified comparators or sort descriptors.

Testing is also implemented. If you create a new heap type subclass, make a copy of [test/testFib.m][] or [test/testBin.m][], modify it to import your header file, and define your class name as HEAP_TYPE. Compile and run. No output means no errors identified. (Sorry about the inelegant testing, it was just what I had on the fly)

License

The MIT License (MIT)

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

LavaSlider/Heap