src/heap.h File Reference

A min-heap that dynamically expands its capacity when necessary. More...

#include <stdlib.h>
#include <stdbool.h>
#include "utils.h"

Include dependency graph for heap.h:

Go to the source code of this file.

Defines
#define	DEFAULT_HEAP_CAPACITY
	The default initial capacity of a heap.
Typedefs
typedef struct Heap	Heap
	A dynamically sized min-heap that provides push and pop in log n time in terms of the number of elements in the heap.
Enumerations
enum	HeapType { MAX_HEAP, MIN_HEAP }
	Whether the heap is a min-heap or a max-heap.
Functions
cdsa_status_t	heap_new (Heap **new_heap, size_t capacity, HeapType heap_type, cdsa_compare_func_t compare, cdsa_destroy_func1_t destroy)
	Create a new heap with the given compare function for determining the heap ordering, optionally specifying an initial capacity for the underlying array (or default is used if 0), setting *new_heap to the resulting heap.
cdsa_status_t	heap_new_from_ptr_array (Heap **new_heap, size_t capacity, HeapType heap_type, void *arr, size_t nmemb, size_t ptrsize, cdsa_compare_func_t compare, cdsa_destroy_func1_t destroy)
	Create a new heap in linear time from the given array of pointers, setting *new_heap to the resulting heap.
cdsa_status_t	heap_new_from_data_array (Heap **new_heap, size_t capacity, HeapType heap_type, void *arr, size_t nmemb, size_t membsize, cdsa_compare_func_t compare, cdsa_destroy_func1_t destroy)
	Create a new heap in linear time from the given array of data.
cdsa_status_t	heap_destroy (Heap **heap)
	Destroy the heap, free its associated memory, and set *heap to NULL.
cdsa_status_t	heap_type (Heap *heap, HeapType *heap_type)
	Answer whether heap is a min heap or a max heap, recording answer in heap_type.
cdsa_status_t	heap_is_empty (Heap *heap, bool *is_empty)
	Answer if the heap contains no elements, recording result in *is_empty.
cdsa_status_t	heap_size (Heap *heap, size_t *size)
	Answer the size of the heap, recording result in *size.
cdsa_status_t	heap_capacity (Heap *heap, size_t *capacity)
	Answer the capacity of the heap, or 0 if heap is NULL.
cdsa_status_t	heap_push (Heap *heap, void *data)
	Add an item onto the heap.
cdsa_status_t	heap_pop (Heap *heap, void *ptr)
	Remove the minimum element (according to given compare function) from the heap and *ptr to element.
cdsa_status_t	heap_peek (Heap *heap, void *ptr)
	Answer the minimum element (according to given compare function) without removing it, recording value in *ptr.
cdsa_status_t	heap_clear (Heap *heap)
	Remove all elements from the heap, maintaining the current capacity.
cdsa_status_t	heap_sort (void *arr, size_t nmemb, size_t ptrsize, cdsa_compare_func_t compare)
	Sort the first nmemb items in the given array of pointers.

---

Detailed Description

A min-heap that dynamically expands its capacity when necessary.

Definition in file heap.h.

---

Typedef Documentation

Heap

A dynamically sized min-heap that provides push and pop in log n time in terms of the number of elements in the heap.

You can either rely on the default size by specifying an initial_capacity of 0, or you can specify some other initial_capacity if you know the maximum number of elements you will need to store. The heap capacity always expands to the smallest power of two that is greater than the current capacity when necessary. You may choose any positive number as the initial capacity, but it will still expand to the next greater power of two if it has to expand.

This heap implementation guarantees that for any elements x and y that are placed in the heap, x will always be popped before y if x compares less than y, and y will always be popped before x if y compares less than x. If x and y compare as equal, the ordering is unspecified, and either x or y may be popped first.

Definition at line 58 of file heap.h.

---

Function Documentation

cdsa_status_t heap_new	(	Heap **	new_heap,
		size_t	capacity,
		HeapType	heap_type,
		cdsa_compare_func_t	compare,
		cdsa_destroy_func1_t	destroy
	)

Create a new heap with the given compare function for determining the heap ordering, optionally specifying an initial capacity for the underlying array (or default is used if 0), setting *new_heap to the resulting heap.

The heap stores only pointers, so the client is responsible for all memory management of heap objects. The memory of the heap itself is freed when heap_destroy is called.

Parameters:

	new_heap	A non-NULL pointer to a Heap pointer, to be set to the new heap on success.
	capacity	The initial capacity of the heap, which ensures space to store initial_capacity elements without expanding the capacity. If equal to 0, then DEFAULT_HEAP_CAPACITY is the initial capacity.
	heap_type	The type of heap to create (min or max).
	compare	A non-NULL pointer to a compare function that will be used to compare the elements in the heap, given a pointer to each element.
	destroy	A function pointer (or NULL) that will be applied to each element in the heap when the heap is destroy.

cdsa_status_t heap_new_from_ptr_array	(	Heap **	new_heap,
		size_t	capacity,
		HeapType	heap_type,
		void *	arr,
		size_t	nmemb,
		size_t	ptrsize,
		cdsa_compare_func_t	compare,
		cdsa_destroy_func1_t	destroy
	)

Create a new heap in linear time from the given array of pointers, setting *new_heap to the resulting heap.

This method creates a heap that stores the nmemb pointers that are stored in the given array. It does not use the given array as the backing array for the heap. Instead, it copies the pointers from the array into the heap. Using this function is equivalent to creating an empty heap and adding the pointers one by one, but it is much more efficient.

