heap/priority queue implementation in "template" C
updated the function list in heapq.h to include the type signature
added tests for heapify/heapify_max failure due to lt failure (ie, returning -1)

heads

tip
browse log

clone

read-only
https://hg.sr.ht/~dalke/heapq
read/write
ssh://hg@hg.sr.ht/~dalke/heapq

#heapq

This is a "template" C heap/priority queue header-only implementation, strongly based on Python's "heapq" module implementation. Quoting the Python documentation :

The API below differs from textbook heap algorithms in two aspects: (a) We use zero-based indexing. ... (b) Our pop method returns the smallest item, not the largest (called a “min heap” in textbooks; a “max heap” is more common in texts because of its suitability for in-place sorting).

The min heap functions are:

  • {HEAPQ_NAME}_heapify(HEAPQ_INDEX_TYPE heap_size, HEAPQ_TYPE *heap):
    Transform array into a min-heap, in-place.
  • {HEAPQ_NAME}_heappush(HEAPQ_INDEX_TYPE *heap_size, HEAPQ_TYPE *heap, HEAPQ_TYPE *item):
    Push an item into the heap.
  • {HEAPQ_NAME}_heappop(HEAPQ_INDEX_TYPE *heap_size, HEAPQ_TYPE *heap, HEAPQ_TYPE *dest):
    Pop the smallest item.
  • {HEAPQ_NAME}_heapreplace(HEAPQ_INDEX_TYPE heap_size, HEAPQ_TYPE *heap, HEAPQ_TYPE *item):
    Get the smallest item then add a new one.
  • {HEAPQ_NAME}_heappushpop(HEAPQ_INDEX_TYPE heap_size, HEAPQ_TYPE *heap, HEAPQ_TYPE *item):
    Push an item then pop the smallest item.
  • {HEAPQ_NAME}_heapadjust(HEAPQ_INDEX_TYPE heap_size, HEAPQ_TYPE *heap):
    Restore the heap after modifying the first element.
  • {HEAPQ_NAME}_heapsort(HEAPQ_INDEX_TYPE heap_size, HEAPQ_TYPE *heap):
    Sort the (previously heapified) heap, largest to smallest.

The functions ending "_max" implement a max heap:

  • {HEAPQ_NAME}_heapify_max(HEAPQ_INDEX_TYPE heap_size, HEAPQ_TYPE *heap):
    Transform array into a max-heap, in-place.
  • {HEAPQ_NAME}_heappush_max(HEAPQ_INDEX_TYPE *heap_size, HEAPQ_TYPE *heap, HEAPQ_TYPE *item):
    Push an item into the heap.
  • {HEAPQ_NAME}_heappop_max(HEAPQ_INDEX_TYPE *heap_size, HEAPQ_TYPE *heap, HEAPQ_TYPE *dest):
    Pop the largest item.
  • {HEAPQ_NAME}_heapreplace_max(HEAPQ_INDEX_TYPE heap_size, HEAPQ_TYPE *heap, HEAPQ_TYPE *item):
    Get the largest item then add a new one.
  • {HEAPQ_NAME}_heappushpop_max(HEAPQ_INDEX_TYPE heap_size, HEAPQ_TYPE *heap, HEAPQ_TYPE *item):
    Push an item then pop the largest item.
  • {HEAPQ_NAME}_heapadjust_max(HEAPQ_INDEX_TYPE heap_size, HEAPQ_TYPE *heap):
    Restore the heap after modifying the first element.
  • {HEAPQ_NAME}_heapsort_max(HEAPQ_INDEX_TYPE heap_size, HEAPQ_TYPE *heap):
    Sort the (previously max-heapified) heap, smallest to largest.

This implementation does not define an abstract data type. The heap is passed in as a size and pointer to an existing array. Entries are copied and moved by value. The caller is responsible for ensuring there is enough space.

The user must #define HEAPQ_NAME, as the prefix for the generated functions and #define HEAPQ_TYPE to the heap element type.

The user may #define HEAPQ_LT(a, b) to change how two values are compared, and #define HEAPQ_INDEX_TYPE to change the index type. See heapq.h for details.

#Tests

The unit tests are in test_heapq.py. It uses the cffi package to build the _test_heapq module used for the tests. You will also need a C compiler.

# install cffi
pip install cffi

# run the unit tests
python test_heapq.py

#Example

The file fizzbuzz.c contains a variation of FizzBuzz based on a priority queue with several tasks.

#Alternatives

For alternative template C implementations of a priority queue/heap, see:

  • Pottery - A container and algorithm template library in C

  • klib - A standalone and lightweight C library

This code is distributed under the terms of the "MIT License" and the "Python Software Foundation License Version 2".

Copyright (c) 2023 Andrew Dalke Scientific, AB (Sweden)

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.

Parts of this code and comments are derived from CPython's Modules/_heapqmodule.c covered under the following license:

  PYTHON SOFTWARE FOUNDATION LICENSE VERSION 2
  Copyright (c) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
  2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020,
  2021, 2022, 2023 Python Software Foundation; All Rights Reserved

  C implementation derived directly from heapq.py in Py2.3 which was
  written by Kevin O'Connor, augmented by Tim Peters, annotated by
  François Pinard, and converted to C by Raymond Hettinger.

I thank Christopher Swenson's sort.h for teaching me how to write "template" C.