Operations on heaps. More...

#include "global.h"
#include <assert.h>
#include "heap.h"

Include dependency graph for src/heap.c:

Data Structures
struct	heap_element
struct	heap_struct
Functions
static int	__heap_is_good (heap_t *heap)
heap_t *	heap_create ()
	Create an empty heap.
void	heap_destroy (heap_t **heap)
	Destroy a heap.
void	heap_free (heap_t heap, void(freefunc)(void *))
	Free all elements in the heap.
static void	__upheap (heap_t *heap, int k)
void	heap_insert (heap_t heap, cost_t cost, void data)
static void	__downheap (heap_t *heap, int k)
	This procedure moves down the heap.
void *	heap_remove_smallest (heap_t *heap)
	Remove the smallest item from the heap.
void *	heap_replace (heap_t heap, cost_t cost, void data)
	Replace the smallest item with a new item and return the smallest item.
int	heap_is_empty (heap_t *heap)
	Return whether the heap is empty.
int	heap_size (heap_t *heap)
	Return the size of the heap.
Variables
static cost_t	MIN_COST = 0

Detailed Description

Operations on heaps.

This file, heap.c, was written and is

Copyright.

PCB, interactive printed circuit board design

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.

Contact addresses for paper mail and Email: harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA haceaton@aplcomm.jhuapl.edu

Definition in file src/heap.c.

Function Documentation

static void __downheap	(	heap_t *	heap,
		int	k
	)		`[static]`

This procedure moves down the heap.

Exchanging the node at position k with the smaller of its two children as necessary and stopping when the node at k is smaller than both children or the bottom is reached.

Definition at line 206 of file src/heap.c.

References heap_element::cost.

Referenced by heap_remove_smallest(), and heap_replace().

static int __heap_is_good ( heap_t * heap ) [static]

Definition at line 100 of file src/heap.c.

Referenced by heap_create(), heap_destroy(), heap_free(), heap_insert(), heap_is_empty(), heap_remove_smallest(), heap_replace(), and heap_size().