Mission Base

Program Base Library

pblHeap - Binary Min Max Heap Implementation

Heap in C, C heap, heap in C, Heap in C, C-Heap, binary heap in C, binary min-max heap in C.


Documentation

Open source C implementation of a binary heap.

This heap orders elements according to a compare function specified. A heap does not permit null elements.

The head of this heap is the biggest element according to the compare function specified. If multiple elements are tied for highest priority, the head is one of those elements -- ties are broken arbitrarily. The heap retrieval operations pblHeapGet and pblHeapRemoveFirst access the element at the head of the heap.

A heap is unbounded, but has an internal capacity governing the size of an array used to store the elements on the heap. It is always at least as large as the heap size. As elements are added to a heap, its capacity grows automatically. The details of the growth policy are not specified.

The Iterator provided in method pblHeapIterator() is not guaranteed to traverse the elements of the Heap in any particular order.

Implementation note: this implementation provides O(log(n)) time for the insertion methods; O(log(n)) time for the removal methods; and constant time for the retrieval methods.


Constructors and Destructors

  • pblHeapNew Creates a new heap.
  • pblHeapFree Frees the heap's memory from heap.
  • pblHeapClear Removes all of the elements from the heap.

    Adding to a Heap

  • pblHeapInsert Inserts the element into the heap and maintains the heap condition of the heap.
  • pblHeapAddLast Adds the element to the end of the heap without ensuring the heap condition.
  • pblHeapConstruct Constructs a heap using 'bottom-up heap construction'.

    Accessing Heap Elements

  • pblHeapGetFirst Returns but does not remove the element at the top of the heap.
  • pblHeapGet Returns the element at the specified position in the heap. HR>

    Removing from a Heap

  • pblHeapRemoveAt Removes the element at the specified position from the heap, maintaining the heap condition of the heap.
  • pblHeapRemoveFirst Removes the biggest element from the heap, maintaining the heap condition of the heap.
  • pblHeapRemoveLast Removes the last element from the heap, maintaining the heap condition of the heap.
  • pblHeapClear Removes all of the elements from the heap.

    Functions on Heaps

  • pblHeapEnsureCapacity Increases the capacity of the heap, if necessary.
  • pblHeapEnsureCondition Ensures the heap condition of the heap for the element with the given index.
  • pblHeapEnsureConditionFirst Ensures the heap condition for the first element.
  • pblHeapGetCapacity Returns the capacity of the heap.
  • pblHeapIsEmpty Tests if the heap has no elements.
  • pblHeapIterator Returns an iterator over the elements in the heap.
  • pblHeapJoin Joins the two heaps by moving all elements of the 'other' heap.
  • pblHeapSetCompareFunction Sets an application specific compare function for the elements of the heap.
  • pblHeapSize Returns the number of elements in the heap.
  • pblHeapTrimToSize Trims the capacity of the heap to the heap's current size.

    Alphabetic List of Heap Functions

  • pblHeapAddLast Adds the element to the end of the heap without ensuring the heap condition.
  • pblHeapClear Removes all of the elements from the heap.
  • pblHeapConstruct Constructs a heap using 'bottom-up heap construction'.
  • pblHeapEnsureCapacity Increases the capacity of the heap, if necessary.
  • pblHeapEnsureCondition Ensures the heap condition of the heap for the element with the given index.
  • pblHeapEnsureConditionFirst Ensures the heap condition for the first element.
  • pblHeapFree Frees the heap's memory from heap.
  • pblHeapGet Returns the element at the specified position in the heap.
  • pblHeapGetCapacity Returns the capacity of the heap.
  • pblHeapGetFirst Returns but does not remove the element at the top of the heap.
  • pblHeapInsert Inserts the element into the heap and maintains the heap condition of the heap.
  • pblHeapIsEmpty Tests if the heap has no elements.
  • pblHeapIterator Returns an iterator over the elements in the heap.
  • pblHeapJoin Joins the two heaps by moving all elements of the 'other' heap.
  • pblHeapNew Creates a new heap.
  • pblHeapRemoveAt Removes the element at the specified position from the heap, maintaining the heap condition of the heap.
  • pblHeapRemoveFirst Removes the biggest element from the heap, maintaining the heap condition of the heap.
  • pblHeapRemoveLast Removes the last element from the heap, maintaining the heap condition of the heap.
  • pblHeapSetCompareFunction Sets an application specific compare function for the elements of the heap.
  • pblHeapSize Returns the number of elements in the heap.
  • pblHeapTrimToSize Trims the capacity of the heap to the heap's current size.

    Alphabetic index


    GET PBL:


    Copyright(C) 2003 - 2015 Peter Graf, this software is distributed under the GNU Lesser General Public License.
    This page was generated with the help of DOC++.