Parameters:

	new_heap	A non-NULL pointer to a Heap pointer, to be set to the new heap on success.
	capacity	The requested capacity (or 0 for default), which if nonzero should be at least equal to nmemb (i.e., sufficient capacity to store all the pointers). If a nonzero capacity is specified that isn't large enough, the capacity will be ignored, and a capacity sufficient to hold the pointers will be used.
	heap_type	The type of heap to create (min or max).
	arr	The base of the array of pointers.
	nmemb	The number of pointers to be copied from the array.
	ptrsize	The size of the pointers.
	compare	A non-NULL pointer to a compare function that will be used to compare the elements in the heap, given a pointer to each element.
	destroy	A function pointer (or NULL) that will be applied to each element in the heap when the heap is destroy.

cdsa_status_t heap_new_from_data_array	(	Heap **	new_heap,
		size_t	capacity,
		HeapType	heap_type,
		void *	arr,
		size_t	nmemb,
		size_t	membsize,
		cdsa_compare_func_t	compare,
		cdsa_destroy_func1_t	destroy
	)

Create a new heap in linear time from the given array of data.

This method creates a heap that includes nmemb pointers into the given array, unlike heap_new_from_ptr_array, which copies the pointers that are stored in the array. Using this function is equivalent to creating an empty heap and adding the address of each element in the array one by one, but it is much more efficient.

Parameters:

	new_heap	A non-NULL pointer to a Heap pointer, to be set to the new heap on success.
	capacity	The requested capacity (or 0 for default), which if nonzero should be at least equal to nmemb (i.e., sufficient capacity to store all the pointers). If a nonzero capacity is specified that isn't large enough, the capacity will be ignored, and a capacity sufficient to hold the pointers will be used.
	heap_type	The type of heap to create (min or max).
	arr	The base of the array of pointers.
	nmemb	The number of pointers to be copied from the array.
	membsize	The size of each element in the array.
	compare	A non-NULL pointer to a compare function that will be used to compare the elements in the heap, given a pointer to each element.
	destroy	A function pointer (or NULL) that will be applied to each element in the heap when the heap is destroy.

cdsa_status_t heap_destroy

(

Heap **

heap

)

Destroy the heap, free its associated memory, and set *heap to NULL.

Parameters:

heap

A non-NULL pointer to a non-NULL heap to be destroyed.

If a destroy function was given when the heap was created, it will be applied to every non-NULL pointer in the heap.

cdsa_status_t heap_type	(	Heap *	heap,
		HeapType *	heap_type
	)

Answer whether heap is a min heap or a max heap, recording answer in heap_type.

Parameters:

	heap	A non-NULL heap.
	heap_type	A non-NULL pointer to a HeapType value, to be updated to the actual type on success.

cdsa_status_t heap_is_empty	(	Heap *	heap,
		bool *	is_empty
	)

Answer if the heap contains no elements, recording result in *is_empty.

Parameters:

	heap	A non-NULL heap.
	is_empty	A non-NULL pointer to a bool variable for recording whether heap is empty on success.

cdsa_status_t heap_size	(	Heap *	heap,
		size_t *	size
	)

Answer the size of the heap, recording result in *size.

The size of the heap is the number of elements currently stored in the heap.

Parameters:

	heap	A non-NULL heap.
	size	A non-NULL pointer to a size_t variable for recording size on success.

cdsa_status_t heap_capacity	(	Heap *	heap,
		size_t *	capacity
	)

Answer the capacity of the heap, or 0 if heap is NULL.

The capacity of the heap is the number of elements that can be stored in the heap without causing more space to be allocated. For example, if the capacity is 16, the heap can hold 16 elements without expanding, and pushing a 17th element will cause the heap to expand.

Parameters:

	heap	A non-NULL heap.
	capacity	A non-NULL pointer to a size_t variable, for storing the capacity of the heap on success.

cdsa_status_t heap_push	(	Heap *	heap,
		void *	data
	)

Add an item onto the heap.

Both the heap and data pointers must be non-NULL.

Parameters:

	heap	A non-NULL heap.
	data	A non-NULL pointer to be stored.

cdsa_status_t heap_pop	(	Heap *	heap,
		void *	ptr
	)

Remove the minimum element (according to given compare function) from the heap and *ptr to element.

Parameters:

	heap	A non-NULL heap.
	ptr	A non-NULL pointer for recording the minimum element that was removed on success.

cdsa_status_t heap_peek	(	Heap *	heap,
		void *	ptr
	)

Answer the minimum element (according to given compare function) without removing it, recording value in *ptr.

Parameters:

	heap	A non-NULL heap.
	ptr	A non-NULL pointer for recording the current minimum element on success.

cdsa_status_t heap_clear

(

Heap *

heap

)

Remove all elements from the heap, maintaining the current capacity.

Parameters:

heap

A non-NULL heap.

cdsa_status_t heap_sort	(	void *	arr,
		size_t	nmemb,
		size_t	ptrsize,
		cdsa_compare_func_t	compare
	)

Sort the first nmemb items in the given array of pointers.

This function performs an in-place heap sort on the first nmemb pointers in the array. It requires no extra memory, and it has time complexity of O(n log n).

The array must contain only pointers, each of which is the same size, and the compare function will be passed the pointers that are stored in the array (and not pointers to the array locations themselves).

Parameters:

	arr	An array of pointers each of which is ptrsize bytes in size.
	nmemb	The number of items in the array to be sorted.
	ptrsize	The size of each pointer in bytes.
	compare	A non-NULL compare function for comparing elements.