An \(O(1)\) priority queue based on algorithms from: Brown R, 1988. Calendar Queues: A Fast {O}(1)Priority Queue Implementation for the Simulation Event Set Problem. Communications of the ACM 31(10), 1220-1227. The priority queue has an \(O(1)\) time for insertion unlinking and holding of queue items with a favorable constant when compared to tree based priority queue data structures such as splay trees. Results presented by Brown show that this data structure outperforms tree based implementations and that simple ordered linked lists with \(O(n)\) operations outperform both calendar queues and tree based queues when there are less than ten items in the queue. More...

Functions
AlcCPQQueue *	AlcCPQQueueNew (AlcErrno *dstErr)
	Creates a new priority queue. More...

AlcCPQItem *	AlcCPQItemNew (AlcCPQQueue q, float priority, void entry, AlcErrno *dstErr)
	Creates a new priority queue item. More...

AlcErrno	AlcCPQQueueFree (AlcCPQQueue *q)
	Frees a priority queue. Queue item entries are not freed. More...

void	AlcCPQItemFree (AlcCPQQueue q, AlcCPQItem item)
	Frees a priority queue item by putting it onto the freeItem list. The queue items entries are not freed. More...

AlcErrno	AlcCPQEntryInsert (AlcCPQQueue q, float priority, void entry)
	Inserts an entry into the priority queue. This function calls AlcCPQItemNew() followed by AlcCPQItemInsert(). More...

AlcErrno	AlcCPQItemInsert (AlcCPQQueue q, AlcCPQItem item)
	Inserts an item into the priority queue. More...

AlcCPQItem *	AlcCPQItemUnlink (AlcCPQQueue *q)
	Unlinks and returns the item with the highest priority from the given priority queue. More...

Detailed Description

An \(O(1)\) priority queue based on algorithms from: Brown R, 1988. Calendar Queues: A Fast {O}(1)Priority Queue Implementation for the Simulation Event Set Problem. Communications of the ACM 31(10), 1220-1227. The priority queue has an \(O(1)\) time for insertion unlinking and holding of queue items with a favorable constant when compared to tree based priority queue data structures such as splay trees. Results presented by Brown show that this data structure outperforms tree based implementations and that simple ordered linked lists with \(O(n)\) operations outperform both calendar queues and tree based queues when there are less than ten items in the queue.

Author: Bill Hill

Date: July 2003

Version

Id: 7e4dd63d577f4c14efd8fb7481edbab613cc3672

: Address: MRC Human Genetics Unit, MRC Institute of Genetics and Molecular Medicine, University of Edinburgh, Western General Hospital, Edinburgh, EH4 2XU, UK.

: Copyright (C), [2012], The University Court of the University of Edinburgh, Old College, Edinburgh, UK.

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

Functions

Detailed Description