writeHeap.C File Reference

Demonstrates array-based heap structure and generates visualization files. More...

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <ctime>
#include <tclap/CmdLine.h>
#include <tpl_arrayHeap.H>

Include dependency graph for writeHeap.C:

Go to the source code of this file.

Macros
#define	HEAP_LLINK(i)   (2*(i))
#define	HEAP_RLINK(i)   (2*(i) + 1)

Functions
void	preorder (int v[], int n, int i)
	Write preorder traversal of heap.
void	inorder (int v[], int n, int i)
	Write inorder traversal of heap.
void	level_order (int v[], int n)
	Write level-order traversal for LaTeX output.
bool	exists_in_heap (ArrayHeap< int > &heap, int x)
	Check if value exists in heap.
int	main (int argc, char *argv[])

Variables
ofstream	output
ofstream	output_tex

Detailed Description

Demonstrates array-based heap structure and generates visualization files.

This program creates an array-based min-heap (priority queue) with random values and generates visualization files showing the heap structure in various traversal orders. Heaps are fundamental data structures for priority queues and efficient sorting.

What is a Heap?

A heap is a complete binary tree stored in an array that satisfies the heap property:

• Min-heap: Parent ≤ children (smallest at root)
• Max-heap: Parent ≥ children (largest at root)

Key properties:

• Complete binary tree: All levels full except possibly last, filled left-to-right
• Heap property: Parent-child relationship maintained
• Array storage: Efficient representation without pointers

Array Representation

Indexing Scheme (1-indexed)

Heaps use a clever array indexing scheme:

• Parent of node i: i/2 (integer division)
• Left child of node i: 2*i
• Right child of node i: 2*i + 1
• Root: Index 1 (index 0 unused or stores size)

Example

Array: [-, 1, 3, 2, 5, 4, 6]
Index:  0  1  2  3  4  5  6
 
Tree:
        1 (index 1)
       / \
      3   2 (indices 2, 3)
     / \ / \
    5  4 6  (indices 4, 5, 6)

Advantages

• Space efficient: No pointers needed (saves memory)
• Cache friendly: Sequential memory access (better performance)
• Fast navigation: Simple arithmetic for parent/child (O(1))
• Simple implementation: Easy to code and understand

Heap Operations

Insertion (Bubble Up)

insert(value):
  1. Add value at end of array
  2. While value < parent:
     Swap with parent
     Move up tree

Time: O(log n) - height of tree

Extract Minimum (Bubble Down)

extract_min():
  1. Save root value
  2. Move last element to root
  3. While heap property violated:
     Swap with smaller child
     Move down tree
  4. Return saved value

Time: O(log n) - height of tree

Build Heap (Heapify)

build_heap(array):
  For i = n/2 down to 1:
    heapify_down(i)

Time: O(n) - surprisingly efficient! Why: Most nodes are near bottom, few swaps needed

Complexity Summary

Operation	Time Complexity	Description
insert	O(log n)	Add element, bubble up
extract_min	O(log n)	Remove root, bubble down
peek	O(1)	Get root without removal
build_heap	O(n)	Heapify array in-place
decrease_key	O(log n)	Decrease element, bubble up
increase_key	O(log n)	Increase element, bubble down

Applications

Priority Queues

• Task scheduling: Execute highest priority tasks first
• Event simulation: Process events in chronological order
• Operating systems: Process scheduling

Graph Algorithms

• Dijkstra's algorithm: Find shortest paths (min-heap)
• Prim's MST: Find minimum spanning tree (min-heap)
• A* search: Pathfinding with heuristics

Sorting

• Heap sort: O(n log n) in-place sorting
• Partial sort: Sort first k elements efficiently

Statistics

• Median finding: Use two heaps (min + max)
• Top-k queries: Keep k largest/smallest elements
• Percentiles: Find k-th percentile efficiently

Heap vs Other Structures

Structure	Insert	Extract Min	Build	Best For
Heap	O(log n)	O(log n)	O(n)	Priority queues
Sorted Array	O(n)	O(1)	O(n log n)	Static data
BST	O(log n)	O(log n)	O(n log n)	Dynamic, ordered
Linked List	O(1)	O(n)	O(n)	Simple cases

Output Files

• **heap-ejm-aux.Tree**: Preorder and inorder traversals for btreepic
  • Shows tree structure
  • Can be visualized with btreepic tool
• **heap-ejm-aux.tex**: Level-order traversal formatted for LaTeX
  • Shows array representation
  • Useful for documentation

The tree visualization shows the heap structure, which is a complete binary tree (all levels full except possibly the last, filled left-to-right).

Usage

# Generate heap with 20 elements
writeHeap -n 20
 
# Use specific seed for reproducibility
writeHeap -n 50 -s 42
 
