heap.h File Reference

Binary min-heap (array-backed priority queue) of int. More...

#include <stdbool.h>
#include <stddef.h>

Go to the source code of this file.

Typedefs
typedef struct heap	heap_t

Functions
void	heap_build_min (int *arr, size_t n)
heap_t *	heap_create (void)
void	heap_destroy (heap_t *h)
bool	heap_extract_min (heap_t *h, int *out_value)
bool	heap_insert (heap_t *h, int value)
bool	heap_is_empty (const heap_t *h)
bool	heap_peek_min (const heap_t *h, int *out_value)
void	heap_sift_down_max (int *arr, size_t i, size_t n)
size_t	heap_size (const heap_t *h)

Detailed Description

Binary min-heap (array-backed priority queue) of int.

Min-heap: parent ≤ children. Array layout — for index i, left child = 2i+1, right child = 2i+2, parent = (i-1)/2.

Operation	Time
insert	O(log n)
extract_min	O(log n)
peek_min	O(1)
heapify (build from array)	O(n) — linear via sift-down

Definition in file heap.h.

Typedef Documentation

heap_t

typedef struct heap heap_t

Definition at line 22 of file heap.h.

Function Documentation

heap_build_min()

void heap_build_min	(	int *	arr,
		size_t	n
	)

Build a min-heap from an existing array in O(n). The array is reordered in place.

Definition at line 94 of file heap.c.

References sift_down_min().

heap_create()

heap_t * heap_create

(

void

)

Definition at line 18 of file heap.c.

References heap::capacity, heap::data, HEAP_INITIAL_CAP, and heap::size.

heap_destroy()

void heap_destroy

(

heap_t *

h

)

Definition at line 28 of file heap.c.

References heap::data.

heap_extract_min()

bool heap_extract_min	(	heap_t *	h,
		int *	out_value
	)

Definition at line 74 of file heap.c.

References heap::data, sift_down_min(), and heap::size.

heap_insert()

bool heap_insert	(	heap_t *	h,
		int	value
	)

Definition at line 65 of file heap.c.

References heap::capacity, heap::data, heap_grow(), sift_up_min(), and heap::size.

heap_is_empty()

bool heap_is_empty

(

const heap_t *

h

)

Definition at line 92 of file heap.c.

References heap::size.

heap_peek_min()

bool heap_peek_min	(	const heap_t *	h,
		int *	out_value
	)

Definition at line 85 of file heap.c.

References heap::data, and heap::size.

heap_sift_down_max()

void heap_sift_down_max	(	int *	arr,
		size_t	i,
		size_t	n
	)

Sift-down at index i for an n-element array — exposed for heap sort.

Definition at line 103 of file heap.c.

References swap().

Referenced by heap_sort_ints().

heap_size()

size_t heap_size

(

const heap_t *

h

)

Definition at line 91 of file heap.c.

References heap::size.