heap.c File Reference

#include "heap.h"
#include <stdlib.h>

Go to the source code of this file.

Classes
struct	heap

Macros
#define	HEAP_INITIAL_CAP   16

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)
static bool	heap_grow (heap_t *h)
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)
static void	sift_down_min (int *arr, size_t i, size_t n)
static void	sift_up_min (int *arr, size_t i)
static void	swap (int *a, int *b)

Macro Definition Documentation

HEAP_INITIAL_CAP

#define HEAP_INITIAL_CAP   16

Definition at line 8 of file heap.c.

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_grow()

static bool heap_grow ( heap_t *  h )

static

Definition at line 34 of file heap.c.

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

Referenced by heap_insert().

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.

sift_down_min()

static void sift_down_min ( int *  arr, size_t  i, size_t  n  )

static

Definition at line 52 of file heap.c.

References swap().

Referenced by heap_build_min(), and heap_extract_min().

sift_up_min()

static void sift_up_min ( int *  arr, size_t  i  )

static

Definition at line 43 of file heap.c.

References swap().

Referenced by heap_insert().

swap()

static void swap ( int *  a, int *  b  )

static

Definition at line 16 of file heap.c.

Referenced by heap_sift_down_max(), sift_down_min(), and sift_up_min().