Mission Base

Program Base Library

pblPriorityQueue - Priority Queue Implementation

PriorityQueue in C, C priority queue, priority queue in C, Heap in C, C-Heap, binary heap in C, binary max heap in C.


Documentation

Open source C implementation of a priority queue based on a binary max-heap. This C implementation is similar to the Java PriorityQueue interface.

An unbounded priority queue based on a priority heap. The implementation is based on a pblHeap.
This queue orders elements according to an integer priority specified with each element. A priority queue does permit null elements.

The head of this queue is the element with the highest priority value. If multiple elements are tied for highest priority, the head is one of those elements -- ties are broken arbitrarily. The queue retrieval operations pblPriorityQueueGet and pblPriorityQueueRemoveFirst access the element at the head of the queue.

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

The Iterator provided in method pblPriorityQueueIterator() is not guaranteed to traverse the elements of the PriorityQueue 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.

See also the source file pblPriorityQueueTest.c for an example on how to use the Priority Queue implementation.


Constructors and Destructors

  • pblPriorityQueueNew Creates a new priority queue.
  • pblPriorityQueueFree Frees the priority queue's memory from heap.
  • pblPriorityQueueClear Removes all of the elements from the priority queue.

    Adding to a PriorityQueue

  • pblPriorityQueueInsert Inserts the element with the specified priority into the priority queue and maintains the heap condition of the priority queue.
  • pblPriorityQueueAddLast Adds the element with the specified priority to the end of the priority queue without ensuring the heap condition.
  • pblPriorityQueueConstruct Constructs a priority queue using 'bottom-up heap construction'.

    Accessing PriorityQueue Elements

  • pblPriorityQueueGetFirst Returns but does not remove the element with the highest priority in the priority queue.
  • pblPriorityQueueGet Returns the element at the specified position in the priority queue.
  • pblPriorityQueueChangePriorityAt Changes the priority of the element at the specified position of the priority queue, maintaining the heap condition of the queue.
  • pblPriorityQueueChangePriorityFirst Changes the priority of the first element of the priority queue, maintaining the heap condition of the queue.

    Removing from a PriorityQueue

  • pblPriorityQueueRemoveAt Removes the element at the specified position from the priority queue, maintaining the heap condition of the queue.
  • pblPriorityQueueRemoveFirst Removes the element with the highest priority from the priority queue, maintaining the heap condition of the queue.
  • pblPriorityQueueRemoveLast Removes the last element from the priority queue, maintaining the heap condition of the queue.
  • pblPriorityQueueClear Removes all of the elements from the priority queue.

    Functions on PriorityQueues

  • pblPriorityQueueEnsureCapacity Increases the capacity of the priority queue, if necessary.
  • pblPriorityQueueIsEmpty Tests if the priority queue has no elements.
  • pblPriorityQueueIterator Returns an iterator over the elements in the queue.
  • pblPriorityQueueSize Returns the number of elements in the priority queue.
  • pblPriorityQueueTrimToSize Trims the capacity of the queue to the priority queue's current size.

    Alphabetic List of PriorityQueue Functions

  • pblPriorityQueueAddLast Adds the element with the specified priority to the end of the priority queue without ensuring the heap condition.
  • pblPriorityQueueChangePriorityAt Changes the priority of the element at the specified position of the priority queue, maintaining the heap condition of the queue.
  • pblPriorityQueueChangePriorityFirst Changes the priority of the first element of the priority queue, maintaining the heap condition of the queue.
  • pblPriorityQueueClear Removes all of the elements from the priority queue.
  • pblPriorityQueueConstruct Constructs a priority queue using 'bottom-up heap construction'.
  • pblPriorityQueueEnsureCapacity Increases the capacity of the priority queue, if necessary.
  • pblPriorityQueueFree Frees the priority queue's memory from heap.
  • pblPriorityQueueGet Returns the element at the specified position in the priority queue.
  • pblPriorityQueueGetCapacity Returns the capacity of the priority queue.
  • pblPriorityQueueGetFirst Returns but does not remove the element with the highest priority in the priority queue.
  • pblPriorityQueueInsert Inserts the element with the specified priority into the priority queue and maintains the heap condition of the priority queue.
  • pblPriorityQueueIsEmpty Tests if the priority queue has no elements.
  • pblPriorityQueueIterator Returns an iterator over the elements in the queue.
  • pblPriorityQueueJoin Joins the two priority queues by moving all elements of the 'other' queue.
  • pblPriorityQueueNew Creates a new priority queue.
  • pblPriorityQueueRemoveAt Removes the element at the specified position from the priority queue, maintaining the heap condition of the queue.
  • pblPriorityQueueRemoveFirst Removes the element with the highest priority from the priority queue, maintaining the heap condition of the queue.
  • pblPriorityQueueRemoveLast Removes the last element from the priority queue, maintaining the heap condition of the queue.
  • pblPriorityQueueSize Returns the number of elements in the priority queue.
  • pblPriorityQueueTrimToSize Trims the capacity of the queue to the priority queue'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++.