# Generate larger heap
writeHeap -n 100

See also

tpl_arrayHeap.H Array-based heap implementation

heap_example.C Comprehensive heap examples (Binary vs Fibonacci)

btreepic.C Visualization tool for binary trees

Author

Leandro Rabindranath León

Definition in file writeHeap.C.

Macro Definition Documentation

HEAP_LLINK

#define HEAP_LLINK

(

i

)

(2*(i))

Definition at line 209 of file writeHeap.C.

HEAP_RLINK

#define HEAP_RLINK

(

i

)

(2*(i) + 1)

Definition at line 210 of file writeHeap.C.

Function Documentation

exists_in_heap()

bool exists_in_heap	(	ArrayHeap< int > &	heap,
		int	x
	)

Check if value exists in heap.

Parameters

heap	The heap to search
x	Value to find

Returns

true if found

Definition at line 275 of file writeHeap.C.

References Aleph::ArrayHeap< T, Compare >::size().

Referenced by main().

inorder()

void inorder	(	int	v[],
		int	n,
		int	i
	)

Write inorder traversal of heap.

Parameters

v	Heap array (1-indexed)
n	Number of elements
i	Current index

Definition at line 242 of file writeHeap.C.

References HEAP_LLINK, HEAP_RLINK, inorder(), Aleph::maps(), and output.

Referenced by avl_to_btreepic(), Aleph::build_tree(), build_tree(), inorder(), main(), read_from_stream(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

level_order()

void level_order	(	int	v[],
		int	n
	)

Write level-order traversal for LaTeX output.

Parameters

v	Heap array (1-indexed)
n	Number of elements

Definition at line 260 of file writeHeap.C.

References Aleph::maps(), and output_tex.

Referenced by main().

main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 283 of file writeHeap.C.

References exists_in_heap(), inorder(), Aleph::ArrayHeap< T, Compare >::insert(), level_order(), Aleph::maps(), output, output_tex, preorder(), Aleph::ArrayHeap< T, Compare >::size(), and Aleph::ArrayHeap< T, Compare >::top().

preorder()

void preorder	(	int	v[],
		int	n,
		int	i
	)

Write preorder traversal of heap.

Parameters

v	Heap array (1-indexed)
n	Number of elements
i	Current index

Definition at line 222 of file writeHeap.C.

References HEAP_LLINK, HEAP_RLINK, Aleph::maps(), output, and preorder().

Referenced by avl_to_btreepic(), Aleph::build_tree(), build_tree(), main(), preorder(), Aleph::preorder_to_bst(), and read_from_stream().

Variable Documentation

output

ofstream output

Definition at line 213 of file writeHeap.C.

Referenced by Aleph::__generate_tree(), avl_to_btreepic(), Aleph::Huffman_Decoder_Engine::decode(), Eepic_Geom_Object::draw(), Eepic_Point::draw(), Eepic_Segment::draw(), Eepic_Arrow::draw(), Eepic_Thick_Segment::draw(), Eepic_Thick_Dash_Segment::draw(), Eepic_Thick_Arrow::draw(), Eepic_Dotted_Segment::draw(), Eepic_Dash_Segment::draw(), Eepic_Dotted_Arrow::draw(), Eepic_Dash_Arrow::draw(), Eepic_Thick_Dash_Arrow::draw(), Eepic_Triangle::draw(), Eepic_Ellipse::draw(), Eepic_Shade_Ellipse::draw(), Eepic_Thick_Ellipse::draw(), Eepic_Text::draw(), Eepic_Left_Text::draw(), Eepic_Right_Text::draw(), Eepic_Center_Text::draw(), Eepic_Polygon::draw(), Eepic_Polygon_With_Points::draw(), Eepic_Polygon_With_Arrows::draw(), Eepic_Dotted_Polygon::draw(), Eepic_Dash_Polygon::draw(), Eepic_Dotted_Polygon_With_Points::draw(), Eepic_Dash_Polygon_With_Points::draw(), Eepic_Dash_Polygon_With_Arrow::draw(), Eepic_Shade_Polygon::draw(), Eepic_Shade_Polygon_With_Points::draw(), Eepic_Shade_Polygon_With_Arrows::draw(), Eepic_Shade_Polygon_With_Text_Points::draw(), Eepic_Shade_Polygon_With_Vertex_Numbers::draw(), Eepic_Spline::draw(), Eepic_Dash_Spline::draw(), Eepic_Spline_Arrow::draw(), Eepic_Dash_Spline_Arrow::draw(), Eepic_Thick_Polygon_With_Points::draw(), Eepic_Thick_Polygon_With_Arrows::draw(), Eepic_Thick_Dotted_Polygon::draw(), Eepic_Thick_Dash_Polygon::draw(), Eepic_Thick_Dotted_Polygon_With_Points::draw(), Eepic_Thick_Dash_Polygon_With_Points::draw(), Eepic_Thick_Dash_Polygon_With_Arrow::draw(), Eepic_Thick_Shade_Polygon::draw(), Eepic_Thick_Shade_Polygon_With_Points::draw(), Eepic_Thick_Shade_Polygon_With_Arrows::draw(), Eepic_Thick_Shade_Polygon_With_Text_Points::draw(), Eepic_Thick_Shade_Polygon_With_Vertex_Numbers::draw(), Eepic_Thick_Spline::draw(), Eepic_Thick_Dash_Spline::draw(), Eepic_Thick_Spline_Arrow::draw(), Eepic_Thick_Dash_Spline_Arrow::draw(), Eepic_Regular_Polygon::draw(), Eepic_Regular_Polygon_With_Points::draw(), Eepic_Dotted_Regular_Polygon::draw(), Eepic_Dash_Regular_Polygon::draw(), Eepic_Dotted_Regular_Polygon_With_Points::draw(), Eepic_Dash_Regular_Polygon_With_Points::draw(), Eepic_Shade_Regular_Polygon::draw(), Eepic_Shade_Regular_Polygon_With_Points::draw(), Eepic_Shade_Regular_Polygon_With_Arrows::draw(), Eepic_Shade_Regular_Polygon_With_Text_Points::draw(), Eepic_Shade_Regular_Polygon_With_Vertex_Numbers::draw(), Eepic_Plane::draw(), draw_arc(), draw_arc_tikz(), Eepic_Plane::draw_arrow(), Eepic_Plane::draw_arrow_dash_segment(), Eepic_Plane::draw_arrow_dotted_segment(), Eepic_Plane::draw_arrows_in_polygon(), Eepic_Plane::draw_cartesian_axis(), Eepic_Plane::draw_closed_polygon(), Eepic_Plane::draw_closed_polygon_with_arrows(), Eepic_Plane::draw_dash_segment(), Eepic_Plane::draw_dash_spline(), Eepic_Plane::draw_dash_spline_arrow(), Eepic_Plane::draw_dots_from_polygon(), Eepic_Plane::draw_dotted_closed_polygon(), Eepic_Plane::draw_dotted_segment(), Eepic_Plane::draw_ellipse(), Eepic_Plane::draw_point(), Eepic_Plane::draw_point_text(), Eepic_Plane::draw_points_text_in_polygon(), Eepic_Plane::draw_polygon(), Eepic_Plane::draw_segment(), Eepic_Plane::draw_spline(), Eepic_Plane::draw_spline_arrow(), Eepic_Plane::draw_text(), Eepic_Plane::draw_vertex_numbers_in_polygon(), Aleph::floyd_all_shortest_paths_latex(), generate_bin_tree(), generate_cross_spanning_tree(), generate_curve(), Aleph::generate_dot_file(), generate_epilogue(), generate_forest(), generate_graph(), Aleph::generate_graphpic(), Aleph::generate_graphviz(), generate_infix_traversal(), generate_net_spanning_tree(), generate_picture(), generate_prefix_traversal(), generate_prologue(), generate_split_lines(), generate_tree(), generate_tree(), huffman_to_btreepic(), inorder(), main(), Aleph::Dft_Store_Arc< GT >::operator()(), Aleph::Dft_Store_Node< GT >::operator()(), Aleph::Warc< GT >::operator()(), Aleph::Wnode< GT >::operator()(), Aleph::Dft_Store_Arc< GT >::operator()(), Aleph::Dft_Store_Node< GT >::operator()(), preorder(), put_string(), put_string_tkiz(), Aleph::IO_Graph< GT, Load_Node, Store_Node, Load_Arc, Store_Arc, NF, AF >::save(), Aleph::BitArray::save(), Aleph::BitArray::save_in_array_of_chars(), Aleph::IO_Graph< GT, Load_Node, Store_Node, Load_Arc, Store_Arc, NF, AF >::save_in_text_mode(), Aleph::Huffman_Encoder_Engine::save_leaf_keys_in_prefix(), save_parameters(), Aleph::Huffman_Encoder_Engine::save_string_as_bytes(), Aleph::save_tree(), Aleph::Huffman_Encoder_Engine::save_tree(), Aleph::Huffman_Encoder_Engine::save_tree_in_array_of_chars(), Aleph::save_tree_in_array_of_chars(), Aleph::save_tree_keys_in_prefix(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), write_avl(), write_bin(), write_rand(), write_rb(), write_splay(), and write_treap().

output_tex

ofstream output_tex

Definition at line 214 of file writeHeap.C.

Referenced by level_order(), and main().